Brtdku

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.

There aren't 2^n possible combinations. There are n! permutations. Plus, I don't understand the question. Are you simply trying to exclude a single permutation, {3,2,1,4,6}? — May 27 '10 at 10:34
Could other language tags be added to this? Since this is an algorithm, it would be good to have multiple implementations in various languages. — Mar 1 '16 at 15:07

Walter 27.4k1475154 · Accepted Answer · 2018-02-24 10:18:54Z

20

If you're using 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's elements

} while(std::next_permutation(a, a+size));

edited Feb 24 '18 at 10:18

Walter

27.4k1475154

answered May 27 '10 at 10:39

reko_t

44.1k87770

add a comment |

Hengameh 571510 · Accepted Answer · 2015-08-17 01:46:35Z

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.

Great Answer. Can you please explain why it's 4!/(2!2!)=6 and not 4!/(2!)=12 — Jul 7 '13 at 22:06
First of all, I know that answer is 6 (from my [3,3,4,4] example). To derive the formula, think about [3,3,4,4] as two blue and two red balls. The question is how many ways to position balls (balls of the same color are the same). If you somehow position your balls, then interchanging of the blue balls (2! ways of doing that) or two red balls (2! ways of doing that) does not change anything. Now, we have 4! ways to place 4 balls, but permuting blue balls (2! ways) or red balls (2! ways) does not change positioning of the balls. So you get 4!/(2!*2!) as final answer — Jul 10 '13 at 1:16
Time complexity of first algorithm is O(n*n!), is that right? — Aug 17 '15 at 1:59
this is the fastest permutation algorithm i've tried. good job — Apr 17 '16 at 2:06

Thor84no 4,64712247 · Accepted Answer · 2012-07-31 07:57:13Z

Here is an implementation of the Permutation in Java:

Permutation - Java

You should have a check on it!

Edit: code pasted below to protect against link-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);

      }

   }

}

+1 please add the relevant code to your post though, in case the link ever goes down — May 27 '10 at 20:30

amiroucheamirouche 3,77363170 · Accepted Answer · 2012-09-29 01:06:58Z

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() {

    }



}

MC Emperor 8,258125488 · Accepted Answer · 2016-12-28 16:11:45Z

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.

BrianBrian 21.1k116778 · Accepted Answer · 2017-08-06 10:56:23Z

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);

}

zc22zc22 13618 · Accepted Answer · 2014-07-04 05:27:51Z

Visual representation of the 3-item recursive solution:
http://www.docdroid.net/ea0s/generatepermutations.pdf.html

Breakdown:

For a two-item array, there are two permutations:
- The original array, and
- The two elements swapped

For a three-item array, there are six permutations:
- The permutations of the bottom two elements, then
- Swap 1st and 2nd items, and the permutations of the bottom two element
- Swap 1st and 3rd items, and the permutations of the bottom two elements.
- Essentially, each of the items gets its chance at the first slot

Community♦ 11 · Accepted Answer · 2017-05-23 10:31:12Z

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;

    }

}

Ryan 1,80321428 · Accepted Answer · 2018-08-16 19:30:17Z

Do 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);

            }

        }

    }



}

Eric WangEric Wang 8,273567103 · Accepted Answer · 2018-10-13 19:25:36Z

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);

    }

}

score 0 · Accepted Answer · 2019-01-20 06:59:28Z

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

Heap's algorithm generates all possible permutations of n objects. It was first proposed by B. R. Heap in 1963. The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other n−2 elements are not disturbed. In a 1977 review of permutation-generating algorithms, Robert Sedgewick concluded that it was at that time the most effective algorithm for generating permutations by computer.

So if we want to do it in recursive manner, Sudo code is bellow.

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, ',');

}

Walter 27.4k1475154 · Accepted Answer · 2018-02-24 10:18:54Z

20

If you're using 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's elements

} while(std::next_permutation(a, a+size));

edited Feb 24 '18 at 10:18

Walter

27.4k1475154

answered May 27 '10 at 10:39

reko_t

44.1k87770

add a comment |

Hengameh 571510 · Accepted Answer · 2015-08-17 01:46:35Z

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.

Great Answer. Can you please explain why it's 4!/(2!2!)=6 and not 4!/(2!)=12 — Jul 7 '13 at 22:06
First of all, I know that answer is 6 (from my [3,3,4,4] example). To derive the formula, think about [3,3,4,4] as two blue and two red balls. The question is how many ways to position balls (balls of the same color are the same). If you somehow position your balls, then interchanging of the blue balls (2! ways of doing that) or two red balls (2! ways of doing that) does not change anything. Now, we have 4! ways to place 4 balls, but permuting blue balls (2! ways) or red balls (2! ways) does not change positioning of the balls. So you get 4!/(2!*2!) as final answer — Jul 10 '13 at 1:16
Time complexity of first algorithm is O(n*n!), is that right? — Aug 17 '15 at 1:59
this is the fastest permutation algorithm i've tried. good job — Apr 17 '16 at 2:06

Thor84no 4,64712247 · Accepted Answer · 2012-07-31 07:57:13Z

Here is an implementation of the Permutation in Java:

Permutation - Java

You should have a check on it!

Edit: code pasted below to protect against link-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);

      }

   }

}

+1 please add the relevant code to your post though, in case the link ever goes down — May 27 '10 at 20:30

amiroucheamirouche 3,77363170 · Accepted Answer · 2012-09-29 01:06:58Z

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() {

    }



}

MC Emperor 8,258125488 · Accepted Answer · 2016-12-28 16:11:45Z

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.

BrianBrian 21.1k116778 · Accepted Answer · 2017-08-06 10:56:23Z

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);

}

zc22zc22 13618 · Accepted Answer · 2014-07-04 05:27:51Z

Visual representation of the 3-item recursive solution:
http://www.docdroid.net/ea0s/generatepermutations.pdf.html

Breakdown:

For a two-item array, there are two permutations:
- The original array, and
- The two elements swapped

For a three-item array, there are six permutations:
- The permutations of the bottom two elements, then
- Swap 1st and 2nd items, and the permutations of the bottom two element
- Swap 1st and 3rd items, and the permutations of the bottom two elements.
- Essentially, each of the items gets its chance at the first slot

Community♦ 11 · Accepted Answer · 2017-05-23 10:31:12Z

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;

    }

}

Ryan 1,80321428 · Accepted Answer · 2018-08-16 19:30:17Z

Do 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);

            }

        }

    }



}

Eric WangEric Wang 8,273567103 · Accepted Answer · 2018-10-13 19:25:36Z

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);

    }

}

score 0 · Accepted Answer · 2019-01-20 06:59:28Z

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

Heap's algorithm generates all possible permutations of n objects. It was first proposed by B. R. Heap in 1963. The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other n−2 elements are not disturbed. In a 1977 review of permutation-generating algorithms, Robert Sedgewick concluded that it was at that time the most effective algorithm for generating permutations by computer.

So if we want to do it in recursive manner, Sudo code is bellow.

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, ',');

}

搜尋此網誌

Brtdku

Permutation of array

11 Answers
11

Code

Your Answer

Post as a guest

11 Answers
11

11 Answers
11

Code

Code

Code

Code

Post as a guest

Popular posts from this blog

Liquibase includeAll doesn't find base path

How to use setInterval in EJS file?

Petrus Granier-Deferre

Permutation of array

11 Answers 11

Code

Your Answer

Sign up or log in

Post as a guest

Post as a guest

11 Answers 11

11 Answers 11

Code

Code

Code

Code

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Popular posts from this blog

Liquibase includeAll doesn't find base path

How to use setInterval in EJS file?

Petrus Granier-Deferre

11 Answers
11

11 Answers
11

11 Answers
11