Giudoku Official Site
Permutations and dispositions of n elements

A permutation of a set of objects is a rearrangement of those objects. For example 2341 is a permutation of 1234. It's easily demonstrated that the number of distinct permutations for a set of n objects is n!.

Task: given a set of distinct characters (the alphabet), print out all the permutations of the characters. If the characters are repeated, the behaviour may vary.

Specifically, this algorithm takes 3 arguments in input:
- The "universe" U: the set of the objects you have to permute. I used a LinkedList because all the operations are already implemented, but an array or a vector is good too.
- S: an initially void string that will be filled with the characters while the permutation is created, printed out when completed with a permutation, and then emptied when another route is tried.
- The length k of the universe (which will be the length of a complete string too).
For every character in the universe, removes it from U and appends it to S. If k==1 this is the last character I had to insert (the next call would be with an empty U), so S is printed. Otherwise, the method is called again with k-1. Of course, the character that was just used is removed so that it won't be used again: for each call, k is precisely the current size of U. Imagine that U={abcd} and S is {ab} at the beginning. The method first set S={abc} and calls itself with U={d}, then S={abd} and U={c}. When the recursion returns to this point, all the possible permutations for S={ab} has been tried. So I remove b from S and inserts it again in U (at the same position!). The next iteration will give S={ac} and everything starts again.

Of course this algorithm runs in exponential time, as you can note if you draw the recursion tree for a small k.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.*;

public class Permutations
{
  public static void main(String[] args)
  {
    try
    {
      char[] alphabet = args[0].toCharArray();
      permutations(alphabet);
    }
    catch (ArrayIndexOutOfBoundsException e)
    {
      System.out.println("You're supposed to enter the alphabet as an argument");
    }
    catch (IllegalStateException e)
    {
      System.out.println("Argument too long (max: 20 chars)");
    }
  }
  
  public static void permutations (char[] alphabet)
  {
    String s = "";
    List<Character> universe = new LinkedList<Character>();
    
    if (alphabet.length > 20)
    {
      throw new IllegalStateException();
    }
    
    for (int i = 0; i < alphabet.length; i++)
    {
      universe.add(alphabet[i]);
    }
    permutations(s, universe, universe.size());
  }
  
  public static void permutations (String S, List<Character> U, int k)
  {
    for (int i = 0; i < U.size(); i++)
    {
      char ch = U.remove(i);
      S += ch;
      
      if (k == 1)
      {
        System.out.println(S);
      }
      else
      {
        permutations(S, U, k-1);
      }
      
      U.add(i, ch);
      S = S.substring(0, S.length() - 1);
    }
  }
}
      


Given a set of N objects, a disposition is an arrangement of K objects taken from that set, where K < N. So, permutations are a special case of dispositions where K=N.
The number of dispositions is = N(N-1)...(N+K-1). But our code will generate a particular category of dispositions, those with repetition, where characters can be repeated into the sequence. So, for the set {abc} and K=2, some dispositions can be 'aa' or 'bc'. The total number of these dispositions is N^K.

The code is very similar to the previous one, except that K is not equal to the size of U and the element is not removed from the universe after being inserted in the string. At every recursion, U represents the characters that can be chosen for the current position: of course, in this case, this includes every character in the set.
Note for both codes: the conversion between the argument string and the char array is not really needed, but this code was an exercise for univesity and the prototype of the methods was given in this way. I was too lazy to change it :).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import java.util.*;

public class Dispositions
{
  public static void main(String[] args)
  {
    try
    {
      char[] alphabet = args[0].toCharArray();
      int k = Integer.parseInt(args[1]);
      dispositions(alphabet, k);
    }
    catch (ArrayIndexOutOfBoundsException e)
    {
      System.out.println("Usage: java Dispositions <alphabet> <K>");
    }
    catch (NumberFormatException e)
    {
      System.out.println("The second argument must be an integer");
    }
    catch (IllegalStateException e)
    {
      System.out.println("K is not valid or the alphabet is greater than 5");
    }
  }
  
  public static void dispositions(char[] a, int k)
  {
    List<Character> l = new LinkedList<Character>();
    
    if (a.length > 5 || k <= 0 || k > a.length)
    {
      throw new IllegalStateException();
    }
    
    for (int i = 0; i < a.length; i++)
    {
      l.add(a[i]);
    }
    
    String s = "";
    dispositions(l, s, k);
  }
  
  public static void dispositions(List<Character> U, String S, int k)
  {
    for (int i = 0; i < U.size(); i++)
    {
      char ch = U.get(i);
      S += ch;
      
      if (k == 1)
      {
        System.out.println(S);
      }
      else
      {
        dispositions(U, S, k-1);
      }
      
      S = S.substring(0, S.length() - 1);
    }
  }
}