在 Java 中创建非 DISTINCT 值子集的所有多重集

Question

给定一个对象数组，当数组中的值可能重复时，我需要尽可能高效地找到给定数组的所有不同子集集，其中包括所有值。

例如：如果数组是1, 2, 1, 2那么我需要创建以下多重集：

1. {[1], [1], [2], [2]}

2. {[1], [1], [2, 2]}

3. {[1], [2], [1, 2]}

4. {[1], [1, 2, 2]}

5. {[1, 1], [2], [2]}

6. {[1, 1], [2, 2]}

7. {[1, 2], [1, 2]}

8. {[1, 1, 2], [2]}

9. {[1, 1, 2, 2]}

请注意，子集中值的顺序和多集内子集的顺序都不重要。多重集 like{[1, 2, 2], [1]}与 相同#4，而{[2, 1], [2], [1]}与 相同#3。

这里的例子是整数，但实际上我必须用对象来做。

这应该尽可能有效。最好只计算正确的（不重复的）多重集，不检查是否已经出现，因为创建它的方式将消除它的发生。

我知道如何使用二进制表示创建所有子集。我使用它，结合递归，来计算所有的多重集。这很完美，除非在值重复时它不起作用。这是我到目前为止所做的：

（a是给定数字的数组， curr是正在构建的当前多重集，而b是所有多重集的最终集。）

public static void makeAll(ArrayList<Integer> a, 

                           ArrayList<ArrayList<Integer>> curr,

                           ArrayList<ArrayList<ArrayList<Integer>>> b) {

    ArrayList<ArrayList<Integer>> currCopy;

    ArrayList<Integer> thisGroup, restGroup;

    int currSize = 0, ii = 0;

    if (a.size() == 0)

        b.add(new ArrayList<ArrayList<Integer>>(curr));

    else {

        for (int i = 0; i < 1 << (a.size() - 1); i++) {

            thisGroup = new ArrayList<>();

            restGroup = new ArrayList<>();

            ii = (i << 1) + 1; // the first one is always in, keeps uniquness.

            for (int j = 0; j < a.size(); j++)

                if ((ii & 1 << j) > 0)

                    thisGroup.add(a.get(j));

                else

                    restGroup.add(a.get(j));

            currSize = curr.size();

            curr.add(new ArrayList<Integer>(thisGroup));

            makeAll(restGroup, curr, b);

            curr.subList(currSize, curr.size()).clear();

        }

    }

}

提前致谢！