求组合的算法问题

2020-05-17 20:05:17 +08:00
 crella
已知列表 A 是 1 到正整数 M 之间所有整数的集合,B 是一个列表,它所有元素之和等于 M,且每个元素皆大于等于 1 。
求把列表 A 按照列表 B 的每个元素所代表的长度来分组的情况。

比如 A=range(1,6),B=[2,2,1,1]。那么可能的分组情况如下:
[[1,2],[3,4],5,6]
[[4,5],[1,3],2,6]
……
其中每个组内的元素是无序的,比如[4,5]==[5,4]。

想了一下,发现我把自己绕晕了;如果只是单独的去重,感觉比较慢,当 M 很大的时候,去重的比较的时间就可能是无底洞了。用动态规划,我又把握不好前后的条件要怎样搞。

请各位大佬指点。
2895 次点击
所在节点    Python
15 条回复
crella
2020-05-17 20:08:20 +08:00
想过一个歪门邪道的办法,那就是把列表的文本形式(排序后的)也缓存起来,然后去重的时候仅比较两个列表的文本是否相同
ConradG
2020-05-17 20:23:43 +08:00
C(M, b1) * C(M-b1, b2) * C(M-b1-b2, b3) ...就行了啊
beidounanxizi
2020-05-17 20:23:58 +08:00
dp[i,m]=dp[i-1,m-b[i]]+N;
N = m 个元素里面取 b[i]个元素
大概思路这样子
也许 dfs+剪枝可以做
teawithlife
2020-05-17 20:25:49 +08:00
不知道我理解的是否正确,这不就是一个简单的组合问题么?
C(6,2)*C(4,2)*C(2,1)*C(1,1)=15*6*2*1=180
beidounanxizi
2020-05-17 20:29:13 +08:00
fix 一点 dp[i,m]=dp[i-1,m-b[i]] * N;
duality
2020-05-18 02:45:20 +08:00
这个结构叫做 lambda 划分的杨格
给定 n, 令 lambda = (n_1, n_2, ..., n_m), n_1 <= n_2 <= ... <= n_m, n_1+ n_2 + ... + n_m = n 为一个划分
对于一个给定的划分 对应的杨格数量是 n!/lambda! = n!/(n_1! n_2! ... n_m!)
duality
2020-05-18 02:45:54 +08:00
yufeizhao.com/ research/youngtab-hcmr.pdf
你可以看一看 36 页那个结构是不是你要的

如果你想列出所有杨格, 好像直接 DFS 就行吧
necomancer
2020-05-18 03:29:51 +08:00
n 个元素划分 k 类?
我知道 SageMath 有 SetPartitions(6, [2,2,1,1]).list(),好像还有 OrderedSetPartition,后者才等于楼上提到的 n!/(n_1!n_2!..n_k!),你需要不考虑顺序的应该是用第一个函数。
necomancer
2020-05-18 03:57:02 +08:00
按你的要求,应该是 45 个而不是 180 个。
guchengyehai1
2020-05-18 08:55:31 +08:00
首先 A 数组来个全排列?再分组
qwertyegg
2020-05-18 09:12:56 +08:00
很明显的 DFS 吧
wingor2015
2020-05-20 10:57:43 +08:00
import itertools
def get_slice_unequal(nums, groups):
datas = itertools.combinations(nums, groups[0])
if len(groups) == 1:
return [[list(item)] for item in datas]
res = list()
for item in datas:
for sub_item in get_slice_unequal(list(set(nums) - set(item)), groups[1:]):
new_item = [list(item)]
res.append(new_item + sub_item)
return res


nums = [1, 2, 3, 4, 5, 6]
numsb = [2, 2, 1, 1]
res = get_slice_unequal(nums, numsb)
for item in res:
print(item)
print(len(res))
wingor2015
2020-05-20 11:01:48 +08:00
import itertools
def get_slice_unequal(nums, groups):
datas = itertools.combinations(nums, groups[0])
if len(groups) == 1:
return [[list(item)] for item in datas]
res = list()
for item in datas:
for sub_item in get_slice_unequal(list(set(nums) - set(item)), groups[1:]):
new_item = [list(item)]
res.append(new_item + sub_item)
return res
wingor2015
2020-05-20 11:02:13 +08:00
擦,这玩意没法编辑格式吗
dahuahua
2020-05-22 23:41:49 +08:00
跟美团的春招笔试题好像

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/672653

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX