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

Answer 1

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

Answer 2

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).

Answer 3

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.