Permutations with repetitions: Difference between revisions
Content added Content deleted
(→Applescript lazy evaluation: pruned a redundant function, edited a sub-title) |
|||
Line 1,515: | Line 1,515: | ||
//"old" compiler-version |
//"old" compiler-version |
||
//real 0m3.465s /fpc/2.6.4/ppc386 "%f" -al -Xs -XX -O3</pre> |
//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}}== |
=={{header|PHP}}== |