Java 数组的排列

Permutation of array

提问by dato datuashvili

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 nthen there are n!possible combinations. How can this algorithm be written?

我需要所有排列的列表，如果一个是这样的{3,2,1,4,6}，其他的一定不一样。我知道如果数组的长度是n那么就有n！可能的组合。这个算法怎么写？

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.

只是算法。是的，API 函数很好，但对我帮助不大。

采纳答案by reko_t

If you're using C++, you can use std::next_permutationfrom the <algorithm>header file:

如果您使用的是 C++，则可以std::next_permutation从头<algorithm>文件中使用：

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

回答by Mr.Expert

Here is an implementation of the Permutation in Java:

这是 Java 中 Permutation 的一个实现：

Permutation - Java

排列 - 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);
      }
   }
}

回答by amirouche

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

这是包含在迭代器中的列表的 2 排列

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

}

回答by Yevgen Yampolskiy

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

以下是如何在 10 行代码中打印所有排列：

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

您取数组的第一个元素 (k=0) 并将其与数组的任何元素 (i) 交换。然后从第二个元素开始对数组递归应用置换。通过这种方式，您可以获得从第 i 个元素开始的所有排列。棘手的部分是，在递归调用之后，您必须将第 i 个元素与第一个元素交换回来，否则您可能会在第一个位置获得重复的值。通过将它交换回来，我们恢复了元素的顺序（基本上你做回溯）。

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, 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 permutefunction 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)

（如果你简单地permute从上面应用函数，你会得到四次 [3,3,4,4]，这不是你在这种情况下自然想要看到的；而且这种排列的数量是 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.

这是迭代器的完整代码。构造函数接受一个对象数组，并使用 将它们映射到一个整数数组中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!)=210permutations.

打印出所有7!/(2!*3!*2!)=210排列。

回答by zc22

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

3 项递归解决方案的可视化表示：http: //www.docdroid.net/ea0s/generatepermutations.pdf.html

Breakdown:

分解：

1. For a two-item array, there are two permutations:
   • The original array, and
   • The two elements swapped
2. 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

1. 对于二项数组，有两种排列：
   • 原始数组，和
   • 两个元素交换
2. 对于三项数组，有六种排列：
   • 底部两个元素的排列，然后
   • 交换第 1 项和第 2 项，以及底部两个元素的排列
   • 交换第 1 项和第 3 项，以及底部两个元素的排列。
   • 本质上，每个项目都有机会在第一个插槽

回答by Void

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

n!给定数组 size有总排列n。这是使用 DFS 用 Ja​​va 编写的代码。

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,2,1,4,6]，一共有 5 个！= 120 种可能的排列，它们是：

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

希望这可以帮助。

回答by artificerpi

A simple java implementation, refer to c++ std::next_permutation:

一个简单的java实现，参考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;
    }
}

回答by Brian

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

回答by Abhishek Sahay

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

}

回答by Eric Wang

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

通过递归（动态编程）实现，在Java 中，使用测试用例 ( TestNG)。

---

---

Code

代码

PrintPermutation.java

打印排列.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)

PrintPermutationTest.java （测试用例通过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);
    }
}