上饶市建设局有什么网站,wordpress 页面二维码,西安危机公关公司,西安做效果图的公司生成整数序列字典序的r-组合算法 一、PPT效果展示二、问题2.1 简述2.2 算法简述2.3 例子 三、PPT实现 一、PPT效果展示 二、问题
2.1 简述
给定一个整数序列 (1#xff0c;2#xff0c;3#xff0c;…n)#xff0c;输出其所有字典序的r-组合#xff0c;注意事项#xf… 生成整数序列字典序的r-组合算法 一、PPT效果展示二、问题2.1 简述2.2 算法简述2.3 例子 三、PPT实现 一、PPT效果展示 二、问题
2.1 简述
给定一个整数序列 (123…n)输出其所有字典序的r-组合注意事项
所有组合不能重复每个组合中的元素顺序需为字典序 (从小到大)所有组合呈字典序 (后一组合 前一组合)
例给定整数序列123456求其4-组合 开始组合1234 中间组合123512361245… 结束组合3456
2.2 算法简述
给定一个整数序列(123...n)其r-组合
其必从{ 1 , 2 , . . . , r 1,2,...,r 1,2,...,r}开始到{ n − r 1 , . . . , n − 1 , n n-r1,...,n-1,n n−r1,...,n−1,n}结束存在最大的一个整数 k ∈ { 1 , . . . , r } k\in \{1,...,r\} k∈{1,...,r}使得 A k 1 ≤ n A_k 1 \leq n Ak1≤n 且 A k ∉ A A_k\notin A Ak∈/A ( A A A为当前组合 A k A_k Ak不属于当前组合)新的组合 A A A { A 1 , . . . , A k − 1 , A k 1 , . . . , A k r − k 1 A_1, ..., A_{k-1}, A_k1, ..., A_kr-k1 A1,...,Ak−1,Ak1,...,Akr−k1} 其中 A 1 , . . . , A k − 1 A_1, ..., A_{k-1} A1,...,Ak−1是上一个组合的前一部分新的组合从 A k A_k Ak开始更新
(个人理解)核心思想就是由于现组合中的元素为字典序选取最大的 k k k以及使用 A k 1 , A k 2 , . . . A_k 1, A_k2, ... Ak1,Ak2,... 替换 A k A_k Ak及其后的元素即可保证替换后依旧为字典序且刚好比前一组合大“一点”
2.3 例子
例整数序列1-6的4-组合从1236 - 1245 A A A { A 1 1 , A 2 2 , A 3 3 , A 4 6 A_11, A_22, A_33, A_46 A11,A22,A33,A46}
若 k 4 k4 k4 A 4 6 A_4 6 A46 A 4 1 6 A_4 1 6 A416不符合条件。存在最大的 k 3 k3 k3使得 A 3 1 4 A_31 4 A3144小于6且不属于1236。新的组合从 A 3 A_3 A3开始更新即 { A 1 , A 2 , A 3 1 , A 3 4 − 3 1 A_1,A_2,A_31,A_34-31 A1,A2,A31,A34−31} { 1 , 2 , 3 1 , 3 4 − 3 1 1, 2 ,31, 34-31 1,2,31,34−31} { 1 , 2 , 4 , 5 1,2,4,5 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 -1Dim tmp As Stringtmp ak - k 1 i s_alls 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 Fcurrent L_c.CaptionMsgBox currentMsgBox numcurrent 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
