Speed

[Dick Kriesel]

On Aug 22, 2014, at 1:17 PM, Beat Cornaz <B.Cornaz at gmx.net> wrote:

> So a good example would be how to make all possible  permutations of say 10 different elements (0-9). This gives 3628800 different permutations.
> The resulting permutations will be in lines I guess, but what would be the best way to do this. Using lines, items, chars or any other way as Input?
> 
> So the start would be f.i. a list with 10 lines with the ten elements, one in each line - That is what I am using now. 
> OR items "0,1,2,3,4,5,6,7,8,9" or chars "0123456789"  or another way to represent 10 elements to make it possible to run the script in minutes, not hours.

Hi, Beat.

The Wikipedia entry for "permutation" says the fastest algorithm for generating permutations is Heap's algorithm.
The entry for "Heap's algorithm" says the following is its pseudocode:

<pseudocode>
procedure generate(N : integer, data : array of any):
if N = 1 then
  output(data)
else
  for c := 1; c <= N; c += 1 do
  generate(N - 1, data)
  swap(data[if N is odd then 1 else c], data[N])	
</pseudocode>

So, here's a way in LiveCode to derive the 3,628,800 permutations of 10 things taken 10 at a time. On my 2012 iMac, it takes under two minutes.  How's that, Beat?

-- Dick

<livecode>
on mouseUp
  test
end mouseUp

command test
  local tArray, tMilliseconds, tCountForPermutation
  put 1 into tArray[ 1 ]
  put 2 into tArray[ 2 ]
  repeat with n = 3 to 10
      put n into tArray[ n ]
      put empty into tCountForPermutation
      put the milliseconds into tMilliseconds
      permute n, tArray, tCountForPermutation
      putLine n & " things produce " & ( number of elements in tCountForPermutation ) & " of " \
            & factorial( n ) & " permutations in " & ( the milliseconds - tMilliseconds ) & " milliseconds"
  end repeat
end test

command permute n, @rArray, @rCountForPermutation
  if n > 1 then
      repeat with c = 1 to n
          permute n-1, rArray, rCountForPermutation
          if n mod 2 is 1 then
              swap rArray, 1, n
          else
              swap rArray, c, n
          end if
          insertPermutation rArray, rCountForPermutation
      end repeat
  end if
end permute

command swap @rArray, pKey1, pKey2
  local t
  put rArray[ pKey1 ] into t
  put rArray[ pKey2 ] into rArray[ pKey1 ]
  put t into rArray[ pKey2 ]
end swap

command insertPermutation @pArray, @rCountForPermutation
  local tPermutation
  repeat with i = 1 to the number of elements in pArray
      put pArray[ i ] & space after tPermutation
  end repeat
  add 1 to rCountForPermutation[ char 1 to -2 of tPermutation ]
end insertPermutation

function factorial n
  if n = 1 then
      return 1
  else
      return n * factorial( n-1 )
  end if
end factorial
</livecode>