Class PermutationGenerator


  • public class PermutationGenerator
    extends java.lang.Object
    The PermutationGenerator Java class systematically generates permutations. It relies on the fact that any set with n elements can be placed in one-to-one correspondence with the set {1, 2, 3, ..., n}. The algorithm is described by Kenneth H. Rosen, Discrete Mathematics and Its Applications, 2nd edition (NY: McGraw-Hill, 1991), pp. 282-284.

    The class is very easy to use. Suppose that you wish to generate all permutations of the strings "a", "b", "c", and "d". Put them into an array. Keep calling the permutation generator's () method until there are no more permutations left. The () method returns an array of integers, which tell you the order in which to arrange your original array of strings. Here is a snippet of code which illustrates how to use the PermutationGenerator class.

     int[] indices;
     String[] elements = {"a", "b", "c", "d"};
     PermutationGenerator x = new PermutationGenerator (elements.length);
     StringBuffer permutation;
     while (x.hasMore ()) {
     permutation = new StringBuffer ();
     indices = x.getNext ();
     for (int i = 0; i < indices.length; i++) {
     permutation.append (elements[indices[i]]);
     }
     System.out.println (permutation.toString ());
     }
     
    One caveat. Don't use this class on large sets. Recall that the number of permutations of a set containing n elements is n factorial, which is a very large number even when n is as small as 20. 20! is 2,432,902,008,176,640,000.

    NOTE: This class was taken from the internet, as posted by Michael Gilleland on this website. The code was posted with the following comment: "The source code is free for you to use in whatever way you wish."

    Author:
    Michael Gilleland, Merriam Park Software (http://www.merriampark.com/index.htm)
    • Constructor Detail

      • PermutationGenerator

        public PermutationGenerator​(int n)
    • Method Detail

      • reset

        public void reset()
      • getNumLeft

        public java.math.BigInteger getNumLeft()
      • getTotal

        public java.math.BigInteger getTotal()
      • hasMore

        public boolean hasMore()
      • getNext

        public int[] getNext()