Permutations: Difference between revisions
Content added Content deleted
Line 109: | Line 109: | ||
</lang> |
</lang> |
||
Output: |
|||
<pre> |
<pre> |
||
(1, 2, 3) |
(1, 2, 3) |
Revision as of 21:41, 3 October 2010
Permutations
You are encouraged to solve this task according to the task description, using any language you may know.
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 )
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
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