生成所有排列，其中排列的长度> Python中的元素数
生成所有排列，其中排列的长度> Python中的元素数
提问于 2018-07-14 02:04:56
我想从这些元素生成排列(元组)：
[None, 0, 1, 2]. 我希望每个排列的长度为5，并且始终包含3个None。一个这样的排列的例子：
(None, 0, None, None, 1).我目前在Python 3.x中创建了这个算法：
[state for state in list(set(it.permutations((None, None, None, 0, 0, 1, 1, 2, 2), 5))) if state.count(None)==3]然而，我觉得这个算法是次优的(而且，嗯，丑陋)，我甚至不能完全确定它是正确的。有没有更好的解决方案？我仔细阅读了NumPy，但没有找到任何对我有帮助的东西。
谢谢你的帮助！
回答 5
Stack Overflow用户
发布于 2018-07-14 02:08:49
您可以创建一个递归函数：
def group(d, current = [], in_place = [None, 3]):
need, _occurs = in_place
if len(current) == 5 and current.count(need) == _occurs:
yield current
else:
for i in d:
_c = current+[i]
if len(_c) <= 5 and _c.count(need) <= _occurs:
yield from group(d, current = _c)输出：
[[None, None, None, 0, 0], [None, None, None, 0, 1], [None, None, None, 0, 2], [None, None, None, 1, 0], [None, None, None, 1, 1], [None, None, None, 1, 2], [None, None, None, 2, 0], [None, None, None, 2, 1], [None, None, None, 2, 2], [None, None, 0, None, 0], [None, None, 0, None, 1], [None, None, 0, None, 2], [None, None, 0, 0, None], [None, None, 0, 1, None], [None, None, 0, 2, None], [None, None, 1, None, 0], [None, None, 1, None, 1], [None, None, 1, None, 2], [None, None, 1, 0, None], [None, None, 1, 1, None], [None, None, 1, 2, None], [None, None, 2, None, 0], [None, None, 2, None, 1], [None, None, 2, None, 2], [None, None, 2, 0, None], [None, None, 2, 1, None], [None, None, 2, 2, None], [None, 0, None, None, 0], [None, 0, None, None, 1], [None, 0, None, None, 2], [None, 0, None, 0, None], [None, 0, None, 1, None], [None, 0, None, 2, None], [None, 0, 0, None, None], [None, 0, 1, None, None], [None, 0, 2, None, None], [None, 1, None, None, 0], [None, 1, None, None, 1], [None, 1, None, None, 2], [None, 1, None, 0, None], [None, 1, None, 1, None], [None, 1, None, 2, None], [None, 1, 0, None, None], [None, 1, 1, None, None], [None, 1, 2, None, None], [None, 2, None, None, 0], [None, 2, None, None, 1], [None, 2, None, None, 2], [None, 2, None, 0, None], [None, 2, None, 1, None], [None, 2, None, 2, None], [None, 2, 0, None, None], [None, 2, 1, None, None], [None, 2, 2, None, None], [0, None, None, None, 0], [0, None, None, None, 1], [0, None, None, None, 2], [0, None, None, 0, None], [0, None, None, 1, None], [0, None, None, 2, None], [0, None, 0, None, None], [0, None, 1, None, None], [0, None, 2, None, None], [0, 0, None, None, None], [0, 1, None, None, None], [0, 2, None, None, None], [1, None, None, None, 0], [1, None, None, None, 1], [1, None, None, None, 2], [1, None, None, 0, None], [1, None, None, 1, None], [1, None, None, 2, None], [1, None, 0, None, None], [1, None, 1, None, None], [1, None, 2, None, None], [1, 0, None, None, None], [1, 1, None, None, None], [1, 2, None, None, None], [2, None, None, None, 0], [2, None, None, None, 1], [2, None, None, None, 2], [2, None, None, 0, None], [2, None, None, 1, None], [2, None, None, 2, None], [2, None, 0, None, None], [2, None, 1, None, None], [2, None, 2, None, None], [2, 0, None, None, None], [2, 1, None, None, None], [2, 2, None, None, None]]Stack Overflow用户
发布于 2018-07-14 02:25:19
如果我真的不想生成和过滤掉一堆不合适的条目，我会这样做：
您需要0到3个代码项(称为n1)，然后是列表中的一个非None项，然后是0到3-n1 Nones (n2)，然后是列表中的第二个非None项，最后是3-n1-n2 <n2>D9None>s。
states = []
for (i1, i2) in permutations((0,1,2), 2):
for n1 in range(4):
for n2 in range(4-n1):
states.append((None,)*n1 + (i1,) + (None,)*n2 + (i2,) + (None,)*(3-n1-n2))Stack Overflow用户
发布于 2018-07-14 02:36:34
假设(从您的代码输出和您故意添加多个0、1和2副本的事实)，您正在进行“置换和替换”，或者基本上是具有3个None需求的笛卡尔乘积，我会这样做：
def tien_gen(size, values, number_of_nones):
to_fill = size - number_of_nones
for locs in itertools.combinations(range(size), to_fill):
for fill_values in itertools.product(values, repeat=to_fill):
out = [None] * size
for loc, fill_value in zip(locs, fill_values):
out[loc] = fill_value
yield tuple(out)它与您的输出相匹配：
In [137]: result = list(tien_gen(5, [0,1,2], 3))
In [138]: len(result)
Out[138]: 90
In [139]: result
Out[139]:
[(0, 0, None, None, None),
(0, 1, None, None, None),
(0, 2, None, None, None),
(1, 0, None, None, None),
[...]
(None, 0, None, 1, None),
(None, 0, None, 2, None),
(None, 1, None, 0, None),
[...]
(None, 2, None, 1, None),
(None, 2, None, 2, None),
(None, 0, None, None, 0),
(None, 0, None, None, 1),
[...]
(None, None, None, 1, 2),
(None, None, None, 2, 0),
(None, None, None, 2, 1),
(None, None, None, 2, 2)]
In [140]: orig = [state for state in list(set(it.permutations((None, None, None, 0, 0, 1, 1, 2, 2), 5))) if state.count(None)==3]
In [141]: len(result) == len(orig) and set(result) == set(orig)
Out[141]: True对于较小的大小，优点是有限的，但对于较大的大小，这样就避免了生成任何不使用的元组，而且由于它是一个生成器，如果您不想实现所有元组，则不必全部实现它们。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51330651
复制相关文章
相似问题