V2EX = way to explore V2EX 是一个关于分享和探索的地方
Sign Up Now For Existing Member Sign In
推荐学习书目 Learn Python the Hard Way Python Sites PyPI - Python Package Index http://diveintopython.org/toc/index.html Pocoo 值得关注的项目 PyPy Celery Jinja2 Read the Docs gevent pyenv virtualenv Stackless Python Beautiful Soup 结巴中文分词 Green Unicorn Sentry Shovel Pyflakes pytest Python 编程 pep8 Checker Styles PEP 8 Google Python Style Guide Code Style from The Hitchhiker's Guide
This topic created in 2171 days ago, the information mentioned may be changed or developed.
已知列表 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 很大的时候，去重的比较的时间就可能是无底洞了。用动态规划，我又把握不好前后的条件要怎样搞。
请各位大佬指点。
求把列表 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 很大的时候，去重的比较的时间就可能是无底洞了。用动态规划，我又把握不好前后的条件要怎样搞。
请各位大佬指点。
 | 1 crella OP 想过一个歪门邪道的办法，那就是把列表的文本形式（排序后的）也缓存起来，然后去重的时候仅比较两个列表的文本是否相同 |
 | 2 ConradG May 17, 2020 C(M, b1) * C(M-b1, b2) * C(M-b1-b2, b3) ...就行了啊 |
 | 3 beidounanxizi May 17, 2020 dp[i,m]=dp[i-1,m-b[i]]+N; N = m 个元素里面取 b[i]个元素 大概思路这样子 也许 dfs+剪枝可以做 |
 | 4 teawithlife May 17, 2020  1 不知道我理解的是否正确，这不就是一个简单的组合问题么？ C(6,2)*C(4,2)*C(2,1)*C(1,1)=15*6*2*1=180 |
| 5 beidounanxizi May 17, 2020 fix 一点 dp[i,m]=dp[i-1,m-b[i]] * N; |
 | 6 duality May 18, 2020 这个结构叫做 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!) |
| 7 duality May 18, 2020 |
 | 8 necomancer May 18, 2020 n 个元素划分 k 类？ 我知道 SageMath 有 SetPartitions(6, [2,2,1,1]).list()，好像还有 OrderedSetPartition，后者才等于楼上提到的 n!/(n_1!n_2!..n_k!)，你需要不考虑顺序的应该是用第一个函数。 |
| 9 necomancer May 18, 2020 按你的要求，应该是 45 个而不是 180 个。 |
 | 10 guchengyehai1 May 18, 2020 via Android 首先 A 数组来个全排列？再分组 |
 | 11 qwertyegg May 18, 2020 很明显的 DFS 吧 |
 | 12 wingor2015 May 20, 2020 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)) |
| 13 wingor2015 May 20, 2020 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 |
| 14 wingor2015 May 20, 2020 擦，这玩意没法编辑格式吗 |
 | 15 dahuahua May 22, 2020 跟美团的春招笔试题好像 |
Select Language