所有独特排列-堆栈溢出问题

Question

我正在尝试解决以下问题:

给定一个可能包含重复项的数字集合，返回所有可能的唯一排列。

下面是我的代码:

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> a) {
        HashMap<ArrayList<Integer>, Boolean> unique = new HashMap<>();
        ArrayList<ArrayList<Integer>> results = new ArrayList<>();
        permu(results, a, 0, unique);
        return results;
    }
    private void permu(ArrayList<ArrayList<Integer>> results, final ArrayList<Integer> a, int item, HashMap<ArrayList<Integer>, Boolean> unique) {
        for(int i = 0; i < a.size(); i++) {
            ArrayList<Integer> aClone = new ArrayList<>(a);
            // swap
            int backup = aClone.get(i);
            aClone.set(i, aClone.get(item));
            aClone.set(item, backup);
            if(!unique.containsKey(aClone)) {
                results.add(aClone);
                unique.put(aClone, true);
                permu(results, aClone, i, unique); //<--- Stack overflow error
            }
        }
    }
}

我有一个堆栈溢出错误在这个调用的递归，行(19)

Answer 1

嗯，我不喜欢破坏好的面试问题，但是这个问题想起来很有趣，所以…

这里有一个超级l337的答案，可以非常快速地生成所有唯一的排列，而不使用太多的内存或堆栈。如果你在工作面试中使用这个，面试官会让你解释它是如何工作的。如果你能做到这一点，那么你值得拥有它:)

请注意，我在字符串中排列字符，而不是在列表中排列整数，只是因为这样更容易美观地打印结果。

import java.util.Arrays;
import java.util.function.Consumer;

public class UniquePermutations
{
    static void generateUniquePermutations(String s, Consumer<String> consumer)
    {
        char[] array = s.toCharArray();
        Arrays.sort(array);
        for (;;)
        {
            consumer.accept(String.valueOf(array));
            int changePos=array.length-2;
            while (changePos>=0 && array[changePos]>=array[changePos+1])
                --changePos;
            if (changePos<0)
                break; //all done
            int swapPos=changePos+1;
            while(swapPos+1 < array.length && array[swapPos+1]>array[changePos])
                ++swapPos;
            char t = array[changePos];
            array[changePos] = array[swapPos];
            array[swapPos] = t;
            for (int i=changePos+1, j = array.length-1; i < j; ++i,--j)
            {
                t = array[i];
                array[i] = array[j];
                array[j] = t;
            }
        }
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        StringBuilder line = new StringBuilder();
        generateUniquePermutations("banana", s->{
            if (line.length() > 0)
            {
                if (line.length() + s.length() >= 75)
                {
                    System.out.println(line.toString());
                    line.setLength(0);
                }
                else
                    line.append(" ");
            }
            line.append(s);
        });
        System.out.println(line);
    }
}

输出如下:

aaabnn aaanbn aaannb aabann aabnan aabnna aanabn aananb aanban aanbna
aannab aannba abaann abanan abanna abnaan abnana abnnaa anaabn anaanb
anaban anabna ananab ananba anbaan anbana anbnaa annaab annaba annbaa
baaann baanan baanna banaan banana bannaa bnaaan bnaana bnanaa bnnaaa
naaabn naaanb naaban naabna naanab naanba nabaan nabana nabnaa nanaab
nanaba nanbaa nbaaan nbaana nbanaa nbnaaa nnaaab nnaaba nnabaa nnbaaa