Permutations/Rank of a permutation: Difference between revisions
→{{header|Phix}}
Thundergnat (talk | contribs) m (→{{header|Ring}}: Remove vanity tags) |
|||
Line 1,215:
[11 10 0 3 4 6 7 9 8 5 1 2]
</pre>
=={{header|Phix}}==
{{trans|C}}
<lang Phix>function get_rank(sequence l)
integer r = length(l)
sequence inv = repeat(0,r)
for i=1 to r do
inv[l[i]+1] = i-1
end for
integer res = 0, mul = 1
for n=r to 2 by -1 do
integer s = l[n]
l[inv[n]+1] = s
inv[s+1] = inv[n]
res += s*mul
mul *= n
end for
return res
end function
puts(1,"rank->permute->rank:\n")
sequence l = tagset(2,0)
for n=1 to factorial(length(l)) do
sequence p = permute(n,l)
?{n-1,p,get_rank(p)}
end for
puts(1,"4 random individual samples of 12 items:\n")
l = tagset(11,0)
for i=1 to 4 do
?permute(rand(factorial(12)),l)
end for</lang>
{{out}}
<pre>
rank->permute->rank:
{0,{1,2,0},0}
{1,{2,0,1},1}
{2,{1,0,2},2}
{3,{2,1,0},3}
{4,{0,2,1},4}
{5,{0,1,2},5}
4 random individual samples of 12 items:
{4,5,12,1,11,8,0,9,2,6,7,3,10}
{7,2,3,0,5,1,4,6,9,11,8,10,12}
{10,8,12,1,9,3,2,4,11,0,5,6,7}
{3,4,0,8,12,11,7,1,6,5,9,10,2}
</pre>
It is worth noting that while the permute builtin can scramble anything, the get_rank function above<br>
(like most others on this page) can only handle permulations of the integers 0 to n-1. Of course as<br>
long as you permute indexes rather than the data itself, that does not matter.
It proved utterly trivial to convert that to bigatoms, however also utterly pointless, since it would take<br>
over 5 days to generate a million perms, whereas a million shuffle(l) (of 144 items) takes just 20 seconds,<br>
and in fact storing the integer(string) ranks takes twice as much space as 144 small integers anyway.
=={{header|Python}}==
| |||