生成所有排列,其中排列的长度> Python中的元素数

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (55)

我想从这些元素生成排列(元组):

[None, 0, 1, 2]. 

我希望每个排列长度为5,并且总是包含3个Nones。一个这样的排列的一个例子:

(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,但没有找到任何可以帮助我的东西。

谢谢您的帮助!

提问于
用户回答回答于

假设(从您的代码输出和故意添加0,1和2的多个副本的事实)您正在做'替换'的排列',或者基本上是具有3 Nones要求的笛卡尔积,我会做就像是:

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

对于小尺寸,优点是有限的,但对于较大的尺寸,这样你就可以避免生成任何不使用的元组,并且因为它是一个生成器,所以如果你不想,你就不必实现它们。

用户回答回答于

您可以创建递归函数:

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]]

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励