Derangement extra postage
May 21, 2020 at 11:16 PM by Dr. Drang
I left something out of last night’s post on derangements: the Python program that generated the table of values I used to search the OEIS for the sequences associated with one, two, three, etc. fixed points. It was a deliberate omission, as I thought the post was long enough as it was. Consider this post the equivalent of Numberphile’s “extra footage.”
Recall that the table looked like this (you may have to scroll left to see it all)
m
0 1 2 3 4 5 6 7 8
----------------------------------------------------------------
2 | 1 0 1
3 | 2 3 0 1
4 | 9 8 6 0 1
n 5 | 44 45 20 10 0 1
6 | 265 264 135 40 15 0 1
7 | 1854 1855 924 315 70 21 0 1
8 | 14833 14832 7420 2464 630 112 28 0 1
where is the number of cards we’re shuffling and is the number of fixed points, that is, the number of cards that are in their original position after the shuffling.
Shuffling cards is a permuting operation, and the itertools module in Python’s standard library has a permutations function that returns all the permutations of the list (or other iterable) passed to it. The program I wrote does nothing more than call that function to generate the permutations and then search through them, counting up the number of fixed points in each. It does that for .
Here it is:
python:
1: #!/usr/bin env python
2:
3: from itertools import permutations
4:
5: def countMatches(o, p):
6: count = 0
7: for i in range(len(o)):
8: if p[i] == o[i]:
9: count += 1
10: return count
11:
12: # Table header
13: print(' '*3, end='')
14: for m in range(9):
15: print(f'{m:7d}', end='')
16: print()
17: print(' '*3 + '-'*64)
18:
19: # Table body
20: for n in range(2, 9):
21: cards = [chr(i+65) for i in range(n)]
22: counts = [0]*(n+1)
23:
24: for a in permutations(cards):
25: matches = countMatches(a, cards)
26: counts[matches] += 1
27:
28: print(f'{n} |', end='')
29: for i in range(n+1):
30: print(f'{counts[i]:7d}', end='')
31: print()
The key to the script is the countMatches function in Lines 5–10. When given the original list and a permutation, it marches through each and returns the number of fixed points. I’m sure there’s a more clever way of doing this, but I wasn’t interested in spending the time to be clever. Since the program as a whole is a brute force approach to the problem, I didn’t care if there was a brute force subroutine lurking within it.
Lines 12–17 just set up the table’s header, with the values of and a row of hyphens. The rest of the program loops through all the values of to create the row labels and body of the table.
Those of you who know your ASCII will recognize that the list of cards created in Line 21 consists of n capital letters in alphabetical order, starting with A. Line 22 initializes the counts list to a bunch of zeros.
The loop in Lines 24–26 goes through all the permutations and uses the countMatches function to increment the appropriate member of counts. For each item in counts, the index is the number of fixed points, , and the value is the number of permutations with that many fixed points.
Finally, Lines 28–31 print out the row of the table associated with the current value of n.
The “m” label above the top header row and the “n” label to the left of the row labels were added by hand. It was easier than programming them in.
You’ll note that some of the printing is done with f-strings, so this will only run in Python 3.6 and above. But you could rewrite those lines to use the format method if you’re really stuck with an older version of Python.
If you ever run into a problem that requires rearranging or combining lists, keep itertools in mind.
