Anonymous user
Permutations: Difference between revisions
Added a Modula-3 implementation
(→{{header|Haskell}}: Switched foldl to foldr (more efficient, and usually the default)) |
(Added a Modula-3 implementation) |
||
Line 4,086:
END Permute.</lang>
=={{header|Modula-3}}==
This implementation merely prints out the orbit of the list (1, 2, ..., n) under the action of <i>S<sub>n</sub></i>. It shows off Modula-3's built-in <code>Set</code> type and uses the standard <code>IntSeq</code> library module.
<lang modula2>MODULE Permutations EXPORTS Main;
IMPORT IO, IntSeq;
CONST n = 3;
TYPE Domain = SET OF [ 1.. n ];
VAR
chosen: IntSeq.T;
values := Domain { };
PROCEDURE GeneratePermutations(VAR chosen: IntSeq.T; remaining: Domain) =
(*
Recursively generates all the permutations of elements
in the union of "chosen" and "values".
Values in "chosen" have already been chosen;
values in "remaining" can still be chosen.
If "remaining" is empty, it prints the sequence and returns.
Otherwise, it picks each element in "remaining", removes it,
adds it to "chosen", recursively calls itself,
then removes the last element of "chosen" and adds it back to "remaining".
*)
BEGIN
FOR i := 1 TO n DO
(* check if each element is in "remaining" *)
IF i IN remaining THEN
(* if so, remove from "remaining" and add to "chosen" *)
remaining := remaining - Domain { i };
chosen.addhi(i);
IF remaining # Domain { } THEN
(* still something to process? do it *)
GeneratePermutations(chosen, remaining);
ELSE
(* otherwise, print what we've chosen *)
FOR j := 0 TO chosen.size() - 2 DO
IO.PutInt(chosen.get(j)); IO.Put(", ");
END;
IO.PutInt(chosen.gethi());
IO.PutChar('\n');
END;
(* add "i" back to "remaining" and remove from "chosen" *)
remaining := remaining + Domain { i };
EVAL chosen.remhi();
END;
END;
END GeneratePermutations;
BEGIN
(* initial setup *)
chosen := NEW(IntSeq.T).init(n);
FOR i := 1 TO n DO values := values + Domain { i }; END;
GeneratePermutations(chosen, values);
END Permutations.</lang>
{{out}}
For reasons of space, we show only the elements of <i>S</i><sub>3</sub>, but we have tested it with higher.
<pre>
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
</pre>
=={{header|NetRexx}}==
<lang NetRexx>/* NetRexx */
| |||