向量中元素的所有组合在更大的向量中

Question

我有以下输入向量。

['a','b','c'] 

我想列出所有可能的组合。

有三个限制：

• 这些值必须插入到六个位置的输出向量中。
• 输入向量中的一个给定值只能在输出向量中出现一次。
• 输出向量中的值的顺序必须与输入向量中的相同。

两个权限：

• 位置可以留空。
• （此处未显示：）输入向量可以具有多个任意给定值（例如

  ['a','b','a','c']

  ）

鉴于上面的输入向量，唯一有效的输出如下（我可能错过了一两个，但你明白了）：

[' ',' ',' ','a','b','c'],
[' ',' ','a',' ','b','c'],
[' ','a',' ',' ','b','c'],
['a',' ',' ',' ','b','c'],
[' ',' ','a','b',' ','c'],
[' ','a','b',' ',' ','c'],
['a','b',' ',' ',' ','c'],
[' ','a',' ','b',' ','c'],
['a',' ','b',' ',' ','c'],
['a',' ',' ','b',' ','c'],
[' ',' ','a','b','c',' '],
[' ','a','b','c',' ',' '],
['a','b','c',' ',' ',' '],
[' ','a',' ','b','c',' '],
['a',' ','b','c',' ',' '],
['a',' ','b',' ','c',' ']

我的第一个想法是生成大约 6 个！向量，其中向量是可能值的随机组合，包括空值：

[abc ]|[abc ]...[abc ]

，然后删除所有 a/b/c 出现次数多于输入向量且 abc 的顺序与以下不同的向量在输入向量中。但这种蛮力措施需要很长时间。

我必须经常这样做，并且对于不同大小的输入向量和输出向量。

Answer 1

IIUC，您可以使用 multiset_permutations

 模块中的 

sympy：

from sympy.utilities.iterables import multiset_permutations

l = ["a", "b", "c"]

for p in multiset_permutations([0] * 3 + [1] * 3):
    i = iter(l)
    print([" " if v == 0 else next(i) for v in p])

打印：

[' ', ' ', ' ', 'a', 'b', 'c']
[' ', ' ', 'a', ' ', 'b', 'c']
[' ', ' ', 'a', 'b', ' ', 'c']
[' ', ' ', 'a', 'b', 'c', ' ']
[' ', 'a', ' ', ' ', 'b', 'c']
[' ', 'a', ' ', 'b', ' ', 'c']
[' ', 'a', ' ', 'b', 'c', ' ']
[' ', 'a', 'b', ' ', ' ', 'c']
[' ', 'a', 'b', ' ', 'c', ' ']
[' ', 'a', 'b', 'c', ' ', ' ']
['a', ' ', ' ', ' ', 'b', 'c']
['a', ' ', ' ', 'b', ' ', 'c']
['a', ' ', ' ', 'b', 'c', ' ']
['a', ' ', 'b', ' ', ' ', 'c']
['a', ' ', 'b', ' ', 'c', ' ']
['a', ' ', 'b', 'c', ' ', ' ']
['a', 'b', ' ', ' ', ' ', 'c']
['a', 'b', ' ', ' ', 'c', ' ']
['a', 'b', ' ', 'c', ' ', ' ']
['a', 'b', 'c', ' ', ' ', ' ']