2

Given an array of length n, I need to print out the array's lexicographic index (indexed from zero). The lexicographic index is essentially the location that the given array would have if placed in a super-array containing all possible permutations of the original array.

This doesn't turn out to be all that difficult (Unique Element Permutations), but my problem is now making the same algorithm, but for an array containing duplicates of the same element.

Here's an example chart showing some of the possible permutations of a small array, and their respective expected return values:

[0 1 1 2 2]->0
[0 1 2 1 2]->1
[0 1 2 2 1]->2
[0 2 1 1 2]->3
[0 2 1 2 1]->4
[0 2 2 1 1]->5
[1 0 1 2 2]->6
[1 0 2 1 2]->7
[1 0 2 2 1]->8
[1 1 0 2 2]->9
[1 1 2 0 2]->10
[1 1 2 2 0]->11
..
[2 2 1 0 1]->28
[2 2 1 1 0]->29

Most importantly, I want to do this WITHOUT generating other permutations to solve the problem (for example, I don't want to generate all permutations less than the given permutation).

I'm looking for pseudocode - no specific language needed as long as I can understand the concept. Even the principle for calculation without pseudocode would be fine.

I've seen some implementations that do something similar but for a binary string (containing only two distinct types of elements), and they used binomial coefficients to get the job done. Hopefully that helps.

A Frayed Knot
  • 476
  • 5
  • 20
  • Is lexicographic order important? I think I have a solution, that give you index in some order of permutations. – jindraivanek Aug 03 '14 at 10:46
  • See this [previous stackoverflow post](http://stackoverflow.com/questions/5131497/find-the-index-of-a-given-permutation-in-the-sorted-list-of-the-permutations-of) – Daishisan Jul 15 '16 at 17:20

1 Answers1

1

As an aside, though the answers to the question linked in Daishisan's comment fulfil the multiset case, the algorithm in your link for binary numbers (for which I was searching when I came upon your answer) works for indexing because it's bijective, but doesn't index the binary number within the sorted infinite sequence of those with the same bit count as you may expect. With the following dependencies,

from functools import reduce
fact=(lambda n: reduce(int.__mul__,range(1,n+1)) if n else 1)
choose=(lambda n,*k: fact(n)//(reduce(int.__mul__,map(fact,k))*fact(n-sum(k))) if all(map(lambda k: 0<=k,k+(n-sum(k),))) else 0)
decompose=(lambda n,l=None: (n>>i&1 for i in range(n.bit_length() if l==None else l)))

It is equivalent to

lambda i,n: reduce(lambda m,i: (lambda s,m,i,b: (s,m-1) if b else (s+choose(n+~i,m),m))(*m,*i),enumerate(decompose(i,n)),(0,i.bit_count()-1))[0]

However, I played with it and found a reduced version that does fulfil this purpose (and thus doesn't need a length specified).

lambda i: reduce(lambda m,i: (lambda s,m,i,b: (s+choose(i,m),m) if b else (s,m+1))(*m,*i),enumerate(decompose(i)),(0,-1))[0]

This is equivalent to A079071 in the OEIS.

Edit: More efficient version without fact and choose (instead mutating choose's output in-place with the other variables)

lambda i: reduce(lambda m,i: (lambda s,m,c,i,b: ((s+c,m,c*i//(i-m+1)) if b else (s,m+1,c*i//m)) if m else (s,m+1-b,c))(*m,*i),enumerate(decompose(i),1),(0,0,1))[0]
DroneBetter
  • 19
  • 6