算法和数据结构|生成r子集组合数学|算法

文章目录

1 问题描述
2 字典序
3 字典序后继
4 按字典序生成 { 1 , 2 , ? ? , n } \{1,2,\cdots, n\} {1,2,?,n}的 r r r子集算法
5r r r子集在字典序中的位置
6 参考资料

1 问题描述 ??对于一个含有 n n n个元素的集合 S = { 1 , 2 , ? ? , n } S=\{1,2,\cdots, n\} S={1,2,?,n}，我们考虑生成固定大小 r ( 1 ≤ r ≤ n ) r(1\le r \le n) r(1≤r≤n)的子集。
2 字典序 ??集合 S S S的自然顺序为：
1 < 2 < ? < n 1\lt 2\lt \cdots \lt n 1<2 设 A A A和 B B B是集合 S S S的两个 r r r子集。如果在并集 A ∪ B A\cup B A∪B中但不在交集 A ∩ B A\cap B A∩B中的最小整数在 A A A中，我们就说在字典序中 A A A先于 B B B。
??由于子集中的元素并不考虑顺序，例如 123 123 123和 321 321 321作为子集是一样的。但是为了便于生成子集，我们约定：当书写 { 1 , 2 , ? ? , n } \{1,2,\cdots, n\} {1,2,?,n}的子集时，以从最小整数到最大整数的顺序书写其中的整数，即下面的形式：
a 1 , a 2 , ? ? , a r 其中 1 ≤ a 1 < a 2 < ? < a r ≤ n a_1,a_2,\cdots,a_r其中1\le a_1\lt a_2 \lt \cdots \lt a_r \le n a1?,a2?,?,ar?其中1≤a1? 这样我们就有了生成 r r r子集的一个先后顺序了。
??例如考虑 { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } \{1,2,3,4,5,6,7,8,9\} {1,2,3,4,5,6,7,8,9}的 5 5 5子集。第一个 5 5 5子集是 12345 12345 12345，最后一个 5 5 5子集是 56789 56789 56789。在字典序中 12389 12389 12389的直接后继是 12456 12456 12456。
3 字典序后继 ??定理：设 a 1 a 2 ? a r a_1a_2\cdots a_r a1?a2??ar?是 { 1 , 2 , ? ? , n } \{1,2,\cdots, n\} {1,2,?,n}的 r r r子集。在字典序中，第一个 r r r子集是 12 ? r 12\cdots r 12?r，最后一个 r r r子集是 ( n ? r + 1 ) ( n ? r + 2 ) ? n (n-r+1)(n-r+2)\cdots n (n?r+1)(n?r+2)?n。假设 a 1 a 2 ? a r ≠ ( n ? r + 1 ) ( n ? r + 2 ) ? n a_1a_2\cdot a_r\ne (n-r+1)(n-r+2)\cdots n a1?a2??ar??=(n?r+1)(n?r+2)?n。设 k k k是满足 a k < n a_k\lt n ak?a 1 ? a k ? 1 ( a k + 1 ) ( a k + 2 ) ? ( a k + r ? k + 1 ) a_1\cdots a_{k-1}(a_k + 1)(a_k+2)\cdots(a_k+r-k+1) a1??ak?1?(ak?+1)(ak?+2)?(ak?+r?k+1)
证明：
??根据字典序的定义，设 a 1 a 2 ? a r a_1a_2\cdots a_r a1?a2??ar?是任意一个 r r r子集，但不是最后的，确定出指定的 k k k，于是：
a 1 a 2 ? a r = a 1 ? a k ? 1 a k ( n ? r + k + 1 ) ( n ? r + k + 2 ) ? ( n ) ，其中 a k + 1 < n ? r + k + 1 a_1a_2\cdots a_r=a_1\cdots a_{k-1}a_k(n-r+k+1)(n-r+k+2)\cdots (n)，其中a_k+1\lt n-r+k+1 a1?a2??ar?=a1??ak?1?ak?(n?r+k+1)(n?r+k+2)?(n)，其中ak?+1 是以 a 1 ? a k ? 1 a k a_1\cdots a_{k-1}a_k a1??ak?1?ak?开始的最后的 r r r子集。而下面的 r r r子集：
a 1 ? a k ? 1 ( a k + 1 ) ( a k + 2 ) ? ( a k + r ? k + 1 ) a_1\cdots a_{k-1}(a_k + 1)(a_k+2)\cdots(a_k+r-k+1) a1??ak?1?(ak?+1)(ak?+2)?(ak?+r?k+1)
是以 a 1 ? a k ? 1 a k + 1 a_1\cdots a_{k-1}a_k+1 a1??ak?1?ak?+1开始的第一个 r r r子集，从而是 a 1 a 2 ? a r a_1a_2\cdots a_r a1?a2??ar?的直接后继。
4 按字典序生成 { 1 , 2 , ? ? , n } \{1,2,\cdots, n\} {1,2,?,n}的 r r r子集算法 ??根据上述定理，我们可以描述算法如下：从 r r r子集 12 ? r 12\cdots r 12?r开始，当 a 1 a 2 ? a r ≠ ( n ? r + 1 ) ( n ? r + 2 ) ? n a_1a_2\cdot a_r\ne (n-r+1)(n-r+2)\cdots n a1?a2??ar??=(n?r+1)(n?r+2)?n时，执行下列操作：

确定最大的整数 k k k，是的 a k + 1 ≤ n a_k + 1\le n ak?+1≤n且 a k + 1 a_k + 1 ak?+1不是 a 1 , a 2 , ? ? , a r a_1,a_2,\cdots,a_r a1?,a2?,?,ar?中的一个。
用 r r r子集 a 1 ? a k ? 1 ( a k + 1 ) ( a k + 2 ) ? ( a k + r ? k + 1 ) a_1\cdots a_{k-1}(a_k + 1)(a_k+2)\cdots(a_k+r-k+1) a1??ak?1?(ak?+1)(ak?+2)?(ak?+r?k+1)替换 a 1 a 2 ? a r a_1a_2\cdots a_r a1?a2??ar?

依照算法生成 { 1 , 2 , 3 , 4 , 5 , 6 } \{1,2,3,4,5,6\} {1,2,3,4,5,6}的 4 4 4子集：
123412562345 123513452346 123613462356 124513562456 124614563456 1234\ 1256\ 2345\\ 1235\ 1345\ 2346\\ 1236\ 1346\ 2356\\ 1245\ 1356\ 2456\\ 1246\ 1456\ 3456 1234 1256 23451235 1345 23461236 1346 23561245 1356 24561246 1456 3456
算法实现如下：

def gen_r(n, r): res = [] curr, end = "", "" for i in range(r): curr += str(i+1) end += str(n-r+i+1) while curr != end: res.append(curr) for i in range(r-1, -1, -1): if curr[i] != str(n-r+i+1): new = curr[:i] k = int(curr[i]) for j in range(1, r-i+1): new += str(j+k) curr = new break res.append(end) return res

输入：6 4 输出：['1234', '1235', '1236', '1245', '1246', '1256', '1345', '1346', '1356', '1456', '2345', '2346', '2356', '2456', '3456']

5r r r子集在字典序中的位置 ??定理： { 1 , 2 , ? ? , n } \{1,2,\cdots,n\} {1,2,?,n}的 r r r子集 a 1 a 2 ? a r a_1a_2\cdots a_r a1?a2??ar?出现在 { 1 , 2 , ? ? , n } \{1,2,\cdots,n\} {1,2,?,n}的 r r r子集的字典序中的位置下标（从 1 1 1开始）是：
( n r ) ? ( n ? a 1 r ) ? ( n ? a 2 r ? 1 ) ? ? ? ( n ? a r ? 1 2 ) ? ( n ? a r 1 ) \begin{pmatrix}n\\r\end{pmatrix}-\begin{pmatrix}n-a_1\\r\end{pmatrix}-\begin{pmatrix}n-a_2\\r-1\end{pmatrix}-\cdots-\begin{pmatrix}n-a_{r-1}\\2\end{pmatrix}-\begin{pmatrix}n-a_r\\1\end{pmatrix} (nr?)?(n?a1?r?)?(n?a2?r?1?)???(n?ar?1?2?)?(n?ar?1?)
??这个定理还是比较好理解的，就是总的 r r r子集数量减去出现在 a 1 a 2 ? a r a_1a_2\cdots a_r a1?a2??ar?后面的 r r r子集数量：

第一个元素比 a 1 a_1 a1?大的数量是 ( n ? a 1 r ) \begin{pmatrix}n-a_1\\r\end{pmatrix} (n?a1?r?)
第一个元素与 a 1 a_1 a1?相等，但是第二个元素比 a 2 a_2 a2?大的数量是 ( n ? a 2 r ? 1 ) \begin{pmatrix}n-a_2\\r-1\end{pmatrix} (n?a2?r?1?)
? ? \cdots \cdots ??
以 a 1 a 2 ? a r ? 1 a_1a_2\cdots a_{r-1} a1?a2??ar?1?开始，但最后一个元素比 a r a_r ar?大的数量是 ( n ? a r 1 ) \begin{pmatrix}n-a_r\\1\end{pmatrix} (n?ar?1?)

例如 { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } \{1,2,3,4,5,6,7,8\} {1,2,3,4,5,6,7,8}的 4 4 4子集的字典序之下，子集 1258 1258 1258所处位置为：
( 8 4 ) ? ( 7 4 ) ? ( 6 3 ) ? ( 3 2 ) ? ( 0 1 ) = 12 \begin{pmatrix}8\\4\end{pmatrix}-\begin{pmatrix}7\\4\end{pmatrix}-\begin{pmatrix}6\\3\end{pmatrix}-\begin{pmatrix}3\\2\end{pmatrix}-\begin{pmatrix}0\\1\end{pmatrix}=12 (84?)?(74?)?(63?)?(32?)?(01?)=12
【算法和数据结构|生成r子集】寻找下标程序实现如下：

def find_index(n, subset): C = lambda x, y: math.factorial(x)//math.factorial(y)//math.factorial(x-y) if x >= y else 0 r = len(subset) a = C(n, r) s = sum(C(n-int(subset[r-i-1]), i+1) for i in range(r)) return a - s