数组的排列

以下是在 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);
    }
}

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

迭代器和扩展到重复值的情况

以前算法的缺点是它是递归的，不能很好地与迭代器一起使用。另一个问题是，如果允许在输入中重复元素，则它将无法按原样工作。

例如，给定输入 [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]

（如果你简单地从上面应用函数，你会得到[3，3，4，4]四次，这不是你在这种情况下自然希望看到的;这样的排列的数量是4！/（2！*2！）=6）permute

可以修改上述算法来处理这种情况，但它看起来并不好看。幸运的是，有一个更好的算法（我在这里找到了它），它可以处理重复的值并且不是递归的。

首先要注意的是，任何对象的数组的排列都可以通过以任何顺序枚举它们来简化为整数的排列。

要获取整数数组的排列，请从按升序排序的数组开始。你的“目标”是让它下降。要生成下一个排列，您尝试从底部找到序列无法降序的第一个索引，并在该索引中提高该索引中的值，同时在这种情况下将尾部其余部分的顺序从降序切换到升序。

这是算法的核心：

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

这是迭代器的完整代码。构造函数接受对象数组，并使用 将它们映射到整数数组。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() {

    }
}

用法/测试：

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

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

如果您使用的是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));