Permutations by swapping: Difference between revisions
→{{header|Phix}}
m (→{{header|Haskell}}: ( applied hlint, hindent )) |
|||
Line 1,475:
[2 0 1] => 1
[0 2 1] => -1</pre>
=={{header|Phix}}==
Ad-hoc recursive solution, not (knowingly) based on any given algorithm, but instead on achieving the desired pattern.<br>
Only once finished did I properly grasp that odd/even permutation idea, and that it is very nearly the same algorithm.<br>
Only difference is my version directly calculates where to insert p, without using the parity (which I added in last).
<lang Phix>function spermutations(integer p, integer i)
-- generate the i'th permutation of [1..p]:
-- first obtain the appropriate permutation of [1..p-1],
-- then insert p/move it down k(=0..p-1) places from the end.
integer k = mod(i-1,2*p)
if k>=p then k=2*p-1-k end if
sequence res
integer parity
if p>1 then
{res,parity} = spermutations(p-1,floor((i-1)/p)+1)
res = res[1..length(res)-k]&p&res[length(res)-k+1..$]
else
res = {1}
end if
return {res,iff(and_bits(i,1)?1:-1)}
end function
for p=1 to 4 do
printf(1,"==%d==\n",p)
for i=1 to factorial(p) do
?{i,spermutations(p,i)}
end for
end for</lang>
{{out}}
<pre>
"started"
==1==
{1,{{1},1}}
==2==
{1,{{1,2},1}}
{2,{{2,1},-1}}
==3==
{1,{{1,2,3},1}}
{2,{{1,3,2},-1}}
{3,{{3,1,2},1}}
{4,{{3,2,1},-1}}
{5,{{2,3,1},1}}
{6,{{2,1,3},-1}}
==4==
{1,{{1,2,3,4},1}}
{2,{{1,2,4,3},-1}}
{3,{{1,4,2,3},1}}
{4,{{4,1,2,3},-1}}
{5,{{4,1,3,2},1}}
{6,{{1,4,3,2},-1}}
{7,{{1,3,4,2},1}}
{8,{{1,3,2,4},-1}}
{9,{{3,1,2,4},1}}
{10,{{3,1,4,2},-1}}
{11,{{3,4,1,2},1}}
{12,{{4,3,1,2},-1}}
{13,{{4,3,2,1},1}}
{14,{{3,4,2,1},-1}}
{15,{{3,2,4,1},1}}
{16,{{3,2,1,4},-1}}
{17,{{2,3,1,4},1}}
{18,{{2,3,4,1},-1}}
{19,{{2,4,3,1},1}}
{20,{{4,2,3,1},-1}}
{21,{{4,2,1,3},1}}
{22,{{2,4,1,3},-1}}
{23,{{2,1,4,3},1}}
{24,{{2,1,3,4},-1}}
</pre>
=={{header|PicoLisp}}==
| |||