Combining Two Mathematical Permutations

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 ")
This entry was posted in Miscellaneous. Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s