Make And Show All Permutations of An Integer Array

Question

I am currently making a Permutation class for java. One of my methods for this class, is advance(), where the computer will take the array, and then display all permutations of the array.

So, for example, if I give the array {0,1,2,3,4,5}, or the number 6, it should give me from 012345.....543210.

Here is the code I have so far:

import java.util.*;

public class Permutation extends java.lang.Object {

public static int[] permutation;
public static int[] firstPerm;
public static int[] lastPerm;
public static int length;
public static int count;

public static void main(String[] args) {
    // TODO Auto-generated method stub

}

public Permutation(int n) {
    length = n;
    permutation = new int[length];
    for (int i = 0; i < length; i++) {
        permutation[i] = i;
    }
}

public Permutation(int[] perm) {
    length = perm.length;
    permutation = new int[length];
    boolean[] t = new boolean[length];
    for (int i = 0; i < length; i++) {
        if (perm[i] < 0 || perm[i] >= length) {
            throw new IllegalArgumentException("INVALID ELEMENT");
        }
        if (t[perm[i]]) {
            throw new IllegalArgumentException("DUPLICATE VALUES");
        }
        t[perm[i]] = true;
        permutation[i] = perm[i];
    }
}

public void advance() {

}

public int getElement(int i) {
    return permutation[i];
}

public boolean isFirstPerm() {
    firstPerm = new int[permutation.length];
    for (int i = 0; i < permutation.length; i++) {
        firstPerm[i] = permutation[i];
    }
    Arrays.sort(firstPerm);
    if (Arrays.equals(firstPerm, permutation)) {
        return true;
    } else {
        return false;
    }
}

public boolean isLastPerm() {
    lastPerm = new int[firstPerm.length];
    for (int i = 0; i < firstPerm.length; i++) {
        lastPerm[i] = firstPerm[firstPerm.length - 1 - i];
    }
    if (Arrays.equals(permutation, lastPerm)) {
        return true;
    } else {
        return false;
    }
}

public static Permutation randomPermutation(int n) {
    if (n <= 0) {
        throw new IllegalArgumentException("INVALID NUMBER");
    } else {
        length = n;
        permutation = new int[length];
        for (int i = 0; i < length; i++) {
            permutation[i] = i;
        }
        Collections.shuffle(Arrays.asList(permutation));
        return new Permutation(permutation);
    }
}

public void reset() {
    Arrays.sort(permutation);
}

public boolean isValid(int[] perm) {
    boolean[] t = new boolean[length];
    for (int i = 0; i < length; i++) {
        if (perm[i] < 0 || perm[i] >= length) {
            return false;
        }
        if (t[perm[i]]) {
            return false;
        }
    }
    return true;
}

public int[] toArray() {
    return permutation;
}

public String toString() {
    StringBuffer result = new StringBuffer();
    for (int i = 0; i < permutation.length; i++) {
        result.append(permutation[i]);
    }
    String perms = result.toString();
    return perms;
}

public static long totalPermutations(int n) {
    count = 1;
    for (int i = 1; i <= n; i++) {
        count = count * i;
    }
    return count;
}

}

As you can see, the advance() method is the last thing I need to do, but I can't figure it out. Any help will be grand.

Answer 1

One of methods you can employ is:

• Fix the first element and recursively find all permutations of rest of the array.
• Then change the first elements by trying each of the remaining elements.

• Base case for recursion is when you travel the entire length to get 0 element array. Then, either print it or add it to a List which you can return at the end.

  public void advance() { 
      int[] temp = Arrays.copyOf(arr, arr.length);        
      printAll(0,temp);
  }
  
  private void printAll(int index,int[] temp) {
      if(index==n) { //base case..the end of array
       //print array temp here
      }           
      else {
          for(int i=index;i<n;i++) {//change the first element stepwise
              swap(temp,index,i);//swap to change 
              printAll(index+1, temp);//call recursively              
              swap(temp,index,i);//swap again to backtrack
          }       
      }
  }   
  
  private void swap(int[] arr, int i, int j) {
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j]  = temp;
  }  
  

Answer 2

The way your code looks right now, it sounds like you want to be able to control the permutation class externally, rather than only supporting the one operation of printing all the permutations in order.

Here's an example of how to calculate a permutation.

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {
        public static int factorial(int x) {
                int f = 1;
                while (x > 1) {
                        f = f * x;
                        x--;
                }
                return f;
        }

        public static List<Integer> permute(List<Integer> list, int iteration) {
                if (list.size() <= 1) return list;
                int fact = factorial(list.size() - 1);
                int first = iteration / fact;
                List<Integer> copy = new ArrayList<Integer>(list);
                Integer head = copy.remove(first);
                int remainder = iteration % fact;
                List<Integer> tail = permute(copy, remainder);
                tail.add(0, head);
                return tail;
        }

        public static void main(String[] args) throws IOException {
                List<Integer> list = Arrays.asList(4, 5, 6, 7);
                for (int i = 0; i < 24; i++) {
                    System.out.println(permute(list, i));
                }
        }
}

Just to elaborate, the idea behind the code is to map an integer (iteration) to a particular permutation (ordering of the list). We're treating it as a base-n representation of the permutation where each digit represents which element of the set goes in that position of the resulting permutation.

For example, if we're permuting (1, 2, 3, 4) then we know there are 4! permutations, and that "1" will be the first element in 3! of them, and it will be followed by all permutations of (2, 3, 4). Of those 3! permutations of the new set (2, 3, 4), "2" will be the first element in 2! of them, etc.

That's why we're using / and % to calculate which element goes into each position of the resulting permutation.

Answer 3

This should work, and it's pretty compact, only drawback is that it is recursive:

private static permutation(int x) {
  if (x < 1) {
    throw new IllegalArgumentException(x);
  } 
  LinkedList<Integer> numbers = new LinkedList<>();
  for (int i = 0; i < x; i++) {
    numbers.add(i);
  }
  printPermutations(numbers, new LinkedList<>());
}

private static void printPermutations(
      LinkedList<Integer> numbers, LinkedList<Integer> heads) {
  int size = numbers.size();
  for (int i = 0; i < size; i++) {
    int n = numbers.getFirst();
    numbers.removeFirst();
    heads.add(n);
    printPermutations(numbers, heads);
    numbers.add(n);
    heads.removeLast();
  }

  if (numbers.isEmpty()) {
    String sep = "";
    for (int n : heads) {
      System.out.print(sep + n);
      sep = " ";
    }
    System.out.println("");
  }
}