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