Anonymous user
Permutations/Rank of a permutation: Difference between revisions
Permutations/Rank of a permutation (view source)
Revision as of 14:12, 27 October 2012
, 11 years ago→{{header|Haskell}}
(→{{header|J}}: stretch task) |
|||
Line 48:
# [http://stackoverflow.com/a/1506337/10562 Another answer] on Stack Overflow to a different question that explains its algorithm in detail.
=={{header|Haskell}}==
Without the random part.
<lang haskell>fact n = foldr (*) 1 [1..n]
-- always assume elements are unique
rankPerm [] _ = []
rankPerm list n = c:rankPerm (a++b) r where
(q,r) = n `divMod` fact (length list - 1)
(a,c:b) = splitAt q list
permRank [] = 0
permRank (x:xs) = length(filter (<x) xs) * fact (length xs) + permRank xs
main = mapM_ f [0..23] where
f n = print (n, p, permRank p) where
p = rankPerm [0..3] n</lang>
{{out}}
from rank to permutation back to rank:
<pre>
(0,[0,1,2,3],0)
(1,[0,1,3,2],1)
(2,[0,2,1,3],2)
(3,[0,2,3,1],3)
(4,[0,3,1,2],4)
(5,[0,3,2,1],5)
(6,[1,0,2,3],6)
(7,[1,0,3,2],7)
(8,[1,2,0,3],8)
(9,[1,2,3,0],9)
(10,[1,3,0,2],10)
(11,[1,3,2,0],11)
(12,[2,0,1,3],12)
(13,[2,0,3,1],13)
(14,[2,1,0,3],14)
(15,[2,1,3,0],15)
(16,[2,3,0,1],16)
(17,[2,3,1,0],17)
(18,[3,0,1,2],18)
(19,[3,0,2,1],19)
(20,[3,1,0,2],20)
(21,[3,1,2,0],21)
(22,[3,2,0,1],22)
(23,[3,2,1,0],23)
</pre>
=={{header|J}}==
The J primitive <code>A.</code> provides an effective solution to this task. Generating 4 random permutations of 144 items takes about 6 milliseconds so solving the Stack Overflow question should be readily acheivable.
| |||