生成一个集合的所有分区
生成一个集合的所有分区
提问于 2015-06-17 13:37:24
用于一组表单A = {1, 2, 3, ..., n}。它被称为集A的划分，这是一组尊重下列定理的k<=n元素：
( a) A的所有分区的联合是A。
A的两个分区的交集是空集(它们不能共享相同的元素)。
例如。A = {1, 2,... n}我们有分区：
{1, 2, 3}
{1, 2} {3}
{1, 3} {2}
{2, 3} {1}
{1} {2} {3}这些理论概念是在我的算法教科书中提出的(顺便说一句，本章是“回溯”一章的一部分)。我应该找到一个算法来生成给定集合的所有分区。我整天都在和这个问题作斗争，却找不到解决办法。你能解释一下这个算法是如何工作的吗？另外，你能给我一个算法的伪代码草图吗？
Stack Overflow用户
发布于 2016-08-26 11:52:37
我正在研究一种高效的算法，它根据@rici定义的关键字方法生成集合的所有分区。下面的算法是用python编写的，这样仍然可以进行优化。我就在上面。您可能知道，这个问题是NP-完全的！由于优化，可能有一些奇怪的表示法，如try/except。然而，n和k变量是通过n来定义的，集合有多少不同的元素，k是集合允许拥有的不同类的数量。信息:算法生成所有的分区，直到不同类的数量，而不仅仅是那些类！
def partitions():
global n
global k
codeword = [1 for digitIndex in range(0, n)]
while True:
print codeword
startIndex = n - 1
while startIndex >= 0:
maxValue = max(codeword[0 : startIndex])
if codeword[startIndex] > maxValue or maxValue > k or codeword[startIndex] >= k:
codeword[startIndex] = 1
startIndex -= 1
else:
codeword[startIndex] += 1
break
n = 12
k = 2
try:
partitions()
except:
pass页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/30893292
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号