I was walking my dogs one evening when I thought of a problem: how to combine two mathematical permutations. Suppose:

perm0 = [2 8 4 9 1 6 7 3 0 5] perm1 = [3 5 1 2 9 8 0 6 7 4]

Here I use 0-based permutations of order = 10. How can you combine the two permutations in a way that retains characteristics of the source permutations, as opposed to just a random result?

Each element in a permutation is unique which makes it a bit tricky to combine them. For example, if you naively take the left half of perm0 and the right half of perm1 the result is [2 8 4 9 1 8 0 6 7 4] which isn’t valid because there are two 8s and two 4s in the result (and no 3 and no 5).

I came up with several algorithms to combine two permutations — most of them incorrect. Eventually (embarrassingly, after several hours) I thought of a simple approach. I create a candidate list that is the first half of perm0, followed by the first half of perm1, followed by the second half of perm0, followed by the second half of perm1. Then iterate through the candidates, fetching the first non-used value.

For the two permutations above, the candidate list is:

2 8 4 9 1 * 3 5 1 2 9 * 6 7 3 0 5 * 8 0 6 7 4

The iteration adds 2, 8, 4, 9, 1, 3, 5 (all unused) but then hits 1 which has already been used, and so advances to 2 (used), 9 (used), then 6 (not used and so adds to result). And so on. The resulting combined permutation is:

[2 8 4 9 1 3 5 6 7 0]

The order in which candidates are created (first half of perm0, first half of perm1, second half of perm0, second half of perm1) is something I need to think about a bit more.

The problem of combining two permutations has been in the back of my mind for a long time. It might be useful for an evolutionary algorithm for combinatorial optimization. But that’s another blog post.

*Slot machines are applied permutations. Left: The first true slot machine was called the Liberty Bell. It was designed by Charles Fey in San Francisco, in approximately 1890 (exact date not clear). Center: The first modern slot machine that had automatic payout was the Money Honey by Bally in 1963. Right: The first rudimentary but functional video slot machine was designed by Fortune Coin Company in 1976 in Las Vegas. It was so unique at the time, it didn’t need a name.*

*Modern slot machines are very sophisticated and practically works of art. I don’t enjoy playing slot machines because there is no decision making by the player. But I do admire the wildly creative designs I see when I’m in Las Vegas.*

Demo code.

# combine_perms.py import numpy as np # ----------------------------------------------------------- def combine(perm0, perm1): n = len(perm0) result = np.zeros(n, dtype=np.int64) used = np.zeros(n, dtype=np.int64) candidates = [] for i in range(0, n//2): candidates.append(perm0[i]) for i in range(0, n//2): candidates.append(perm1[i]) for i in range(n//2, n): candidates.append(perm0[i]) for i in range(n//2, n): candidates.append(perm1[i]) idx = 0 for i in range(n): while (used[candidates[idx]] == 1): # advance to unused idx += 1 result[i] = candidates[idx] used[candidates[idx]] = 1 return result # ----------------------------------------------------------- print("\nBegin combine permutations demo ") rnd = np.random.RandomState(0) n = 10 perm0 = rnd.permutation(n) perm1 = rnd.permutation(n) print("\nperm0: ") print(perm0) print("\nperm1: ") print(perm1) p = combine(perm0, perm1) print("\nCombined: ") print(p) print("\nEnd demo ")

You must be logged in to post a comment.