Permutation of array

Question

For example I have this array:

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

I need list of all permutations such that if one is like this, {3,2,1,4,6}, others must not be the same. I know that if the length of the array is n then there are n! possible combinations. How can this algorithm be written?

Update: thanks, but I need a pseudo code algorithm like:

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

Just algorithm. Yes, API functions are good, but it does not help me too much.

Answer 1

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

---

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 2

A simple java implementation, refer to 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 3

Example with 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 4

This a 2-permutation for a list wrapped in an iterator

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

Here is 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 first element of an array (k=0) and exchange it with any element (i) of the array. Then you recursively apply permutation on array starting with second element. This way you get all permutations starting with i-th element. The tricky part is that after recursive call you must swap i-th element with first element back, otherwise you could get repeated values at the first spot. By swapping it back we restore order of elements (basically you do backtracking).

Iterators and Extension to the case of repeated values

The drawback of previous algorithm is that it is recursive, and does not play nicely with iterators. Another issue is that if you allow repeated elements in your input, then it won't work as is.

For example, given input [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 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; and the number of such permutations is 4!/(2!*2!)=6)

It is possible to modify the above algorithm to handle this case, but it won't look nice. Luckily, there is a better algorithm (I found it here) which handles repeated values and is not recursive.

First note, that permutation of array of any objects can be reduced to permutations of integers by enumerating them in any order.

To get permutations of an integer array, you start with an array sorted in ascending order. You 'goal' is to make it descending. To generate next permutation you are trying to find the first index from the bottom where sequence fails to be descending, and improves value in that index while switching order of 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 full code of iterator. Constructor accepts an array of objects, and maps them into an array of integers using 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 out all 7!/(2!*3!*2!)=210 permutations.

Answer 6

There are n! total permutations for the given array size n. Here is 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 input array [3,2,1,4,6], there are totally 5! = 120 possible permutations which are:

[[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.