Algorithm for finding the index of given permutation of a multiset permutation

Question

I am trying to find the most efficient algorithm to find the index of given permutation of a multiset permutations of '0' and '1'.

Ex: Given {0, 0, 1, 1}. All possible permutations in ascending order are: {0011, 0101, 0110, 1001, 1010, 1100}. These elements are indexed as 0 -> 6. Given s = 0110, the result is 2.

This question is quite similar to here, but his question is on proper set (e.g., {1, 2, 3}). Another similar question is here, but the answer is O(N!). The following code is my try, but it is not efficient too (O(N!)).

def find_index(s, pos): # s is the given permutation, pos is the index list of '1' in s
    d_index = 0
    c = 0
    for i in range (len(pos)-1, -1, -1):
        d_index = d_index + 1
        if (len-1-pos[i] >= d_index):
            c_i = c_i + Combination (d_index, len-1-pos[i])
    if (c == 0):
        return 0
    return c

http://stackoverflow.com/questions/22219074/calculate-the-index-of-a-given-number-within-a-sorted-set/22219424#22219424 this question is already discussed here. — Pham Trung, Jul 09 '14 at 07:37
@PhamTrung: thank you. The answer of Gassa seems to be similar to me. I wonder is there a more efficient way. — santa, Jul 09 '14 at 07:51
I don't think so, his answer is O(N) with N is number of bit, I think it is optimal. — Pham Trung, Jul 09 '14 at 07:55
But doesn't that require a sorted list of all the permutations? — user2963623, Jul 09 '14 at 08:01
@PhamTrung: thank you very much. I am trying Glassa and hivert methods on my tests. — santa, Jul 09 '14 at 08:22
@user2963623 No, it just iterate from bit to bit of the current permutation. For example, you have 2 bit 1 and 2 bit 0, so if you see the first 1 bit at position 4, so this current permutation should be greater than C(3,2) other permutations (chosing 2 position to be 1 in the last 3 position) — Pham Trung, Jul 09 '14 at 08:33
@PhamTrung: I am trying to find the opposite algorithm (find permutation of a set of '0' and '1', given index). Could you please kindly show me. I actually asked this question in [http://stackoverflow.com/questions/24506460/algorithm-for-finding-multiset-permutation-given-lexicographic-index], the answer is O(N^2). Is there any way which takes O(N)? Thanks in advance — santa, Jul 15 '14 at 05:53

score 0 · Answer 1 · answered Jul 09 '14 at 08:14

This approach simply loops over all the binary numbers till the given number s and checks if each number has the required number of 0s and 1s, if it does then increments a counter.

s = '0110'     # input
count_0 = s.count('0')
count_1 = s.count('1')
l = len(s)
index = 0
for i in xrange(0, int(s,2)):
    binary = ('{:0%sb}'%l).format(i) #converts integer into binary of length l bits
    if binary.count('0') == count_0 and binary.count('1') == count_1: index += 1

score 0 · Answer 2 · answered Jul 09 '14 at 08:24

First solve this problem : Given a multiset, find the n-th permutation. You can do this recursively. Let F(S, n) be a function which computes two things : the n-th permutation of multiset S and the total number of permutations.

`F(S, ~).total = F(S-{0}, ~).total + F(S-{1}, ~).total`.

If F(S-{0}, ~).total < n, F(S, n) = 0 . F(S-{0}, n) else F(S, n) = 1 . F(S-{1}, n - F(S-{0}, ~).total)

Armed with F(S, n), you can do a binary search to find the index of your required permutation. The range for this binary search will be [0, N!].

Let's add up the runtimes : if S in your initial set and |S| = N, computing all the F(s, n)s requires O(N) time per state, assuming you are memoizing(this accounts for the fact that hashing your state might not be O(1)). The number of states is O(N*2^N). The binary search takes O(log N!) = O(N log N), giving you a runtime of O(N*2^N).

score 0 · Answer 3 · answered Jul 09 '14 at 13:51

why is it not posible to use a list?

s = '0110'
p = ['0011', '0101', '0110', '1001', '1010', '1100']
p.index(s)

To make the data storage even more efficient you could use them as integers:

s = 0b0110
p = [0b0011, 0b0101, 0b0110, 0b1001, 0b1010, 0b1100]

Indexing works the same way.

Algorithm for finding the index of given permutation of a multiset permutation

3 Answers3