获取单个列表的递归排列

Question

我在 Python 工作，我想获得某种 'permutations' 的单个列表。我会尽力解释问题，但如果有任何疑问，请告诉我。

假设我们有一个字符串列表 a = ['?','A','A','A']，即有三个 'A' 元素：n=3。我想创建一种方法来递减地获取 'A' 的所有排列（其余元素为 '?'），从某种意义上说，在每个 'permutation layer' 中， 'A' 的数量减一：n=n-1.

有了例子，这个就更好理解了：

例如，对于 a，我们将在第一个 'permutation layer' (n=3-1) 中获得 a0 = ['?','A','A','?']、a1 = ['?','A','?','A'] 和 a2 = ['?','?','A','A']。同理，在第二个'permutation layer'(n=3-1-1);对于 a0，我们将有 a00 = ['?','A','?','?'] 和 a01 = ['?','?','A','?']，对于 a1，我们将有 a10 = ['?','A','?','?'] 和 a11 = ['?','?','?','A']，对于 a2，我们将有 a20 = ['?','?','A','?'] 和 a21 = ['?','?','?','A']。我知道其中一些可能是多余的，例如 a00 和 a10；没问题。

请注意，一旦达到 n=1，就不再有排列层，因为每个结果都是 aN = ['?','?','?','?']。

澄清：图层确实很重要，因为我想测试一个列表是否包含属性（不重要）以深入了解图层.我会更好地解释：如果 a0 持有属性，那么我们探索 a00 和 a01，否则我们不会。这样，我们可能不会探索所有排列。因此，我只需要在给定列表的情况下获得紧邻 NEXT 层的排列的方法，而不需要其余的排列。如果 n=1、returns 无论如何，请说 foo.

我不知道如何找到这个或类似的问题（事实上，谈论排列是否正确？）。这里最接近的 post 似乎是 Recursive list of permutations，其中提到了 'cartesian product' 和 'combinations with repetition' 等术语。但是问题不一样。

我不关心用什么方法求解，我不求效率；但是，我觉得这可以通过对 n.

进行递归的优雅方式来完成

谁能解决我的问题？我将不胜感激以 Python 或类似语言给出的代码。

编辑 1

使用 itertools.permutations() 没有产生预期的结果：

import itertools
a = ['?', 'A', 'A', 'A']

b = itertools.permutations(a)
for j in list(b): 
    print(j)

这会打印：

('?', 'A', 'A', 'A')
('?', 'A', 'A', 'A')
('?', 'A', 'A', 'A')
('?', 'A', 'A', 'A')
('?', 'A', 'A', 'A')
('?', 'A', 'A', 'A')
('A', '?', 'A', 'A')
('A', '?', 'A', 'A')
('A', 'A', '?', 'A')
('A', 'A', 'A', '?')
('A', 'A', '?', 'A')
('A', 'A', 'A', '?')
('A', '?', 'A', 'A')
('A', '?', 'A', 'A')
('A', 'A', '?', 'A')
('A', 'A', 'A', '?')
('A', 'A', '?', 'A')
('A', 'A', 'A', '?')
('A', '?', 'A', 'A')
('A', '?', 'A', 'A')
('A', 'A', '?', 'A')
('A', 'A', 'A', '?')
('A', 'A', '?', 'A')
('A', 'A', 'A', '?')

请注意，这里没有任何一个预期结果，因为 A 的数量没有减少。

Answer 1

听起来你想要一种方法来列出用 ?s 替换 As 的某些子集的所有方法，这意味着它与查找所有方法相同选择 A 的一个子集（itertools 有代码）。

Answer 2

这些并不是真正的排列。它们是 4 个 ['A','?'] 列表的产物。

您可以使用 itertool 的乘积函数在不递归的情况下获取它们：

from itertools import product

for p in product(*['A?']*4): print(p)
('A', 'A', 'A', 'A')
('A', 'A', 'A', '?')
('A', 'A', '?', 'A')
('A', 'A', '?', '?')
('A', '?', 'A', 'A')
('A', '?', 'A', '?')
('A', '?', '?', 'A')
('A', '?', '?', '?')
('?', 'A', 'A', 'A')
('?', 'A', 'A', '?')
('?', 'A', '?', 'A')
('?', 'A', '?', '?')
('?', '?', 'A', 'A')
('?', '?', 'A', '?')
('?', '?', '?', 'A')
('?', '?', '?', '?')

对于递归版本，您可以向下传递每个值（A 或 ? 以 n-1 作为计数向下递归：

def prod(values,n,result=[]):
    for v in values:
        if n == 1: yield [*result,v]
        else: yield from prod(values,n-1,[*result,v])

获取单个列表的递归排列

Obtaining recursively permutations of a single list

python

list

permutation

subset

combinatorics