生成所有 "without-replacement" 个子集系列
Generate all "without-replacement" subsets series
我正在寻找一种方法来生成一组所有可能的子组合，其中每个元素最多只能使用一次。
例如，集合 {1,2,3} 会产生
{{1},{2},{3}}
{{1},{2,3}}
{{1,2},{3}}
{{2},{1,3}}
{{1,2,3}}
最好有伪代码提示。另外，如果有这个术语，或者适用的术语，我很想学习它。
首先，几点建议。
将一个集合分成不相交的子集称为集合划分 (Wikipedia, MathWorld)。
编码集合分区的常用方法是restricted growth string。
set partitions的个数是Bell number，而且增长很快：对于20个元素的set，有51,724,158,235,372个set partitions。
这里是编码的工作原理。
按升序查看元素：1、2、3、4、...。
设 c 为当前子集数，最初为 0。
每当当前元素是其子集的最低元素时，我们为这个集合分配数字 c，然后将 c 增加 1。
无论如何，我们记下包含当前元素的子集的编号。
根据该过程，字符串的第一个元素将是 0，每个下一个元素不大于目前的最大值加一。因此得名 "restricted growth strings".
例如，考虑分区 {1,3},{2,5},{4}。
元素 1 是其子集中的最低元素，因此子集 {1,3} 标记为 0。
元素 2 是其子集中的最低元素，因此子集 {2,5} 标记为 1。
元素 3 位于已由 0 标记的子集中。
元素 4 是其子集中的最低元素，因此子集 {4} 标记为 2。
元素 5 位于已由 1 标记的子集中。
这样我们就得到了字符串01021。
字符串告诉我们：
元素 1 在子集 0 中。
元素 2 在子集 1 中。
元素 3 在子集 0 中。
元素 4 在子集 2 中。
元素 5 在子集 1 中。
为了从不同的角度感受它，这里是 four-element 集的所有分区，以及各自减少的增长字符串：
0000 {1,2,3,4}
0001 {1,2,3},{4}
0010 {1,2,4},{3}
0011 {1,2},{3,4}
0012 {1,2},{3},{4}
0100 {1,3,4},{2}
0101 {1,3},{2,4}
0102 {1,3},{2},{4}
0110 {1,4},{2,3}
0111 {1},{2,3,4}
0112 {1},{2,3},{4}
0120 {1,4},{2},{3}
0121 {1},{2,4},{3}
0122 {1},{2},{3,4}
0123 {1},{2},{3},{4}
至于伪代码，生成所有这些字符串相对简单。
我们递归地做。
保持值 c，将 0 到 c 的每个数字分配给当前位置，并且对于每个这样的选择，递归地构造字符串的其余部分。
也可以延迟生成它们，从一个全为零的字符串开始，然后重复查找字典顺序下一个这样的字符串，类似于 next_permutation 用于 list all permutations.
的方式
最后，如果您想了解更多（以及提到的 next 功能），这里有一些 self-promotion。
最近，我们在我的大学做了一个学习项目，要求学生以合理的效率实现组合 objects 的各种功能。
Here 是我们得到的限制增长字符串的部分；我链接了用英文描述功能的 header 部分。
我正在寻找一种方法来生成一组所有可能的子组合，其中每个元素最多只能使用一次。
例如，集合 {1,2,3} 会产生
{{1},{2},{3}}
{{1},{2,3}}
{{1,2},{3}}
{{2},{1,3}}
{{1,2,3}}
最好有伪代码提示。另外，如果有这个术语，或者适用的术语，我很想学习它。
首先，几点建议。
将一个集合分成不相交的子集称为集合划分 (Wikipedia, MathWorld)。
编码集合分区的常用方法是restricted growth string。
set partitions的个数是Bell number，而且增长很快：对于20个元素的set，有51,724,158,235,372个set partitions。
这里是编码的工作原理。
按升序查看元素：1、2、3、4、...。
设 c 为当前子集数，最初为 0。
每当当前元素是其子集的最低元素时，我们为这个集合分配数字 c，然后将 c 增加 1。
无论如何，我们记下包含当前元素的子集的编号。
根据该过程，字符串的第一个元素将是 0，每个下一个元素不大于目前的最大值加一。因此得名 "restricted growth strings".
例如，考虑分区 {1,3},{2,5},{4}。
元素 1 是其子集中的最低元素，因此子集 {1,3} 标记为 0。
元素 2 是其子集中的最低元素，因此子集 {2,5} 标记为 1。
元素 3 位于已由 0 标记的子集中。
元素 4 是其子集中的最低元素，因此子集 {4} 标记为 2。
元素 5 位于已由 1 标记的子集中。
这样我们就得到了字符串01021。
字符串告诉我们：
元素 1 在子集 0 中。
元素 2 在子集 1 中。
元素 3 在子集 0 中。
元素 4 在子集 2 中。
元素 5 在子集 1 中。
为了从不同的角度感受它，这里是 four-element 集的所有分区，以及各自减少的增长字符串：
0000 {1,2,3,4}
0001 {1,2,3},{4}
0010 {1,2,4},{3}
0011 {1,2},{3,4}
0012 {1,2},{3},{4}
0100 {1,3,4},{2}
0101 {1,3},{2,4}
0102 {1,3},{2},{4}
0110 {1,4},{2,3}
0111 {1},{2,3,4}
0112 {1},{2,3},{4}
0120 {1,4},{2},{3}
0121 {1},{2,4},{3}
0122 {1},{2},{3,4}
0123 {1},{2},{3},{4}
至于伪代码，生成所有这些字符串相对简单。
我们递归地做。
保持值 c，将 0 到 c 的每个数字分配给当前位置，并且对于每个这样的选择，递归地构造字符串的其余部分。
也可以延迟生成它们，从一个全为零的字符串开始，然后重复查找字典顺序下一个这样的字符串，类似于 next_permutation 用于 list all permutations.
最后，如果您想了解更多（以及提到的 next 功能），这里有一些 self-promotion。
最近，我们在我的大学做了一个学习项目，要求学生以合理的效率实现组合 objects 的各种功能。
Here 是我们得到的限制增长字符串的部分；我链接了用英文描述功能的 header 部分。