Permutations

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>

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

Works with: Python version 2.6

<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

Library: tcllib

<lang tcl>package require struct::list

1. Make the sequence of digits to be permuted

set n [lindex $argv 0] for {set i 1} {$i <= $n} {incr i} {lappend sequence $i}

1. 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