A more efficient algorithm?

[LanceGary]

The engineering mathematics program Matlab has a a function ‘Randperm’ that will produce a set of integers between two numbers with no number repeated and every number between the two digits included but in random order. This would be useful for example for sorting a pack of fifty two cards, but I was thinking about a use in a Monte Carlo simulation.
Anyway, sitting in Dentists waiting room with a CASIO graphing calculator (the fx9860 Slim, which can easily fit into a pocket) I wondered how to implement RANDPERM on the calculator. CASIO BASIC is a bit primitive (all global variables, names of variables restricted to one character, etc) but it has richer mathematical commands than most PC BASICS.

My initial attempt looked something like this:

S -> Dim List 26    ‘List 26 is an array, and S is the number of elements
For 1 -> J to S
   0 -> F     ‘F is a Flag
   Do
      RandInt#(1,S) -> T       ‘Generate a random integer between 1 and S and
                  ‘Store it in T
      1 -> F            ‘Set flag
      For 1 -> I to S
         If T = List 26   ‘If random number already in list
         Then 0 -> F      ‘Reverse flag
         IfEnd
         If F = 0
         Then Break      ‘Jump out of loop if flag set
         IfEnd
      Next
   LpWhile F =0
   T -> List 26[J]          ‘Insert rand numb into list
Next

The trouble with this routine - which works - is that it is incredibly inefficient and slow. Effectively random integers in the required range are generated and then tested against all the numbers already in the list (array). So numbers are being generated that are already there, and the list is being searched from top to bottom for each number being generated. For a RandPerm of 10 digits (say 1 to 10) this isn’t so bad, but for 52 (as in a pack of cards) this routine becomes very slow. Surely there must be a more efficient way of doing this?
I tried modifying the above routine so that a smaller range of digits could be produced as the range of numbers gets filled up, but this modification didn’t make the routine much quicker.


S -> Dim List 26    ‘List 26 is an array, and S is the number of elements
1 -> Z       ’ Z is the first number of the RandPerm
S -> L      ‘L is the largest integer in the RandPerm
For 1 -> J to S
   0 -> F     ‘F is a Flag
   Do
      RandInt#(Z,L) -> T       ‘Generate a random integer between 1 and S and
                  ‘Store it in T
      If T =Z            ‘If rand int = lower bound raise lower bound by 1
      Then Z + 1 -> Z
      IfEnd
      If T = L         ‘If rand int = higher bound lower upper bound
      Then L-1 -> L
      IfEnd
      If Z = L
      Then Z -> T
      IfEnd

      1 -> F            ‘Set flag
      For 1 -> I to S
         If T = List 26   ‘If random number already in list
         Then 0 -> F      ‘Reverse flag
         If Z = T      ‘If rand int = lower bound raise it
         Then Z + 1 -> Z
         IfEnd
         If T = L      ‘If rand int = higher bound lower it
         Then L-1 -> L
         IfEnd
         If Z = L       ‘If lower & upper bound meet
         Then Z -> T
         IfEnd
         IfEnd
         If F = 0
         Then Break      ‘Jump out of loop if flag set
         IfEnd
      Next
   LpWhile F =0
   T -> List 26[J]          ‘Insert rand numb into list
Next

Surely there must be a more efficient way of doing this?

Lance

[syzygy]

I would start with a sorted list and then swap list members randomly for as long as I want:

In Pseudocode --

Code:

no_values= 100        ' number of list members

dim x[no_values]      ' the target list

' fill array:
for i=0 to no_values
   x[i]= i
next i

' shuffle array members:
no_swaps= no_values
for i=0 to no_swaps
   y= rnd(no_values)
   z= rnd(no_values)
   swap(x[y], x[z])
next i

I'm not sure how big no_swaps needs to be to effectively destroy any order that had been in the array... that would require some experimentation. But you'd safe yourself all the conditional branches...

syzygy

[Jacob]

You should look at the Fisher-Yates Shuffle.

The basic idea is the same as syzygy, but with a slightly different approach that insures all cards are shuffled and it runs in linear time.

[LanceGary]

Thasnks guys. Much appreciated.

Lance