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

Question

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

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

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

请注意，子集中值的顺序和多重集中子集的顺序都不重要。像 {[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();
        }
    }
}

提前致谢！

Answer 1

这是 "power set" 问题，比通常的两个集合多（通常包含在子集中或从子集中排除，因此幂集有 2^N 个元素）。对于您这个问题的版本，任何元素都可以是最多 N 个子集中的任何一个的一部分，因此问题扩展为 N^N（它很快就会变大）。

给定一个包含 N 个元素的列表，要找到此 "N-way power set" 中的所有唯一分区，您需要在概念上生成以 N 为基数的所有 N 位数字，然后每个数字的值给出输入中相应元素的分区索引（这意味着通常您将得到空分区，对于所有情况，分区数等于 N 时除外）。使用这些数字索引将元素分组到共享相同索引的元素列表中，从而生成列表列表。为了检测重复项，您必须对子列表进行排序，然后对列表列表进行排序，然后将排序后的列表列表添加到集合中。您无法避免最后的重复数据删除步骤，因为您的描述允许输入中的重复元素。

package main;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class PrintPartitionings {
    /** A list of integers */
    public static class Partition extends ArrayList<Integer>
            implements Comparable<Partition> {
        // Lexicographic comparator
        @Override
        public int compareTo(Partition other) {
            for (int i = 0, ii = Math.min(this.size(),
                    other.size()); i < ii; i++) {
                int c = this.get(i).compareTo(other.get(i));
                if (c != 0) {
                    return c;
                }
            }
            return Integer.compare(this.size(), other.size());
        }
    }

    /** A list of lists of integers */
    public static class Partitioning extends ArrayList<Partition>
            implements Comparable<Partitioning> {
        public Partitioning() {
            super();
        }

        public Partitioning(int N) {
            super(N);
            // Pre-allocate sub-lists for convenience
            for (int j = 0; j < N; j++) {
                add(new Partition());
            }
        }

        // Lexicographic comparator
        @Override
        public int compareTo(Partitioning other) {
            for (int i = 0, ii = Math.min(this.size(),
                    other.size()); i < ii; i++) {
                int c = this.get(i).compareTo(other.get(i));
                if (c != 0) {
                    return c;
                }
            }
            return Integer.compare(this.size(), other.size());
        }
    }

    /** Print all unique partitionings of the passed array of integers */
    public static void printPartitionings(int[] elts) {
        int N = elts.length;
        Set<Partitioning> setOfPartitionings = new HashSet<>();
        // Generate integers in [0, N^N)
        for (long i = 0, ii = (long) Math.pow(N, N); i < ii; i++) {
            // Create empty partitioning
            Partitioning partitioning = new Partitioning(N);

            // Assign each element to a partition based on base N digit
            long digits = i;
            for (int j = 0; j < N; j++) {
                int digit = (int) (digits % N);
                digits /= N;
                partitioning.get(digit).add(elts[j]);
            }

            // Sort individual partitions, and remove empty partitions
            Partitioning partitioningSorted = new Partitioning();
            for (Partition partition : partitioning) {
                if (!partition.isEmpty()) {
                    Collections.sort(partition);
                    partitioningSorted.add(partition);
                }
            }

            // Sort the partitioning
            Collections.sort(partitioningSorted);

            // Add the result to the final set of partitionings
            setOfPartitionings.add(partitioningSorted);
        }

        // Sort lexicographically to make it easier to view the result
        List<Partitioning> setOfPartitioningsSorted = new ArrayList<>(
                setOfPartitionings);
        Collections.sort(setOfPartitioningsSorted);
        for (Partitioning partitioning : setOfPartitioningsSorted) {
            System.out.println(partitioning);
        }
    }

    public static void main(String[] args) {
        printPartitionings(new int[] { 1, 2, 1, 2 });
    }
}

实施并未特别优化——可以通过多种方式使其更快。此外，所示代码仅适用于中等规模的问题，当 N^N < Long.MAX_VALUE 时，即所示代码的 N 的最大值为 15（但您不想运行那样大的问题，因为代码运行).

需要很长时间

输出：

[[1], [1], [2], [2]]
[[1], [1], [2, 2]]
[[1], [1, 2], [2]]
[[1], [1, 2, 2]]
[[1, 1], [2], [2]]
[[1, 1], [2, 2]]
[[1, 1, 2], [2]]
[[1, 1, 2, 2]]
[[1, 2], [1, 2]]

对于输入 { 1, 2, 3, 2 } 输出是：

[[1], [2], [2], [3]]
[[1], [2], [2, 3]]
[[1], [2, 2], [3]]
[[1], [2, 2, 3]]
[[1, 2], [2], [3]]
[[1, 2], [2, 3]]
[[1, 2, 2], [3]]
[[1, 2, 2, 3]]
[[1, 2, 3], [2]]
[[1, 3], [2], [2]]
[[1, 3], [2, 2]]

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

Creating all multisets of subsets of NON DISTINCT values, in Java

java

set

subset

multiset