Permutations with repetitions: Difference between revisions
→{{header|Phix}}
(→Applescript lazy evaluation: pruned a redundant function, edited a sub-title) |
|||
Line 1,515:
//"old" compiler-version
//real 0m3.465s /fpc/2.6.4/ppc386 "%f" -al -Xs -XX -O3</pre>
=={{header|Phix}}==
The task is equivalent to simply counting in base=length(set), from 1 to power(base,n).<br>
Asking for the 0th permutation just returns the total number of permutations (ie "").<br>
Results can be generated in any order, hence early termination is quite simply a non-issue.
<lang Phix>function permrep(sequence set, integer n, idx=0)
integer base = length(set),
nperm = power(base,n)
if idx=0 then
-- return the number of permutations
return nperm
end if
-- return the idx'th [1-based] permutation
if idx<1 or idx>nperm then ?9/0 end if
idx -= 1 -- make it 0-based
sequence res = ""
for i=1 to n do
res = prepend(res,set[mod(idx,base)+1])
idx = floor(idx/base)
end for
if idx!=0 then ?9/0 end if -- sanity check
return res
end function</lang>
Some slightly excessive testing:
<lang Phix>procedure show_all(sequence set, integer n)
integer l = permrep(set,n)
sequence s = repeat(0,l)
for i=1 to l do
s[i] = permrep(set,n,i)
end for
?s
end procedure
show_all("123",1)
show_all("123",2)
show_all("123",3)
show_all("456",3)
show_all({1,2,3},3)
show_all({"bat","fox","cow"},2)
sequence s = {}
for i=31 to 36 do
s = append(s,permrep("XYZ",4,i))
end for
?s
integer l = permrep("ACKR",5)
for i=1 to l do
if permrep("ACKR",5,i)="CRACK" then -- 455
printf(1,"Permutation %d of %d: CRACK\n",{i,l})
exit
end if
end for
--The 590th (one-based) permrep is KCARC, ie reverse(CRACK), matching the 589 result of 0-based idx solutions
printf(1,"reverse(permrep(\"ACKR\",5,589+1):%s\n",{reverse(permrep("ACKR",5,590))})</lang>
{{out}}
<pre>
{"1","2","3"}
{"11","12","13","21","22","23","31","32","33"}
{"111","112","113","121","122","123","131","132","133","211","212","213","221","222","223","231","232","233","311","312","313","321","322","323","331","332","333"}
{"444","445","446","454","455","456","464","465","466","544","545","546","554","555","556","564","565","566","644","645","646","654","655","656","664","665","666"}
{{1,1,1},{1,1,2},{1,1,3},{1,2,1},{1,2,2},{1,2,3},{1,3,1},{1,3,2},{1,3,3},{2,1,1},{2,1,2},{2,1,3},{2,2,1},{2,2,2},{2,2,3},{2,3,1},{2,3,2},{2,3,3},{3,1,1},{3,1,2},{3,1,3},{3,2,1},{3,2,2},{3,2,3},{3,3,1},{3,3,2},{3,3,3}}
{{"bat","bat"},{"bat","fox"},{"bat","cow"},{"fox","bat"},{"fox","fox"},{"fox","cow"},{"cow","bat"},{"cow","fox"},{"cow","cow"}}
{"YXYX","YXYY","YXYZ","YXZX","YXZY","YXZZ"}
Permutation 455 of 1024: CRACK
reverse(permrep("ACKR",5,589+1):CRACK
</pre>
=={{header|PHP}}==
| |||