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 )
C
Iterative method. Given a permutation, find the next in lexicographic order. Iterate until the last one. Here the main program shows letters and is thus limited to permutations of 26 objects. The function computing next permutation is not limited. <lang c>#include <stdio.h>
- include <stdlib.h>
/* Find next permutation in lexicographic order. Return -1 if already the last, otherwise 0. A permutation is an array[n] of value between 0 and n-1. */ int nextperm(int n, int *perm) { int i,j,k,t;
t = 0; for(i=n-2; i>=0; i--) { if(perm[i] < perm[i+1]) { t = 1; break; } }
/* last permutation if decreasing sequence */ if(!t) { return -1; }
/* swap tail decreasing to get a tail increasing */ for(j=i+1; j<n+i-j; j++) { t = perm[j]; perm[j] = perm[n+i-j]; perm[n+i-j] = t; }
/* find min acceptable value in tail */ k = n-1; for(j=n-2; j>i; j--) { if((perm[j] < perm[k]) && (perm[j] > perm[i])) { k = j; } }
/* swap with ith element (head) */ t = perm[i]; perm[i] = perm[k]; perm[k] = t;
/* sort tail, i.e. place kth to its position */
/* if after */ while((k < n-1) && (perm[k] > perm[k+1])) { t = perm[k]; perm[k] = perm[k+1]; perm[k+1] = t; k += 1; }
/* if before */ while((k > i+1) && (perm[k] < perm[k-1])) { t = perm[k]; perm[k] = perm[k-1]; perm[k-1] = t; k -= 1; }
return 0; }
int main(int argc, char **argv) { int i, n, *perm;
if(argc != 2) { printf("perm n (1 <= n <= 26\n"); return 1; } n = strtol(argv[1], NULL, 0);
perm = (int *)calloc(n, sizeof(int)); for(i=0; i<n; i++) { perm[i] = i; } do { for(i=0; i<n; i++) { printf("%c", perm[i] + 'A'); } printf("\n"); } while(!nextperm(n, perm)); free(perm); return 0; }</lang>
Sample result :
perm 3
ABC ACB BAC BCA CAB CBA
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) { System.out.println(Utils.Permutations(Utils.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>
PARI/GP
<lang>vector(n!,k,numtoperm(n,k))</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>
PureBasic
The procedure findPermutations() takes a string of characters as input and returns a list of the permutations of a given length using those characters. Even though this will only permute characters and not objects, the characters used can be treated as indexes of limited size into a list of objects that can replace the characters in the permutations. <lang PureBasic>Procedure findPermutations(List permutations.s(), elementChar.s, permSize) ;include duplicates if needed
Protected i, j, stackDepth, elementCount = Len(elementChar) - 1, working.s = Space(permSize), *working = @working
permSize - 1
Dim stack(permSize) ;holds index states
Dim elements(elementCount)
Dim elementChar.c(elementCount)
For i = 0 To elementCount
elementChar(i) = PeekC(@elementChar + i)
Next
i = 0
Repeat
While i <= elementCount
If elements(i) = 0
stack(stackDepth) = i
If stackDepth = permSize
For j = 0 To permSize
PokeC(*working + j * SizeOf(Character), elementChar(stack(j)))
Next
AddElement(permutations())
permutations() = working
Else
elements(i) = 1
stackDepth + 1
i = 0
Continue ;skip update
EndIf
EndIf
i + 1
Wend
stackDepth - 1
If stackDepth < 0
Break
EndIf
i = stack(stackDepth) + 1
elements(i - 1) = 0
ForEver
EndProcedure
If OpenConsole()
NewList a.s() findPermutations(a(), "123", 3) ForEach a() PrintN(a()) Next Print(#CRLF$ + "Press ENTER to exit"): Input() CloseConsole()
EndIf</lang> Sample output:
123 132 213 231 312 321
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