]> git.ipfire.org Git - thirdparty/FORT-validator.git/commit
Generate all permutations of the list with equal probability
authorJob Snijders <job@sobornost.net>
Tue, 25 Jun 2024 05:21:39 +0000 (05:21 +0000)
committerJob Snijders <job@sobornost.net>
Tue, 25 Jun 2024 05:21:39 +0000 (05:21 +0000)
commit7b72fe8a2bddc5134c821bbe58ef35e50a22cf1e
treea767e2ec414d5b746f16be82d180bfa829e11097
parent7088ea4bf9d8ec0ff6230c89bd25dc63fe393ecb
Generate all permutations of the list with equal probability

@botovq was kind enough to point out that although my earlier
implementation produced random-ish ordering, it strictly speaking
wasn't Fisher-Yates.

We need to ensure `j` is a random number between `i` and `list.count`
see the second example in the 'Modern Algorithm'
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
src/object/manifest.c