Rosetta Code

Permutations: Difference between revisions

Page Discussion

Permutations (view source)

Revision as of 13:51, 18 March 2022

5,798 bytes removed ,  2 years ago
m
→‎{{header|Phix}}: use new builtin
m (→‎{{header|Phix}}: use new builtin)
Line 6,734:
 
=={{header|Phix}}==
The distribution includes builtins\permute.e, which is reproduced below. This can be used to retrieve all possible permutations, in
no particular order. The elements can be any type. It is just as fast to generate the (n!)th permutation as the first, so some applications may benefit by storing
an integer key rather than duplicating all the elements of the given set.
<!--<lang Phix>-->
<span style="color: #008080;">global</span> <span style="color: #008080;">function</span> <span style="color: #7060A8;">permute</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- return the nth permute of the given set.
-- n should be an integer in the range 1 to factorial(length(set))
--</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">)?</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">:</span><span style="color: #000000;">0</span><span style="color: #0000FF;">),</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">set</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (top level only needed)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">w</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">w</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</lang>-->
Example use:
<!--<lang Phix>(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #0080807060A8;">function</span> <span style="color: #000000;">permutesrequires</span><span style="color: #0000FF;">(</span><span style="color: #004080008000;">sequence</span> <span style="color: #000000;1.0.2">set</span><span style="color: #0000FF;">)</span>
<span style="color: #0040800000FF;">sequence?</span> <span style="color: #0000007060A8;">resshorten</span> <span style="color: #0000FF;">=(</span> <span style="color: #7060A8;">repeatpermutes</span><span style="color: #0000FF;">(</span><span style="color: #000000008000;">0"abcd"</span><span style="color: #0000FF;">),</span><span style="color: #7060A8008000;">factorial</span><span style="color: #0000FF;elements">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(,</span><span style="color: #000000;">set5</span><span style="color: #0000FF;">)))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">permute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">set</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">permutes</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"abcd"</span><span style="color: #0000FF;">)</span>
<!--</lang>-->
{{out}}
<pre>
{"bcdaabcd","dcababdc","bdacacbd","bcadacdb","cdbaadbc","cadb","dabc","cabd","bdca...","dacb","badc","bacd","cbda","cdab","dbac","cbad","dcba","acdb","adbc","acbd","dbca","adcbdcab","abdcdcba","abcd (24 elements)"}
</pre>
The elements can be any type. There is also a permute() function which accepts an integer between 1 and factorial(length(s)) and returns the permutations in lexicographical position order. It is just as fast to generate the (n!)th permutation as the first, so some applications may benefit by storing an integer key rather than duplicating all the elements of the given set.
 
=={{header|Phixmonti}}==
Petelomax
7,831

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/158835"