一、PPT效果展示

二、问题

2.1 简述

给定一个整数序列 (1，2，3，…n)，输出其所有字典序的r-组合，注意事项：

1. 所有组合不能重复，每个组合中的元素顺序需为字典序 (从小到大)
2. 所有组合呈字典序 (后一组合 > 前一组合)

例：给定整数序列123456，求其4-组合
开始组合：1234
中间组合：1235，1236，1245，…
结束组合：3456

2.2 算法简述

给定一个整数序列(1，2，3，...n)，其r-组合：

1. 其必从{$1,2,...,r$}开始，到{$n-r+1,...,n-1,n$}结束
2. 存在最大的一个整数 k ∈ { 1 , . . . , r } k\in \{1,...,r\} k∈{1,...,r}，使得$A_k+1\le n$ 且$A_k\notin A$ ($A$为当前组合，$A_k$不属于当前组合)
3. 新的组合$A=$ {$A_1,...,A_{k-1},A_k+1,...,A_k+r-k+1$}
   其中，$A_1,...,A_{k-1}$是上一个组合的前一部分，新的组合从$A_k$开始更新

(个人理解)核心思想就是：由于现组合中的元素为字典序，选取最大的$k$以及使用$A_k+1,A_k+2,...$ 替换 $A_k$及其后的元素，即可保证替换后依旧为字典序，且刚好比前一组合大“一点”

2.3 例子

例：整数序列1-6的4-组合，从1236 -> 1245： $A=$ {$A_1=1,A_2=2,A_3=3,A_4=6$}

1. 若$k=4$，$A_4=6$，$A_4+1>6$，不符合条件。
2. 存在最大的$k=3$，使得$A_3+1=4$，4小于6且不属于1236。
3. 新的组合从$A_3$开始更新，即 {$A_1,A_2,A_3+1,A_3+4-3+1$} =
   {$1,2,3+1,3+4-3+1$} = {$1,2,4,5$}

三、PPT实现

可到博客顶端 or 通过此链接 进入资源页下载完整PPT，放映即可用

亦可自行开发：在PPT左上角选择开发工具
主要控件：文本框 和 按钮

核心源码：

Public Sub F()s_all = T_in.Textn = Len(T_in.Text)num = T_num.Texts = L_c.Captionk = 0ak = 0flag = 0' 计算k和AkFor i = 1 To numflag = 1' 如果大于n 则直接退出a = Mid(s, i, 1) + 1If (Val(a) > n) ThenExit ForEnd IfFor j = i To num' 如果不符合条件 标志位set为0 跳出循环b = Mid(s, j, 1)If (StrComp(a, b, 1) = 0) Thenflag = 0Exit ForEnd IfNext jIf StrComp(flag, 1, 0) = 0 Thenk = iEnd IfNext iL_k.Caption = kL_ak.Caption = Mid(s, k, 1)ak = L_ak.Caption' 下一个组合For i = num To k Step -1'Dim tmp As String'tmp = ak - k + 1 + i s_all's = Replace(s, Mid(s, i, 1), Mid(s_all, ak - k + 1 + i, 1))Mid(s, i, 1) = Mid(s_all, ak - k + 1 + i, 1)Next iL_next.Caption = s
End SubPrivate Sub B_next_Click()s_all = T_in.Textn = Len(T_in.Text)num = T_num.TextL_c.Caption = L_next.CaptionT_show = T_show + L_c.Caption + vbCr + vbLfIf StrComp(L_c.Caption, Mid(s_all, n - num + 1, num), 1) = 0 ThenMsgBox "已经是最后一个组合了"Exit SubEnd IfCall F'current = L_c.Caption'MsgBox current'MsgBox num'current = Replace(current, Mid(current, 1, 1), Mid(s, 2, 1))'MsgBox current
End SubPrivate Sub B_s_Click()s = T_in.Textnum = T_num.TextL_c.Caption = Mid(s, 1, num)T_show = ""T_show = T_show + L_c.Caption + vbCr + vbLfCall F
End SubPrivate Sub T_show_Change()End Sub

可参考的C源码

r-组合: https://blog.csdn.net/ld326/article/details/84341452