TrueShuffle

[phact]

I hit a problem with Shuffle this weekend. It only shuffles half the "deck".

I wrote a patch and some tests here #60

[phact]

In the test I run two runs for each function (Shuffle and TrueShuffle):
one:
cycles = 100, max = 10, seed/bank = 1
two:
cycles = 100, max = 10, seed/bank = 2

Shuffle:

18:01:37,485 |-INFO in ch.qos.logback.classic.joran.JoranConfigurator@3e58a80e - Registering current configuration as safe fallback point
one: [1, 10, 2, 7, 3, 9, 4, 8, 5, 6, 1, 10, 2, 7, 3, 9, 4, 8, 5, 6, 1, 10, 2, 7, 3, 9, 4, 8, 5, 6, 1, 10, 2, 7, 3, 9, 4, 8, 5, 6, 1, 10, 2, 7, 3, 9, 4, 8, 5, 6, 1, 10, 2, 7, 3, 9, 4, 8, 5, 6, 1, 10, 2, 7, 3, 9, 4, 8, 5, 6, 1, 10, 2, 7, 3, 9, 4, 8, 5, 6, 1, 10, 2, 7, 3, 9, 4, 8, 5, 6, 1, 10, 2, 7, 3, 9, 4, 8, 5, 6]
two: [1, 8, 2, 6, 3, 10, 4, 7, 5, 9, 1, 8, 2, 6, 3, 10, 4, 7, 5, 9, 1, 8, 2, 6, 3, 10, 4, 7, 5, 9, 1, 8, 2, 6, 3, 10, 4, 7, 5, 9, 1, 8, 2, 6, 3, 10, 4, 7, 5, 9, 1, 8, 2, 6, 3, 10, 4, 7, 5, 9, 1, 8, 2, 6, 3, 10, 4, 7, 5, 9, 1, 8, 2, 6, 3, 10, 4, 7, 5, 9, 1, 8, 2, 6, 3, 10, 4, 7, 5, 9, 1, 8, 2, 6, 3, 10, 4, 7, 5, 9]
50.0 percent of the cards matched

TrueShuffle:

one: [5, 1, 2, 6, 7, 8, 9, 4, 3, 10, 5, 1, 2, 6, 7, 8, 9, 4, 3, 10, 5, 1, 2, 6, 7, 8, 9, 4, 3, 10, 5, 1, 2, 6, 7, 8, 9, 4, 3, 10, 5, 1, 2, 6, 7, 8, 9, 4, 3, 10, 5, 1, 2, 6, 7, 8, 9, 4, 3, 10, 5, 1, 2, 6, 7, 8, 9, 4, 3, 10, 5, 1, 2, 6, 7, 8, 9, 4, 3, 10, 5, 1, 2, 6, 7, 8, 9, 4, 3, 10, 5, 1, 2, 6, 7, 8, 9, 4, 3, 10]
two: [1, 3, 10, 9, 8, 7, 6, 2, 5, 4, 1, 3, 10, 9, 8, 7, 6, 2, 5, 4, 1, 3, 10, 9, 8, 7, 6, 2, 5, 4, 1, 3, 10, 9, 8, 7, 6, 2, 5, 4, 1, 3, 10, 9, 8, 7, 6, 2, 5, 4, 1, 3, 10, 9, 8, 7, 6, 2, 5, 4, 1, 3, 10, 9, 8, 7, 6, 2, 5, 4, 1, 3, 10, 9, 8, 7, 6, 2, 5, 4, 1, 3, 10, 9, 8, 7, 6, 2, 5, 4, 1, 3, 10, 9, 8, 7, 6, 2, 5, 4]
0.0 percent of the cards matched
Disconnected from the target VM, address: '127.0.0.1:33187', transport: 'socket'

[phact]

Notice that for Shuffle(), every other value is always the same regarless of the seed.

[jshook]

Have you tried the higher valued seeds? I was hoping we could find a way to increase the apparent randomness of shuffled values, but hadn't found a good way to to it yet. It looks like you are using half of a LCG to get the desired effect. It will probably work for most cases, but there will be cases I suspect in which the original behavior comes back. There are other artifacts in the examples, like "10, 9, 8, 7, 6".

I'm happy to add this to the toolbox. I'd like for us to test and document the behavior of the various shuffle algorithms with some set of randomness measurements before claiming victory with any one.
Also, I think that the functionality of these to methods differs only mildly in that it is simply a left shift by one bit. The tests and added documentation are quite valuable.

It seems that we should be able to rank the banks for each LFSR configuration in order of some apparent randomness. If we could do some testing and find that ranking, then we can extend the embedded galois register database to include the most apparent randomness first.

One nice effect of the LFSR configurations being slightly related (with overlapping bit masks in many cases as you traverse through the configurations) is that you can get shuffling orders which have some degree of functional (in the value mapping sense) overlap. This can make for some degree of union or disjunction depending on the relationship. The connectedness of the resulting value maps has not been studied much by us. This is also an interesting topic for users when constructing sets of related values. Using the shuffle as a seed for set relationships could be very powerful and very efficient if we just knew what the degree of overlap was ahead of time.

Would you be willing to extend the testing in a subsequent commit to provide us some insight to these things?