首页 > 代码库 > 非递归实现:从给定的字典中抽出所有相加值SUM的全部组合
非递归实现:从给定的字典中抽出所有相加值SUM的全部组合
例如
dic = {0 : 1, 1 : 3, 2 : 5, 3 : 9, 4 : 4}
SUM = 9
抽取组合为
- 3:9
- 2:5 4:4 (5+4=9)
- 0:1 1:3 2:5 (1+3+5=9)
本程序的思路是开一个数组,其下标表示1到m个数,数组元素的值为1表示其下标
代表的数被选中,为0则没选中。
首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。
然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为
“01”组合,同时将其左边的所有“1”全部移动到数组的最左端。
当第一个“1”移动到数组的m-n的位置,即n个“1”全部移动到最右端时,就得
到了最后一个组合。
例如求5中选3的组合:
1 1 1 0 0 //1,2,3 1 1 0 1 0 //1,2,4 1 0 1 1 0 //1,3,4 0 1 1 1 0 //2,3,4 1 1 0 0 1 //1,2,5 1 0 1 0 1 //1,3,5 0 1 1 0 1 //2,3,5 1 0 0 1 1 //1,4,5 0 1 0 1 1 //2,4,5 0 0 1 1 1 //3,4,5
因此非递归实现的大致代码如下:
#coding=utf-8 #从m个数字里面抽出来n个 def sum(pos,target): sum = 0 for i in range(len(pos)): if pos[i] == 1: sum += dic[i] if sum == target: return True def leftfix(index,onecount,pos,target): if index >= 2 and index < len(pos)-2: pos[0:index] = [1]*onecount+[0]*(index-onecount) if sum(pos,target): print pos def find(m ,n ,target): pos = [1]*n+[0]*(m-n) if sum(pos,target): print pos i = 0 j = 0 while True: if i>=len(pos)-1:break if pos[i] == 1: j += 1 if pos[i+1] == 0: j -= 1 #之前的i个数字里面有j个1 i-j个0 pos[i], pos[i + 1] = pos[i + 1], pos[i] if sum(pos,target): print pos leftfix(i,j,pos,target) i = -1 j = 0 i+=1 dic = {0 : 1, 1 : 3, 2 : 5, 3 : 9, 4 : 4} for n in range(1,len(dic)+1): find(len(dic),n,9)
非递归实现:从给定的字典中抽出所有相加值SUM的全部组合
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。