Mathematics desk
< April 15	<< Mar \| April \| May >>	Current desk >

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

April 16

Sattolo's algorithm code giving questionable results

When I run the Python code on Fisher–Yates_shuffle#Sattolo's_algorithm with

permutations = {}
for i in range(24000):
    list4 = list('ABCD')
    sattolo_cycle(list4)
    key = ''.join(list4)
    permutations[key] = permutations.get(key, 0) + 1
print('\n'.join(sorted([str(items) for items in permutations.items()])))

I get

('BCDA', 3895)
('BDAC', 3971)
('CADB', 4012)
('CDBA', 4153)
('DABC', 4030)
('DCAB', 3939)

I think BCDA and DABC are the same cycle, while the cycle BADC (or DCBA) is not represented. The table on the right uses the code output. Is my understanding incorrect, or is there something wrong with the code?

Thanks
cmɢʟee⎆τaʟκ 00:41, 16 April 2021 (UTC)[reply]

The notation in the article is somewhat non-standard in group theory but make sense from a computer science perspective. The permutation WXYZ refers to the map A→W, B→X, C→Y, D→Z, where A,B,C,D were the original contents of the array. In group theory the notation (WXYZ) is the permutation W→X, X→Y, Y→Z, Z→W, which is not the same thing. For example ABCD is just the identity permutation while (ABCD) is the 4-cycle A→B, B→C, C→D, D→A. It's true that (BCDA) and (DABC) are the same 4-cycle, but BCDA written in group theory notation is (ABCD) while DABC is (ADCB). It looks like, aside from this notation issue, the program worked as intended. --RDBury (talk) 02:27, 16 April 2021 (UTC)[reply]

In combinatorics this is called one-line notation of a permutation (as opposed to cycle notation). --JBL (talk) 16:54, 16 April 2021 (UTC)[reply]

Thanks, that's useful terminology. There should really be standard notation as well; I think at one point I used square brackets for the one-line notation and parentheses for cycle notation because I needed both for what I was doing, but I'm pretty sure it was something I just made up. --RDBury (talk) 19:04, 16 April 2021 (UTC)[reply]

Thank you very much. I'll update the table accordingly. cmɢʟee⎆τaʟκ 16:21, 18 April 2021 (UTC)[reply]

ABCD	BACD	CABD	DABC
ABDC	BADC	CADB	DACB
ACBD	BCAD	CBAD	DBAC
ACDB	BCDA	CBDA	DBCA
ADBC	BDAC	CDAB	DCAB
ADCB	BDCA	CDBA	DCBA
Of the 24 permutations of A, B, C and D generatable by the Fisher–Yates shuffle, the 6 in bold and red are generatable using Sattolo's algorithm – all 9 in bold are the derangements of A, B, C and D