排列组合
2022-09-09 本文已影响0人
垃圾桶边的狗
需求
- n个10以内的数字[1,4,5,8...]
2.生成2-10的种组合
3.每个组合的和在8-20之间
4.每个小组合元素重复率小于之前生成组合的50%
5.每种大组合元素重复率小于之前生成2-10种组合的50%
例子:
组合顺序：[4, 6, 5, 3, 2]
每种生成2组
[
[1, 2, 3, 22], [1, 4, 15, 23],
[1, 2, 5, 23, 24, 25], [1, 6, 15, 21, 22, 23],
[1, 3, 19, 21, 24],[1, 9, 19, 22, 25],
[1, 10, 11], [2, 4, 19],
[1, 7], [2, 6]
]
code_v1 初版本
import random
from itertools import combinations
from box import Box
import toolz
l = [5.78, 5.87, 6.74, 9.15, 5.31, 5.78, 14.17, 9.15, 7.23, 8.19, 5.97, 8.66, 11.54, 11.54, 3.86, 9.15, 7.7, 8.19, 3.78,
9.11, 1.89, 1.13, 1, 1, 1]
l1 = {1: 5.78, 2: 5.87, 3: 6.74, 4: 9.15, 5: 5.31, 6: 5.78, 7: 14.17, 8: 9.15, 9: 7.23, 10: 8.19, 11: 5.97, 12: 8.66,
13: 11.54, 14: 11.54, 15: 3.86, 16: 9.15, 17: 7.7, 18: 8.19, 19: 3.78, 20: 9.11, 21: 1.89, 22: 1.13, 23: 1,
24: 1, 25: 1}
# l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
# l1 = {1: 1.78, 2: 1.87, 3: 1.74, 4: 1.15, 5: 1.31, 6: 1.78, 7: 1, 8: 1, 9: 1, 10: 1, 11: 1, 12: 1, 13: 1, 14: 1, 15: 1,
# 16: 1}
class A:
filter_list = []
data_set = None
num = 0
class Combination(A):
def combination_sum3(self, k, gt, lt, tag):
unique_set = set()
candidates = range(1, len(l) + 1)
target = lt
# 结果列表
ans = []
ans1 = []
# 可能组合
tmp = []
const = Box({4: {"var": 2, "length": 6},
3: {"var": 2, "length": 3},
2: {"var": 1, "length": 2},
5: {"var": 3, "length": 10},
6: {"var": 3, "length": 20},
7: {"var": 4, "length": 35},
8: {"var": 4, "length": 70},
9: {"var": 5, "length": 126},
10: {"var": 5, "length": 252},
})
config = const[k]
def back_dfs(idx, total):
# 判断长度和值是否达到要求
if total > gt and total < lt and len(tmp[::]) == k: # and len(tmp[::])==k
combis = list(combinations(tmp[::], config.var))
if not unique_set:
if tag == 'one':
unique_set.update(set(combis))
ans.append(tmp[::])
self.filter_list.append(tmp[::])
ans1.append([l1[i] for i in tmp[::]])
else:
base_num = int(len(tmp) / 2 + 1)
# 对self.filter_list 排列组合
com_lists = [list(combinations(arr, base_num)) for arr in self.filter_list]
com_lists_flatten = list(toolz.concat(com_lists))
# 对tmp 排列组合
tmp_com = list(combinations(tmp, base_num))
# 全部是False 就添加
if True not in [i in com_lists_flatten for i in tmp_com]:
unique_set.update(set(combis))
ans.append(tmp[::])
self.filter_list.append(tmp[::])
# ans1.append([l1[i] for i in tmp[::]])
bools = [c in unique_set for c in combis]
false_len = len([b for b in bools if b == False])
if unique_set and tuple(tmp[:config.var]) not in unique_set and false_len == config.length: # len(combis)
if len(ans) == 10: # 限定取多少组
return ans
if tag == 'one':
unique_set.update(set(combis))
ans.append(tmp[::])
self.filter_list.append(tmp[::])
# ans1.append([l1[i] for i in tmp[::]])
else:
base_num = int(len(tmp) / 2 + 1)
# 对self.filter_list 排列组合
com_lists = [list(combinations(arr, base_num)) for arr in self.filter_list]
com_lists_flatten = list(toolz.concat(com_lists))
# 对tmp 排列组合
tmp_com = list(combinations(tmp, base_num))
# 全部是False 就添加
if True not in [i in com_lists_flatten for i in tmp_com]:
unique_set.update(set(combis))
ans.append(tmp[::])
self.filter_list.append(tmp[::])
# ans1.append([l1[i] for i in tmp[::]])
# return
if total > target:
return
# 打乱顺序
# shuffle_seq = list(range(idx, len(candidates)))
# random.shuffle(shuffle_seq)
# for i in shuffle_seq:
for i in range(idx, len(candidates)):
# 这里限制同一层不能选择值相同的元素
# 若有相同的元素，优先选择索引靠前的
if candidates[i - 1] == candidates[i] and i - 1 >= idx:
continue
total += l1[candidates[i]]
# total += candidates[i]
tmp.append(candidates[i])
# 从当前索引的下一位开始选取，避免重复选取同个元素
back_dfs(i + 1, total)
# 回溯
tmp.pop()
total -= l1[candidates[i]]
# total -= candidates[i]
total = 0
back_dfs(0, total)
# print(ans1)
return ans
if __name__ == '__main__':
ids = [4, 6, 5, 3, 2]
first_num = ids.pop(0)
c = Combination()
c.combination_sum3(k=first_num, gt=8, lt=20, tag='one')
# 如果第一位没有匹配到继续pop 0 知道filter_list为True
while not c.filter_list:
first_num = ids.pop(0)
c = Combination()
c.combination_sum3(k=first_num, gt=8, lt=20, tag='one')
for i in ids:
c.num = ids[0]
com_array = c.combination_sum3(k=i, gt=8, lt=20, tag='any')
print('------------------------', i)
print(com_array)
# for arr in com_array:
# print(arr)
print([l1[i] for sub_arr in c.filter_list for i in sub_arr])
print("每个sub_arr时长：",[sum(map(lambda x:l1[x], sub_arr)) for sub_arr in c.filter_list])
print("len(c.filter_list)",len(c.filter_list),c.filter_list)
