java - 数组的排列

Question

例如我有这个数组:

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

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

更新:谢谢，但我需要一个伪代码算法，例如:

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

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

Answer 1

以下是如何在 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]

(如果你只是简单地应用上面的 permute 函数，你会得到四次 [3,3,4,4] ，这不是你在这种情况下自然想要看到的；并且这种排列的数量是 4!/(2!*2!)=6)

可以修改上述算法来处理这种情况，但看起来不太好。幸运的是，有一个更好的算法(我发现它 here )可以处理重复值并且不是递归的。

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

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

这里是算法的核心:

//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 排列。