Permutations/Rank of a permutation: Difference between revisions
Content added Content deleted
(→{{header|J}}: stretch task) |
|||
Line 48: | Line 48: | ||
# [http://stackoverflow.com/a/1506337/10562 Another answer] on Stack Overflow to a different question that explains its algorithm in detail. |
# [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}}== |
=={{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. |
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. |