Permutations: Difference between revisions
(J) |
(Added Fortran) |
||
Line 4: | Line 4: | ||
(c.f. [[Find the missing permutation]] ) |
(c.f. [[Find the missing permutation]] ) |
||
=={{header|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> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
Revision as of 09:57, 4 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 )
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>
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
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