首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >创建非独异值的子集的所有多集,在Java中

问创建非独异值的子集的所有多集,在Java中
EN

Stack Overflow用户
提问于 2018-10-06 05:57:15
回答 1查看 293关注 0票数 2

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

例如:如果数组是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]}

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

这里的示例使用的是it,但实际上我必须使用对象。

这应该是尽可能高效的。最好的方法是只计算正确的(不重复的)多集,而不检查是否已经出现了多集,因为创建多集的方式将会消除它。

我知道如何使用二进制表示法创建所有子集。我使用它,结合递归,来计算所有的多集。这可以完美地工作,除了在值重复时不能工作。以下是我到目前为止所做的:

(a是给定数字的数组,curr是正在构建的当前多集,b是所有多集的最终集。)

代码语言:javascript
复制
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();
        }
    }
}

提前感谢!

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2018-10-06 07:17:40

这就是“幂集合”问题,超过了通常的两个集合(通常包含在一个子集中或排除在子集之外,因此幂集合有2^N个元素)。对于您的问题版本,任何元素都可以是最多N个子集中的任何一个子集的一部分,因此问题的规模为N^N (很快就会变大)。

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

代码语言:javascript
复制
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 (但无论如何,您都不希望运行该大小的问题,因为它将永远花费代码的运行时间)。

输出:

代码语言:javascript
复制
[[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 },输出为:

代码语言:javascript
复制
[[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]]
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/52673738

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档