算法找到共同的子集 [英] Algorithm to find common subsets

问题描述

我的 N 的集数的取值<子>我 的数字，每一个不同的尺寸。让我们的 M ₁ 的 M ₂ 的，... M <子> N 的是各组的大小（ M <子>我 = | S <子>我 | 的），和 M 的是最大的集合的大小。我必须找到至少有两个数字在他们共同的子集。例如：

I have N number of sets S_i of Numbers, each of a different size. Let m₁, m₂, ... m_n be the sizes of respective sets (m_i = | S_i |), and M be the size of the largest set. I have to find common subsets that have at least two numbers in them. Example:

Set  Items
1    10,80,22
2    72, 10, 80, 26,50
3    80,
4    10, 22
5    22, 72, 10, 80, 26,50

那么结果就会像

So the result will be like that

Items                Found in sets
10, 22               1, 4
10, 80               1, 2, 5
10, 80, 22           1, 5
10, 72, 80, 26, 50   2, 5

那么如何实现自动化这个问题，什么是各自的解决方案预期的复杂性？我需要它是尽可能快。

So how to automate this problem and what is the expected complexity for respective solution? I need it to be as fast as possible.

推荐答案

由于原来的问题要求作出讨论，以最快的速度，这是它的可短。

Since the original question asks to make a discussion as fast as possible, here's how it can be made short.

首先，讨论输出是否是指数来输入。假设你有2个元素，和N组。假设每个元素属于每个组;这将需要N行作为输入。那么，有多少行应打印？

First, discuss whether the output is exponential to your input. Assume you have 2 elements, and N sets. Assume that each element belongs to each set; it will require N lines as your input. Then, how many lines should you print?

我觉得你要打印2 ^N -N-1线路，像这样的：

I think that you're going to print 2^N-N-1 lines, like these:

1,2     1,2
1,2     1,3
.....
1,2     1,N
1,2     2,1
.....
1,2     1,2,3
.....
1,2     1,2,3,...N

既然你要花费O（2 ^N ）打印时间，你可以随便选的建议，在此页上计算这个信息you've被捕获指数反正。

Since you're going to spend O(2^N) time printing, you could pick any of the suggestions on this page to calculate this information—you've been caught by an exponent anyway.

这个说法会让你的讨论非常快。

This argument would make your discussion very fast.

这篇关于算法找到共同的子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！