Numbering permutations

Question

Given an alphabet A = {a,b,c,d,...} of length n, I would like to get all permutations of length r (r < n).

Now I would like to number these permutations, and there should be a reverse mapping.

For example:

A = {a,b,c}, r = 2

ab -> 0
ba -> 1
ac -> 2
ca -> 3
...

How can I achieve this? I have found it for problems which are order-invariant. But I cant apply it to this situation with the order.

Is there some library doing it in python?

Answer 1

Presumably aa is an invalid selection. Since you are dealing from a distinct alphabet, each deal produces a non-intersecting set of permutations. Your list is counted by r! * choose(n,r) which is n!/(n-r)! or n_r or "k-permutations of n elements." The canonical way to number these is lexicographically.

If I were attempting to generate these using a generic library, I would find a way to deal or choose the unrepeated r elements, then produce all permutations on that set of size r. As far as numbering goes, if you can store the permutations lexicographically in an array you can binsearch to find the index. It is possible to reverse the mapping analytically, but realistically, whatever you're doing here is going to have to have small r.

A quick search shows Python's itertools give you two functions you need: combinations and permutations.

Answer 2

We know that there are n permutations of length one (where n is the length of the alphabet). Permutations of length r are all of the permutations of length r-1 appended with each of the n elements in the alphabet. There are n^r of these.

Assigning ids permutations is straight-forward, since generating permutations and counting are really the same thing.

Here, in JS, we compute permutations or length r with any array of characters. To illustrate the idea about counting, see the output when the alphabet is the set of digits '0'='9'...

function permute(r, alphabet) {
  if (r === 1) return alphabet
  let result = []
  let r1 = permute(r-1, alphabet)
  for (let p of r1) {
    for (let a of alphabet) {
      result.push(p+a)
    }
  }
  return result
}

const permutations = permute(3, ['a', 'b', 'c', 'd']);
const withIds = permutations.map((value, id) => ({id, value}));
console.log(withIds);

Same thing in python...

def permute(r, alphabet):
    if r == 1: return alphabet
    result = []
    r1 = permute(r-1, alphabet)
    for p in r1:
        for a in alphabet:
            result.append(p+a)
    return result