查找集合中所有分区的时间复杂度 [英] Time Complexity of finding all partitions of a set

问题描述

我们知道这个问题是np-完全的，因此，找不到多项式算法.同样，我们知道集合中所有分区的数量等于响铃的数量.我看到很少有算法可以生成集合的所有分区，但是找不到解决该问题的时间复杂度.

We know that this problem is np-complete, hence, no polynomial algorithm can be found for it. Also, we know that number of all partitions of a set is equal to the bell's number. I see there are few algorithms to generate all partitions of a set but couldn't find what is the time complexity to solve this problem.

例如，此python代码以递归方式生成集合的所有分区.该算法的时间复杂度是多少?能否以更好的时间复杂度解决此问题?

For example, this python code generates all partitions of a set recursively. What is the time complexity of this algorithm? Could this problem be solved with better time complexity?

def partition(collection):
    global counter
    if len(collection) == 1:
        yield [collection]
        return
    first = collection[0]
    for smaller in partition(collection[1:]):
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[first] + subset] + smaller[n + 1:]
        yield [[first]] + smaller

推荐答案

首先，请注意，此问题不是 NP -完整的. NP 是一类决策问题，但不是.通常，区别是无用的语义，但是在这种情况下，没有明显的大致等效的决策问题.此外，对于要在 NP 中出现的问题，答案必须是可在多项式时间内验证的，并且对于 NP -困难，必须为该问题提供O(1)的预言 NP 中的其他问题需要在多项式时间内解决.都不是这种情况.

First off, note that this problem is not NP-complete. NP is a class of decision problems, which this problem is not. Often the distinction is useless semantics, but in this case there is no clear roughly equivalent decision problem. Furthermore, for a problem to be in NP the answer has to be verifiable in polynomial time, and to be NP-hard an O(1) oracle for the problem must allow other problems in NP to be solved in polynomial time. Neither of these is the case.

话虽如此，您正确地说一组大小为 n 的分区的数量等于第n个Bell编号.现在，由于您的代码不需要搜索分区，因此它给出了分区每一步"，因此按与Bell数成比例的时间运行.从技术上讲，还有一个多项式项，因为较大的分区需要更长的时间才能生成，但是该项将占主导地位.

That having been said, you rightly say that the number of partitions of a set of size n is equal to the n'th Bell number. Now, because your code requires no search for partitions, it gives a partition "every step", and thus runs in time proportional to the Bell number. Technically there is also a polynomial term as larger partitions take longer to generate, but this term will be dominated.

那么，贝尔数字的大数字是什么?事实证明，这个问题很难回答.维基百科提到了贝尔数字的一些上限，其中一个在2010年发现((0.792n/ln(n + 1))^ n)，但似乎没有严格的证明.

What, then, is the big-o for the Bell numbers? This question turns out to be somewhat difficult to answer. Wikipedia mentions some upper bounds for Bell numbers, one of them found in 2010 ((0.792n / ln(n+1))^n), but there does not appear to be a tight bound proven.

这篇关于查找集合中所有分区的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！