Jump to content

Wikipedia:Reference desk/Archives/Mathematics/2021 April 16

From Wikipedia, the free encyclopedia
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

[edit]

Sattolo's algorithm code giving questionable results

[edit]
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

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]