Print all array permutations

Question

I am working on a program, and I have a function that swaps the length array that the user enters. However, I am trying to figure out how to print this call to function N! times, which lists all the permutations in the function.

My code for the permutation function:

static void nextPerm(int[] A){ for( int i = (n-1); i > 0; i-- ){ if( A[i] < A[i+1] ){ A[i] = pivot; continue; } if( A[i] >= A[i+1] ){ reverseArray(A); return; } } for( int i = n; i > 0; i--){ if( A[i] > pivot ){ A[i] = successor; continue; } } Swap(pivot, successor); int[] B = new int[pivot+1]; reverseArray(B); return; } 

Should I write a loop in the main function that will print this n! time?

Answer 1

Creating (or printing) permutations of an array is much simpler as a combination of recursively and iteratively than purely iteratively. Of course, there are iterative ways to do this, but it is especially easy with a combination. In particular, note that, by definition, N! permutations of an array of length N - N options for the first slot, selection of N-1 for the second, etc. etc. Thus, we can split the algorithm into two steps for each index i in the array.

• Select the element in the arr[i....end] ith as the ith element of the array. Change this item with the item currently on arr[i] .
• Rearrange arr[i+1...end] recursively.

Note that this will work in O (N!), Since N subheadings will be made on the first call, each of which will do N-1 sub-elections, etc. etc. In addition, each element will be in each position, and until only swaps are executed, no element will be duplicated.

 public static void permute(int[] arr){ permuteHelper(arr, 0); } private static void permuteHelper(int[] arr, int index){ if(index >= arr.length - 1){ //If we are at the last element - nothing left to permute //System.out.println(Arrays.toString(arr)); //Print the array System.out.print("["); for(int i = 0; i < arr.length - 1; i++){ System.out.print(arr[i] + ", "); } if(arr.length > 0) System.out.print(arr[arr.length - 1]); System.out.println("]"); return; } for(int i = index; i < arr.length; i++){ //For each index in the sub array arr[index...end] //Swap the elements at indices index and i int t = arr[index]; arr[index] = arr[i]; arr[i] = t; //Recurse on the sub array arr[index+1...end] permuteHelper(arr, index+1); //Swap the elements back t = arr[index]; arr[index] = arr[i]; arr[i] = t; } } 

Example input, output:

 public static void main(String[] args) { permute(new int[]{1,2,3,4}); } [1, 2, 3, 4] [1, 2, 4, 3] [1, 3, 2, 4] [1, 3, 4, 2] [1, 4, 3, 2] [1, 4, 2, 3] [2, 1, 3, 4] [2, 1, 4, 3] [2, 3, 1, 4] [2, 3, 4, 1] [2, 4, 3, 1] [2, 4, 1, 3] [3, 2, 1, 4] [3, 2, 4, 1] [3, 1, 2, 4] [3, 1, 4, 2] [3, 4, 1, 2] [3, 4, 2, 1] [4, 2, 3, 1] [4, 2, 1, 3] [4, 3, 2, 1] [4, 3, 1, 2] [4, 1, 3, 2] [4, 1, 2, 3] 

Answer 2

I used this method most of the time. (he is given by Robert Sedgewick and Kevin Wayne.).

 public class Permutations { // print N! permutation of the characters of the string s (in order) public static void perm1(String s) { perm1("", s); } private static void perm1(String prefix, String s) { int N = s.length(); if (N == 0) System.out.println(prefix); else { for (int i = 0; i < N; i++) perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N)); } } // print N! permutation of the elements of array a (not in order) public static void perm2(String s) { int N = s.length(); char[] a = new char[N]; for (int i = 0; i < N; i++) a[i] = s.charAt(i); perm2(a, N); } private static void perm2(char[] a, int n) { if (n == 1) { System.out.println(a); return; } for (int i = 0; i < n; i++) { swap(a, i, n-1); perm2(a, n-1); swap(a, i, n-1); } } // swap the characters at indices i and j private static void swap(char[] a, int i, int j) { char c; c = a[i]; a[i] = a[j]; a[j] = c; } 

However, there is an easier way to do this. Maybe you can work on this too.

 class PermutingArray { static void permutingArray(java.util.List<Integer> arrayList, int element) { for (int i = element; i < arrayList.size(); i++) { java.util.Collections.swap(arrayList, i, element); permutingArray(arrayList, element + 1); java.util.Collections.swap(arrayList, element, i); } if (element == arrayList.size() - 1) { System.out.println(java.util.Arrays.toString(arrayList.toArray())); } } public static void main(String[] args) { PermutingArray .permutingArray(java.util.Arrays.asList(9, 8, 7, 6, 4), 0); } } 

A working example is here .. IDeone Link

Answer 3

The trick is to return a special value ( false in the code below) from nextPerm when it was the last permutation (i.e. when the array is sorted in descending order):

 import java.util.*; public class Main { public static boolean nextPerm(List<Integer> a) { int i = a.size() - 2; while (i >= 0 && a.get(i) >= a.get(i + 1)) i--; if (i < 0) return false; int j = a.size() - 1; while (a.get(i) >= a.get(j)) j--; Collections.swap(a, i, j); Collections.reverse(a.subList(i + 1, a.size())); return true; } ... 

Then you can use a loop (note that the required array must be sorted in ascending order):

  ... public static void main(String[] args) { List<Integer> a = Arrays.asList(new Integer[] {1, 2, 3, 4}); do { System.out.println(a); } while (nextPerm(a)); } } 

You can try this code here: http://ideone.com/URDFsc