Permutations: Difference between revisions
(Added PicoLisp) |
|||
Line 193: | Line 193: | ||
3 2 1 |
3 2 1 |
||
</pre> |
</pre> |
||
'''optimized''' |
|||
<lang java> |
|||
import java.util.ArrayList; |
|||
import java.util.Collections; |
|||
public class Permutations { |
|||
public static class Utils<T extends Comparable<T>> { |
|||
private void swap(ArrayList<T> data, int i, int j) { |
|||
T t = data.get(i); |
|||
data.set(i, data.get(j)); |
|||
data.set(j, t); |
|||
} |
|||
public ArrayList<Integer> mRange(int from, int to) { |
|||
ArrayList<Integer> result = new ArrayList<Integer>(); |
|||
for (int i = from; i <= to; i++) |
|||
result.add(i); |
|||
return result; |
|||
} |
|||
public boolean nextPerm(ArrayList<T> data) { |
|||
// find the swaps |
|||
int c = -1, d = data.size(); |
|||
for (int i = d - 2; i >= 0; i--) |
|||
if (data.get(i).compareTo(data.get(i + 1)) < 0) { |
|||
c = i; |
|||
break; |
|||
} |
|||
if (c < 0) |
|||
return false; |
|||
int s = c + 1; |
|||
for (int j = c + 2; j < d; j++) |
|||
if (data.get(j).compareTo(data.get(s)) < 0 && // |
|||
data.get(j).compareTo(data.get(c)) > 0) |
|||
s = j; |
|||
// do the swaps |
|||
swap(data, c, s); |
|||
while (--d > ++c) |
|||
swap(data, c, d); |
|||
return true; |
|||
} |
|||
@SuppressWarnings("unchecked") |
|||
public ArrayList<ArrayList<T>> Permutations(ArrayList<T> d) { |
|||
ArrayList<ArrayList<T>> result = new ArrayList<ArrayList<T>>(); |
|||
Collections.sort(d); |
|||
do { |
|||
result.add((ArrayList<T>) d.clone()); |
|||
} while (this.nextPerm(d)); |
|||
return result; |
|||
} |
|||
} |
|||
public static void main(String[] args) { |
|||
Utils<Integer> u = new Utils<Integer>(); |
|||
System.out.println(u.Permutations(u.mRange(1, 3))); |
|||
} |
|||
}</lang> |
|||
output: |
|||
<pre>[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]</pre> |
|||
=={{header|Logtalk}}== |
=={{header|Logtalk}}== |
Revision as of 10:33, 27 October 2010
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 <lang java> import java.util.ArrayList; import java.util.Collections;
public class Permutations {
public static class Utils<T extends Comparable<T>> { private void swap(ArrayList<T> data, int i, int j) { T t = data.get(i); data.set(i, data.get(j)); data.set(j, t); }
public ArrayList<Integer> mRange(int from, int to) { ArrayList<Integer> result = new ArrayList<Integer>(); for (int i = from; i <= to; i++) result.add(i); return result; }
public boolean nextPerm(ArrayList<T> data) { // find the swaps int c = -1, d = data.size(); for (int i = d - 2; i >= 0; i--) if (data.get(i).compareTo(data.get(i + 1)) < 0) { c = i; break; }
if (c < 0) return false;
int s = c + 1; for (int j = c + 2; j < d; j++) if (data.get(j).compareTo(data.get(s)) < 0 && // data.get(j).compareTo(data.get(c)) > 0) s = j;
// do the swaps swap(data, c, s); while (--d > ++c) swap(data, c, d);
return true; }
@SuppressWarnings("unchecked") public ArrayList<ArrayList<T>> Permutations(ArrayList<T> d) { ArrayList<ArrayList<T>> result = new ArrayList<ArrayList<T>>(); Collections.sort(d); do { result.add((ArrayList<T>) d.clone()); } while (this.nextPerm(d)); return result; } }
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