On Aug 22, 2014, at 1:17 PM, Beat Cornaz <b.cor...@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>
_______________________________________________
use-livecode mailing list
use-livecode@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
