Mathematics desk
< March 20	<< Feb \| March \| Apr >>	March 22 >

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)[reply]

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)[reply]

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)[reply]

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