Wikipedia:Reference desk/Archives/Mathematics/2019 March 21

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 21

counting partial permutations

Remember Wikipedia:Reference_desk/Archives/Mathematics/2016 June 19#to index a permutation? Of course, who could forget it?

I've had a try at writing the inverse function (in Python of course), to read a permutation and infer its index number:

flawed code
def mut_to_index( mysequence ): cumul = 0 cbang = 1 countall = 0 counter = {} keys = [] for j in reversed(mysequence): if j not in keys: keys.append(j) keys.sort() counter[j] = 0 jj = keys.index(j) cumul += jj * cbang counter[j] += 1 countall += 1 cbang = (countall * cbang) // counter[j] print cbang, counter return cumul

but it's wrong; the simplest failure case is BAA, whose index is clearly 2 (after AAB, ABA) but the function returns 1 (after AAA; which is wrong in another way too, because one doesn't know if three As are available). At the moment, I see no way to proceed. —Tamfang (talk) 15:46, 21 March 2019 (UTC)

Now I think my solution will have the same structure as BenRG's code in that past item, adding rather than subtracting. —Tamfang (talk) 18:39, 21 March 2019 (UTC)

Yep, that works (in a small but nontrivial test). Can't help thinking there may be a more efficient way. —Tamfang (talk) 19:58, 21 March 2019 (UTC)

better code
def mut_to_index(group_sizes, alphabet, mysequence): group_sizes = list(group_sizes) total = count_permutations(group_sizes) result = 0 remain = len(mysequence) for x in mysequence: j = alphabet.index(x) for k in xrange(j): subtotal = total * group_sizes[k] // remain result += subtotal total = group_sizes[j] * total // remain group_sizes[j] -= 1 remain -= 1 return result