Permutations
You are encouraged to solve this task according to the task description, using any language you may know.
Write a program which generates the all permutations of n different objects. (Practically numerals!)
(c.f. Find the missing permutation )
D
<lang d>import std.stdio: writeln;
T[][] permutations(T)(T[] items) {
T[][] result;
void perms(T[] s, T[] prefix=[]) {
if (s.length)
foreach (i, c; s)
perms(s[0 .. i] ~ s[i+1 .. $], prefix ~ c);
else
result ~= prefix;
}
perms(items); return result;
}
void main() {
foreach (p; permutations([1, 2, 3]))
writeln(p);
}</lang> Output:
[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]
Fortran
<lang fortran>program permutations
implicit none integer, parameter :: value_min = 1 integer, parameter :: value_max = 3 integer, parameter :: position_min = value_min integer, parameter :: position_max = value_max integer, dimension (position_min : position_max) :: permutation
call generate (position_min)
contains
recursive subroutine generate (position)
implicit none integer, intent (in) :: position integer :: value
if (position > position_max) then
write (*, *) permutation
else
do value = value_min, value_max
if (.not. any (permutation (: position - 1) == value)) then
permutation (position) = value
call generate (position + 1)
end if
end do
end if
end subroutine generate
end program permutations</lang> Output: <lang> 1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1</lang>
Haskell
<lang haskell>import Data.List (permutations)
main = mapM_ print (permutations [1,2,3])</lang>
J
<lang j>perms=: A.&i.~ !</lang>
Example use:
<lang j> perms 2 0 1 1 0
({~ perms@#)&.;: 'some random text'
some random text some text random random some text random text some text some random text random some</lang>
Java
Using the code of Michael Gilleland. <lang java>public class PermutationGenerator {
private int[] array; private int firstNum; private boolean firstReady = false;
public PermutationGenerator(int n, int firstNum_) {
if (n < 1) {
throw new IllegalArgumentException("The n must be min. 1");
}
firstNum = firstNum_;
array = new int[n];
reset();
}
public void reset() {
for (int i = 0; i < array.length; i++) {
array[i] = i + firstNum;
}
firstReady = false;
}
public boolean hasMore() {
boolean end = firstReady;
for (int i = 1; i < array.length; i++) {
end = end && array[i] < array[i-1];
}
return !end;
}
public int[] getNext() {
if (!firstReady) {
firstReady = true;
return array;
}
int temp;
int j = array.length - 2;
int k = array.length - 1;
// Find largest index j with a[j] < a[j+1]
for (;array[j] > array[j+1]; j--);
// Find index k such that a[k] is smallest integer
// greater than a[j] to the right of a[j]
for (;array[j] > array[k]; k--);
// Interchange a[j] and a[k]
temp = array[k];
array[k] = array[j];
array[j] = temp;
// Put tail end of permutation after jth position in increasing order
int r = array.length - 1;
int s = j + 1;
while (r > s) {
temp = array[s];
array[s++] = array[r];
array[r--] = temp;
}
return array; } // getNext()
// For testing of the PermutationGenerator class
public static void main(String[] args) {
PermutationGenerator pg = new PermutationGenerator(3, 1);
while (pg.hasMore()) {
int[] temp = pg.getNext();
for (int i = 0; i < temp.length; i++) {
System.out.print(temp[i] + " ");
}
System.out.println();
}
}
} // class</lang>
If I tested the program for n=3 with beginning 1, I got this output:
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
optimized
Following needs: Utils.java
<lang java> public class Permutations { public static void main(String[] args) { Utils<Integer> u = new Utils<Integer>(); System.out.println(u.Permutations(u.mRange(1, 3))); } } </lang>
output:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Logtalk
<lang logtalk>:- object(list).
:- public(permutation/2).
permutation(List, Permutation) :-
same_length(List, Permutation),
permutation2(List, Permutation).
permutation2([], []).
permutation2(List, [Head| Tail]) :-
select(Head, List, Remaining),
permutation2(Remaining, Tail).
same_length([], []).
same_length([_| Tail1], [_| Tail2]) :-
same_length(Tail1, Tail2).
select(Head, [Head| Tail], Tail).
select(Head, [Head2| Tail], [Head2| Tail2]) :-
select(Head, Tail, Tail2).
- - end_object.</lang>
Usage example: <lang logtalk>| ?- forall(list::permutation([1, 2, 3], Permutation), (write(Permutation), nl)).
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] yes</lang>
PicoLisp
<lang PicoLisp>(load "@lib/simul.l")
(permute (1 2 3))</lang> Output:
-> ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))
Prolog
Works with SWI-Prolog and library clpfd, <lang Prolog>:- use_module(library(clpfd)).
permut_clpfd(L, N) :-
length(L, N), L ins 1..N, all_different(L), label(L).</lang>
Example of output : <lang Prolog>?- permut_clpfd(L, 3), writeln(L), fail. [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] false. </lang>A declarative way of fetching permutations : <lang Prolog>% permut_Prolog(P, L) % P is a permutation of L
permut_Prolog([], []). permut_Prolog([H | T], NL) :- select(H, NL, NL1), permut_Prolog(T, NL1).</lang> Example of output : <lang Prolog> ?- permut_Prolog(P, [ab, cd, ef]), writeln(P), fail. [ab,cd,ef] [ab,ef,cd] [cd,ab,ef] [cd,ef,ab] [ef,ab,cd] [ef,cd,ab] false. </lang>
Python
<lang python>import itertools for values in itertools.permutations([1,2,3]):
print values
</lang>
Output:
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
Tcl
<lang tcl>package require struct::list
- Make the sequence of digits to be permuted
set n [lindex $argv 0] for {set i 1} {$i <= $n} {incr i} {lappend sequence $i}
- Iterate over the permutations, printing as we go
struct::list foreachperm p $sequence {
puts $p
}</lang>
Testing with tclsh listPerms.tcl 3 produces this output:
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1