Till when we are going to get the editorial of BSHUFFLE?

Please share the editorial of BSHUFFLE or its link if its already posted as I didn’t find anything with “BSHUFFLE” on forum :slight_smile:

You should be able to satisfy yourself that any permutation is possible; just swap the appropriate element into each place in turn (or “swap an element with itself” if appropriate, i.e. leave in place). So there are no “missing” permutations to worry about.

As an investigation exercise, you can brute-force the answers for BSHUFFLE up to 8 fairly easily - generate all possible swaps, sort by frequency and report a few lowest-frequency and highest-frequent results. If you find this difficult, try for lower numbers and then try to fix any slow parts. Getting beyond about 9 in this way gets slow, though, even with some shortcuts. But at that point you should see the pattern for the other answers.

For example, it’s reasonably feasible to get permutation counts for 7 and 8 elements:


((7, 1, 2, 3, 4, 5, 6), 64)
((6, 7, 2, 3, 4, 5, 1), 69)
((7, 1, 2, 4, 3, 5, 6), 76)
...
((2, 1, 4, 5, 6, 7, 3), 504)
((2, 3, 4, 1, 6, 7, 5), 543)
((2, 3, 1, 5, 6, 7, 4), 543)

((8, 1, 2, 3, 4, 5, 6, 7), 128)
((7, 8, 2, 3, 4, 5, 6, 1), 134)
((8, 1, 2, 4, 5, 3, 6, 7), 152)
...
((2, 3, 4, 5, 1, 7, 8, 6), 1875)
((2, 3, 1, 5, 6, 7, 8, 4), 1875)
((2, 3, 4, 1, 6, 7, 8, 5), 1931)

My guess is that the top limit was brought down to 17 because proving the correctness of the continuation of the pattern of high and low probability permutations was getting difficult beyond that.

2 Likes
//