Array Swap

Question

For example, I have this array:

int a[] = new int[]{3,4,6,2,1}; 

I need a list of all permutations, so if so, {3,2,1,4,6} , the others should not be the same. I know that if the length of the array is n, that is, n! possible combinations. How can I write this algorithm?

Update: thanks, but I need a pseudo-code algorithm, for example:

 for(int i=0;i<a.length;i++){ // code here } 

Just an algorithm. Yes, the API functions are good, but that doesn't help me much.

Answer 1

If you use C ++, you can use std::next_permutation from the <algorithm> header file:

 int a[] = {3,4,6,2,1}; int size = sizeof(a)/sizeof(a[0]); std::sort(a, a+size); do { // print a elements } while(std::next_permutation(a, a+size)); 

Answer 2

Here's how you can print all permutations in 10 lines of code:

 public class Permute{ static void permute(java.util.List<Integer> arr, int k){ for(int i = k; i < arr.size(); i++){ java.util.Collections.swap(arr, i, k); permute(arr, k+1); java.util.Collections.swap(arr, k, i); } if (k == arr.size() -1){ System.out.println(java.util.Arrays.toString(arr.toArray())); } } public static void main(String[] args){ Permute.permute(java.util.Arrays.asList(3,4,6,2,1), 0); } } 

You take the first element of the array (k = 0) and exchange it with any element (i) of the array. Then you recursively apply the permutation in the array, starting with the second element. This way you get all permutations starting from the i-th element. The tricky part is that after the recursive call, you must swap the ith element back to the first element, otherwise you could get duplicate values ​​in the first place. Changing it back, we restore the order of the elements (basically you return back).

Iterators and extension for the case of duplicate values

The disadvantage of the previous algorithm is that it is recursive and does not play well with iterators. Another problem is that if you allow repeating elements at your input, then this will not work as it is.

For example, when you enter [3,3,4,4], all possible permutations (without repetitions) are

 [3, 3, 4, 4] [3, 4, 3, 4] [3, 4, 4, 3] [4, 3, 3, 4] [4, 3, 4, 3] [4, 4, 3, 3] 

(if you simply apply the permute function from above, you will get [3,3,4,4] four times, and this is not what you naturally want to see in this case, but the number of such permutations is 4! / (2! * 2!) = 6)

You can change the algorithm described above to handle this case, but it will not look beautiful. Fortunately, there is a better algorithm (I found it here ) that handles duplicate values ​​and is not recursive.

First of all, we note that the permutation of an array of any objects can be reduced to permutations of integers by listing them in any order.

To get permutations of an integer array, you start with an array sorted in ascending order. You are the “goal” - to make it descend. In order to generate the next permutation, you try to find the first index from below, where the sequence does not go down, and improves the value in this index, while the order of switching the rest of the tail from descending to ascending in this case.

Here is the core of the algorithm:

 //ind is an array of integers for(int tail = ind.length - 1;tail > 0;tail--){ if (ind[tail - 1] < ind[tail]){//still increasing //find last element which does not exceed ind[tail-1] int s = ind.length - 1; while(ind[tail-1] >= ind[s]) s--; swap(ind, tail-1, s); //reverse order of elements in the tail for(int i = tail, j = ind.length - 1; i < j; i++, j--){ swap(ind, i, j); } break; } } 

Here is the complete iterator code. The constructor takes an array of objects and maps them to an array of integers using a HashMap .

 import java.lang.reflect.Array; import java.util.*; class Permutations<E> implements Iterator<E[]>{ private E[] arr; private int[] ind; private boolean has_next; public E[] output;//next() returns this array, make it public Permutations(E[] arr){ this.arr = arr.clone(); ind = new int[arr.length]; //convert an array of any elements into array of integers - first occurrence is used to enumerate Map<E, Integer> hm = new HashMap<E, Integer>(); for(int i = 0; i < arr.length; i++){ Integer n = hm.get(arr[i]); if (n == null){ hm.put(arr[i], i); n = i; } ind[i] = n.intValue(); } Arrays.sort(ind);//start with ascending sequence of integers //output = new E[arr.length]; <-- cannot do in Java with generics, so use reflection output = (E[]) Array.newInstance(arr.getClass().getComponentType(), arr.length); has_next = true; } public boolean hasNext() { return has_next; } /** * Computes next permutations. Same array instance is returned every time! * @return */ public E[] next() { if (!has_next) throw new NoSuchElementException(); for(int i = 0; i < ind.length; i++){ output[i] = arr[ind[i]]; } //get next permutation has_next = false; for(int tail = ind.length - 1;tail > 0;tail--){ if (ind[tail - 1] < ind[tail]){//still increasing //find last element which does not exceed ind[tail-1] int s = ind.length - 1; while(ind[tail-1] >= ind[s]) s--; swap(ind, tail-1, s); //reverse order of elements in the tail for(int i = tail, j = ind.length - 1; i < j; i++, j--){ swap(ind, i, j); } has_next = true; break; } } return output; } private void swap(int[] arr, int i, int j){ int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public void remove() { } } 

Usage / Test:

  TCMath.Permutations<Integer> perm = new TCMath.Permutations<Integer>(new Integer[]{3,3,4,4,4,5,5}); int count = 0; while(perm.hasNext()){ System.out.println(Arrays.toString(perm.next())); count++; } System.out.println("total: " + count); 

Prints all permutations 7!/(2!*3!*2!)=210 .

Answer 3

Here is the implementation of Permutation in Java:

Permutation - Java

You must check it out!

Edit: the code inserted below to protect against death-death:

 // Permute.java -- A class generating all permutations import java.util.Iterator; import java.util.NoSuchElementException; import java.lang.reflect.Array; public class Permute implements Iterator { private final int size; private final Object [] elements; // copy of original 0 .. size-1 private final Object ar; // array for output, 0 .. size-1 private final int [] permutation; // perm of nums 1..size, perm[0]=0 private boolean next = true; // int[], double[] array won't work :-( public Permute (Object [] e) { size = e.length; elements = new Object [size]; // not suitable for primitives System.arraycopy (e, 0, elements, 0, size); ar = Array.newInstance (e.getClass().getComponentType(), size); System.arraycopy (e, 0, ar, 0, size); permutation = new int [size+1]; for (int i=0; i<size+1; i++) { permutation [i]=i; } } private void formNextPermutation () { for (int i=0; i<size; i++) { // i+1 because perm[0] always = 0 // perm[]-1 because the numbers 1..size are being permuted Array.set (ar, i, elements[permutation[i+1]-1]); } } public boolean hasNext() { return next; } public void remove() throws UnsupportedOperationException { throw new UnsupportedOperationException(); } private void swap (final int i, final int j) { final int x = permutation[i]; permutation[i] = permutation [j]; permutation[j] = x; } // does not throw NoSuchElement; it wraps around! public Object next() throws NoSuchElementException { formNextPermutation (); // copy original elements int i = size-1; while (permutation[i]>permutation[i+1]) i--; if (i==0) { next = false; for (int j=0; j<size+1; j++) { permutation [j]=j; } return ar; } int j = size; while (permutation[i]>permutation[j]) j--; swap (i,j); int r = size; int s = i+1; while (r>s) { swap(r,s); r--; s++; } return ar; } public String toString () { final int n = Array.getLength(ar); final StringBuffer sb = new StringBuffer ("["); for (int j=0; j<n; j++) { sb.append (Array.get(ar,j).toString()); if (j<n-1) sb.append (","); } sb.append("]"); return new String (sb); } public static void main (String [] args) { for (Iterator i = new Permute(args); i.hasNext(); ) { final String [] a = (String []) i.next(); System.out.println (i); } } } 

Answer 4

This is a 2-permutation for an iterated list

 import java.util.Iterator; import java.util.LinkedList; import java.util.List; /* all permutations of two objects * * for ABC: AB AC BA BC CA CB * * */ public class ListPermutation<T> implements Iterator { int index = 0; int current = 0; List<T> list; public ListPermutation(List<T> e) { list = e; } public boolean hasNext() { return !(index == list.size() - 1 && current == list.size() - 1); } public List<T> next() { if(current == index) { current++; } if (current == list.size()) { current = 0; index++; } List<T> output = new LinkedList<T>(); output.add(list.get(index)); output.add(list.get(current)); current++; return output; } public void remove() { } } 

Answer 5

There are total permutations of n! for a given size of the array n . Here is the code written in Java using DFS.

 public List<List<Integer>> permute(int[] nums) { List<List<Integer>> results = new ArrayList<List<Integer>>(); if (nums == null || nums.length == 0) { return results; } List<Integer> result = new ArrayList<>(); dfs(nums, results, result); return results; } public void dfs(int[] nums, List<List<Integer>> results, List<Integer> result) { if (nums.length == result.size()) { List<Integer> temp = new ArrayList<>(result); results.add(temp); } for (int i=0; i<nums.length; i++) { if (!result.contains(nums[i])) { result.add(nums[i]); dfs(nums, results, result); result.remove(result.size() - 1); } } } 

For the input array [3,2,1,4,6] there are only 5! = 120 possible permutations:

 [[3,4,6,2,1],[3,4,6,1,2],[3,4,2,6,1],[3,4,2,1,6],[3,4,1,6,2],[3,4,1,2,6],[3,6,4,2,1],[3,6,4,1,2],[3,6,2,4,1],[3,6,2,1,4],[3,6,1,4,2],[3,6,1,2,4],[3,2,4,6,1],[3,2,4,1,6],[3,2,6,4,1],[3,2,6,1,4],[3,2,1,4,6],[3,2,1,6,4],[3,1,4,6,2],[3,1,4,2,6],[3,1,6,4,2],[3,1,6,2,4],[3,1,2,4,6],[3,1,2,6,4],[4,3,6,2,1],[4,3,6,1,2],[4,3,2,6,1],[4,3,2,1,6],[4,3,1,6,2],[4,3,1,2,6],[4,6,3,2,1],[4,6,3,1,2],[4,6,2,3,1],[4,6,2,1,3],[4,6,1,3,2],[4,6,1,2,3],[4,2,3,6,1],[4,2,3,1,6],[4,2,6,3,1],[4,2,6,1,3],[4,2,1,3,6],[4,2,1,6,3],[4,1,3,6,2],[4,1,3,2,6],[4,1,6,3,2],[4,1,6,2,3],[4,1,2,3,6],[4,1,2,6,3],[6,3,4,2,1],[6,3,4,1,2],[6,3,2,4,1],[6,3,2,1,4],[6,3,1,4,2],[6,3,1,2,4],[6,4,3,2,1],[6,4,3,1,2],[6,4,2,3,1],[6,4,2,1,3],[6,4,1,3,2],[6,4,1,2,3],[6,2,3,4,1],[6,2,3,1,4],[6,2,4,3,1],[6,2,4,1,3],[6,2,1,3,4],[6,2,1,4,3],[6,1,3,4,2],[6,1,3,2,4],[6,1,4,3,2],[6,1,4,2,3],[6,1,2,3,4],[6,1,2,4,3],[2,3,4,6,1],[2,3,4,1,6],[2,3,6,4,1],[2,3,6,1,4],[2,3,1,4,6],[2,3,1,6,4],[2,4,3,6,1],[2,4,3,1,6],[2,4,6,3,1],[2,4,6,1,3],[2,4,1,3,6],[2,4,1,6,3],[2,6,3,4,1],[2,6,3,1,4],[2,6,4,3,1],[2,6,4,1,3],[2,6,1,3,4],[2,6,1,4,3],[2,1,3,4,6],[2,1,3,6,4],[2,1,4,3,6],[2,1,4,6,3],[2,1,6,3,4],[2,1,6,4,3],[1,3,4,6,2],[1,3,4,2,6],[1,3,6,4,2],[1,3,6,2,4],[1,3,2,4,6],[1,3,2,6,4],[1,4,3,6,2],[1,4,3,2,6],[1,4,6,3,2],[1,4,6,2,3],[1,4,2,3,6],[1,4,2,6,3],[1,6,3,4,2],[1,6,3,2,4],[1,6,4,3,2],[1,6,4,2,3],[1,6,2,3,4],[1,6,2,4,3],[1,2,3,4,6],[1,2,3,6,4],[1,2,4,3,6],[1,2,4,6,3],[1,2,6,3,4],[1,2,6,4,3]] 

Hope this helps.

Answer 6

Example with a primitive array:

 public static void permute(int[] intArray, int start) { for(int i = start; i < intArray.length; i++){ int temp = intArray[start]; intArray[start] = intArray[i]; intArray[i] = temp; permute(intArray, start + 1); intArray[i] = intArray[start]; intArray[start] = temp; } if (start == intArray.length - 1) { System.out.println(java.util.Arrays.toString(intArray)); } } public static void main(String[] args){ int intArr[] = {1, 2, 3}; permute(intArr, 0); } 

Answer 7

A visual representation of a recursive 3-piece solution: http://www.docdroid.net/ea0s/generatepermutations.pdf.html

Breakdown:

• For an array of two elements, there are two permutations:
  • Source array and
  • Two items replaced
• For an array of three elements, there are six permutations:
  • Rearrange the bottom two elements, then
  • Change 1st and 2nd position and rearrangement of the bottom two elements
  • Exchange of 1st and 3rd elements and rearrangement of the lower two elements.
  • In fact, each of the elements gets its chance in the first slot

Answer 8

Simple Java implementation, see C ++ std::next_permutation :

 public static void main(String[] args){ int[] list = {1,2,3,4,5}; List<List<Integer>> output = new Main().permute(list); for(List result: output){ System.out.println(result); } } public List<List<Integer>> permute(int[] nums) { List<List<Integer>> list = new ArrayList<List<Integer>>(); int size = factorial(nums.length); // add the original one to the list List<Integer> seq = new ArrayList<Integer>(); for(int a:nums){ seq.add(a); } list.add(seq); // generate the next and next permutation and add them to list for(int i = 0;i < size - 1;i++){ seq = new ArrayList<Integer>(); nextPermutation(nums); for(int a:nums){ seq.add(a); } list.add(seq); } return list; } int factorial(int n){ return (n==1)?1:n*factorial(n-1); } void nextPermutation(int[] nums){ int i = nums.length -1; // start from the end while(i > 0 && nums[i-1] >= nums[i]){ i--; } if(i==0){ reverse(nums,0,nums.length -1 ); }else{ // found the first one not in order int j = i; // found just bigger one while(j < nums.length && nums[j] > nums[i-1]){ j++; } //swap(nums[i-1],nums[j-1]); int tmp = nums[i-1]; nums[i-1] = nums[j-1]; nums[j-1] = tmp; reverse(nums,i,nums.length-1); } } // reverse the sequence void reverse(int[] arr,int start, int end){ int tmp; for(int i = 0; i <= (end - start)/2; i++ ){ tmp = arr[start + i]; arr[start + i] = arr[end - i]; arr[end - i ] = tmp; } } 

Answer 9

Do it like this ...

 import java.util.ArrayList; import java.util.Arrays; public class rohit { public static void main(String[] args) { ArrayList<Integer> a=new ArrayList<Integer>(); ArrayList<Integer> b=new ArrayList<Integer>(); b.add(1); b.add(2); b.add(3); permu(a,b); } public static void permu(ArrayList<Integer> prefix,ArrayList<Integer> value) { if(value.size()==0) { System.out.println(prefix); } else { for(int i=0;i<value.size();i++) { ArrayList<Integer> a=new ArrayList<Integer>(); a.addAll(prefix); a.add(value.get(i)); ArrayList<Integer> b=new ArrayList<Integer>(); b.addAll(value.subList(0, i)); b.addAll(value.subList(i+1, value.size())); permu(a,b); } } } } 

Answer 10

Implementation through recursion (dynamic programming), in Java, with a test case ( TestNG ).

---

The code

PrintPermutation.java

 import java.util.Arrays; /** * Print permutation of n elements. * * @author eric * @date Oct 13, 2018 12:28:10 PM */ public class PrintPermutation { /** * Print permutation of array elements. * * @param arr * @return count of permutation, */ public static int permutation(int arr[]) { return permutation(arr, 0); } /** * Print permutation of part of array elements. * * @param arr * @param n * start index in array, * @return count of permutation, */ private static int permutation(int arr[], int n) { int counter = 0; for (int i = n; i < arr.length; i++) { swapArrEle(arr, i, n); counter += permutation(arr, n + 1); swapArrEle(arr, n, i); } if (n == arr.length - 1) { counter++; System.out.println(Arrays.toString(arr)); } return counter; } /** * swap 2 elements in array, * * @param arr * @param i * @param k */ private static void swapArrEle(int arr[], int i, int k) { int tmp = arr[i]; arr[i] = arr[k]; arr[k] = tmp; } } 

PrintPermutationTest.java (test case via TestNG)

 import org.testng.Assert; import org.testng.annotations.Test; /** * PrintPermutation test. * * @author eric * @date Oct 14, 2018 3:02:23 AM */ public class PrintPermutationTest { @Test public void test() { int arr[] = new int[] { 0, 1, 2, 3 }; Assert.assertEquals(PrintPermutation.permutation(arr), 24); int arrSingle[] = new int[] { 0 }; Assert.assertEquals(PrintPermutation.permutation(arrSingle), 1); int arrEmpty[] = new int[] {}; Assert.assertEquals(PrintPermutation.permutation(arrEmpty), 0); } } 

Answer 11

According to the wiki https://en.wikipedia.org/wiki/Heap%27s_algorithm

The heap algorithm generates all possible permutations of n objects. It was first proposed by BR Heap in 1963. The algorithm minimizes movement: it generates each permutation from the previous one by replacing one pair of elements; the remaining n - 2 elements are not broken. In a survey of permutation generation algorithms conducted in 1977, Robert Sedgwick concluded that at that time it was the most efficient algorithm for generating permutations using a computer.

Therefore, if we want to do this recursively, the Sudo code is given below.

 procedure generate(n : integer, A : array of any): if n = 1 then output(A) else for i := 0; i < n - 1; i += 1 do generate(n - 1, A) if n is even then swap(A[i], A[n-1]) else swap(A[0], A[n-1]) end if end for generate(n - 1, A) end if 

Java code:

 public static void printAllPermutations( int n, int[] elements, char delimiter) { if (n == 1) { printArray(elements, delimiter); } else { for (int i = 0; i < n - 1; i++) { printAllPermutations(n - 1, elements, delimiter); if (n % 2 == 0) { swap(elements, i, n - 1); } else { swap(elements, 0, n - 1); } } printAllPermutations(n - 1, elements, delimiter); } } private static void printArray(int[] input, char delimiter) { int i = 0; for (; i < input.length; i++) { System.out.print(input[i]); } System.out.print(delimiter); } private static void swap(int[] input, int a, int b) { int tmp = input[a]; input[a] = input[b]; input[b] = tmp; } public static void main(String[] args) { int[] input = new int[]{0,1,2,3}; printAllPermutations(input.length, input, ','); }