给定一个对象数组,当数组中的值可能重复时,我需要尽可能高效地找到给定数组的所有不同子集,这些子集包括所有值。
例如:如果数组是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相同。
这里的示例使用的是it,但实际上我必须使用对象。
这应该是尽可能高效的。最好的方法是只计算正确的(不重复的)多集,而不检查是否已经出现了多集,因为创建多集的方式将会消除它。
我知道如何使用二进制表示法创建所有子集。我使用它,结合递归,来计算所有的多集。这可以完美地工作,除了在值重复时不能工作。以下是我到目前为止所做的:
(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();
}
}
}提前感谢!
发布于 2018-10-06 07:17:40
这就是“幂集合”问题,超过了通常的两个集合(通常包含在一个子集中或排除在子集之外,因此幂集合有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]]https://stackoverflow.com/questions/52673738
复制相似问题