对于一个形如A = {1, 2, 3, ..., n}的集合。如果存在一个大小为k<=n的集合，满足以下定理，则称其为集合A的一个划分：
a) 所有划分的并集等于原集合A
b) 任意两个划分的交集为空集（它们不能拥有共同元素）。
例如，对于集合A = {1, 2,... n}，我们可以得到以下划分：
{1, 2, 3}
{1, 2} {3}
{1, 3} {2}
{2, 3} {1}
{1} {2} {3}
这些理论概念在我的算法教材中介绍（顺便说一下，这个子章节是“回溯”章节的一部分）。我需要找到一个算法来生成给定集合的所有划分。我整天都在苦苦思考这个问题，但是我找不到解决方案。你能否向我解释一下这个算法是如何工作的？同时，你能给我提供一个伪代码草图吗？
有一个重要的观察结果（在注释中），即一个包含n个元素的集合的划分可以表示为形如[p1, … pn]的整数序列，其中pi是元素i的划分号。为了使这样的序列有效，必须遵守规则：p1等于1，并且对于每个1 < j ≤ n的j，存在某个 i < j满足pj≤ pi+1。换句话说，在序列的任何前缀中，都不会跳过任何整数。
现在，有一种标准算法，可以按词典顺序列举有限制的序列，该算法包括以下步骤：
这个算法有几个关于寻找可增量元素的约定，最坏情况为O(n)，当要增加的元素通常接近序列末尾时通常为O(1)。（例如，使用此算法枚举排列是O(1)，只要您可以在O(1)中找到“下一个元素”）。
为了将此算法应用于分区案例，我们观察以下内容：
陈述观察2中的条件的另一种方式是，除非元素的值为n或它是具有其值的序列中的第一个元素，否则该元素是可增量的。如果我们还维护序列[m1，… mn]，其中m1为0，mi是mi-1和pi-1的最大值。维护m很容易，它允许我们将增量条件简单地重新编写为pi≤mi。
很容易看出，Next Partition 可以在O(n)时间内实现，但事实上它的分摊时间也是O(1)。大致来说，这是因为在大多数情况下，序列的最后一个元素是可以递增的。
rec_func(SET) = List of List of Set
rec_func(SET) =
if SET = {empty}:
// if no element, easy to give the answer
return([[]])
else:
// 1. Remove one element from the set : 'a' to this set
a = SET.pop()
// 2. Call rec_func :
list_of_list_of_set = rec_func(SET\'a')
response = []
// 3. For every possibilities given by the function add the element 'a' :
For every list_of_set in list_of_list_of_set :
// Case 1, you add 'a' to list_of_set
response.push( [{'a'} + list_of_set] )
// Case 2, for every set, you create a copy where you add 'a'
for every set in list_of_set:
response.push( [{set,'a'} + list_of_set\set] )
// The function return the list of list of set created.
return(response)
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
{1} {2}），你需要尝试将新元素添加到每个部分 -- 这样你就会为每个部分创建一个全新的分区。2. 你还需要创建包含新数字单独在一个部分中的分区。 - j_random_hackerprintPartitions的递归调用中，您传递i > maximum ? i : maximum。这可以通过观察到，在除了最后一个递归调用之外的所有递归调用中，您只需传递最大值，在最后一个递归调用中，您传递最大值加一来使其更有效率。这会使代码变得简单些。请参见https://ideone.com/6vaXaN。 - rici