Beaver Bar Camp


http://barcamp.org/BeaverBarCamp

I asked the attendees at the Beaver (Corvallis) BarCamp to help me find a sequence of dice faces that meet the unusual conditional probabilities suggested for the DiceRoller part.

To avoid long explanations I described the problem as one of shuffling with constraints:

  • Shuffle a deck of cards such that no two adjacent cards have the same rank. For example, no two aces in a row, no two duces, etc.

  • Except for the constraint above, make sure that all legal shuffles are equally likely.

A trivial solution would be to do a regular shuffle and then check if it meets our constrains. We could repeat the process until we are luck enough to find one that passes.

The solution that came out of our session was to insert cards from a sorted deck into a shuffled deck, one at a time, at random locations, and each time checking that the one card inserted meet our constraints. If not, we try inserting a little further in the deck and check again.

I adapted the idea to produce this perl program that generates face sequences in a dice rolling simulator. Think of this as a deck with five suits, each with six cards with rank 1 through 6.

    $_="123456"; 
    for $n (1..5) {
      for $i (1..6) {
        $r = int(rand($l=length($_)));
        s/(.{$r})(.*)/$2$1/;
        s/([^$i]{2})([^$i]{2})/$1$i$2/;
      }
    }
    print "$_\n";

This program repeatedly applies two pattern matching string substitutions to do the following.

  • Cut the shuffled deck at a random position, $r

  • Insert $i into the reassembled deck at first opportunity.

I initialize the shuffled deck with the decidedly unshuffled "123456". This surely bias my stats in some undesirable way but it sure simplifies the boundary conditions when getting the algorithm started.

I wrote the pattern for the second match to look for strings of digits that do not include $i. In my application I don't want a repeat within two cards. I say [^$i] to mean any character other than $i, and then, {2} to mean exactly two characters meeting this constraint.

This longer range duplication is hard to spot by eye. This is the perl program I used to check my results.

    s/(\d)(\d)(\1)/ ($1$2$3) /g

It uses one substitute command to look for three digits where the third digit is the same as the first (\1). Should I find one, I will put parenthesis around the unwanted sequence and set it off from the rest with spaces.


BartMassey pointed out that this algorithm is flawed in a well known way. The search for the first available space will create clusters of values. He suggested the this fix: Repeat the cut when the new card can't be placed in the first position. Don't even look at the second position.

Here is a modified program.

    $_="123456"; 
    for $n (1..5) {
      for $i (1..6) {
        do {
          $r = int(rand($l=length($_)));
          s/(.{$r})(.*)/$2$1/;
        } until s/^([^$i]{2})([^$i]{2})/$1$i$2/;
      }
    }
    print "$_\n";

We've added a ^ to our second pattern. This disables searching, which means this match could fail. We added a do-until loop around the random cut so that it will be repeated until the insertion succeeds.


Here we further analyze sample sequences by factoring each possible digit into a separate line.

Unconstrained.

    616123425324626632215333456335465464114511551224
    .1.1...............1................11..11..1...
    ....2..2..2..2...22..........................22.
    .....3...3......3....333...33...................
    ......4....4............4.....4..4.4..4........4
    ........5...........5....5...5..5......5..55....
    6.6.........6.66..........6....6..6.............

No repeats in adjacent position.

    561365324252626354152614154623543512134142614363
    ..1...............1...1.1.........1.1..1...1....
    .......2.2.2.2......2.......2......2.....2......
    ...3..3........3.............3..3....3.......3.3
    ........4........4.....4..4....4......4.4...4...
    5....5....5.....5..5.....5....5..5..............
    .6..6.......6.6......6.....6..............6...6.

No repeats in adjacent two positions.

    426531645243561235215416521325412364156324136436
    .....1........1....1..1...1....1....1.....1.....
    .2.......2.....2..2......2..2...2.......2.......
    ....3......3....3..........3.....3.....3...3..3.
    4......4..4..........4........4....4.....4...4..
    ...5....5...5....5..5...5....5.......5..........
    ..6...6......6.........6..........6...6.....6..6

Try is this version at http://codepad.org/Vtxp52bN

 

Last edited March 4, 2008
Return to WelcomeVisitors