两个列表 - 找到所有排列 - 偶数对一 - 第 2 轮

Question

我之前问过这个问题，但事情发生了变化，所以新问题是有序的。

---

我有两个列表，我需要找到所有排列。

关键是可以分配多个“数字”项目（如下例所示）。也不允许分配。

所以这个：

names = ['a', 'b']
numbers = [1, 2]

会变成这样：

[
    "not only this"
    {'a': [1], 'b': [2]},
    {'a': [2], 'b': [1]},
    "but also"
    {'a': [], 'b': []},
    {'a': [1], 'b': []},
    {'a': [2], 'b': []},
    {'a': [1, 2], 'b': []},
    {'a': [2, 1], 'b': []},
    {'a': [], 'b': [1]},
    {'a': [], 'b': [2]},
    {'a': [], 'b': [1, 2]},
    {'a': [], 'b': [2, 1]},
]

与我之前的问题不同的是，在这种情况下，列表顺序确实很重要，所以

[1, 2] != [2, 1]

- 这两种情况都需要包含。

---

此外，上面的列表仅用于说明目的，因为在实际场景中我将使用类：

class sample_class():
    def __init__(self, parameter_1, parameter_2):
        self.parameter_1 = parameter_1
        self.parameter_2 = parameter_2
        
first_group_example_list = [sample_class(x, x+1) for x in range(2)]
second_group_example_list = [sample_class(x+5, x+5+1) for x in range(2)]

---

现在，由于排列的数量非常快地变得非常高，速度就是王道。不确定与 int 列表相比使用类是否对速度有任何影响，但我怀疑是这样，所以如果有任何好的做法，请告诉我。

不确定它是否对速度/内存有任何影响，但由于列表是有序的，我正在考虑在生成排列时使用元素索引，而不是类本身，并且仅在随后的中拉取实际的类实例加工步骤。

---

编辑：让我们不要使类复杂化并坚持使用名称和数字（只要解决方案不关心两个输入列表是什么类型（整数或字符串））。我会弄清楚剩下的，希望，我去。

---

EDIT2：HERE是将计算“排列”数量的解决方案。

import math

numbers = 6 # length of numbers list
names = 7 # length of names list

result = 0
for j in range(numbers + 1):
    result += math.factorial(j + names - 1) / (math.factorial(j) * math.factorial(numbers - j))

result *= math.factorial(numbers) / math.factorial(names - 1)

print(result) # number of "permutations"

Answer 1

这是一个快速的解决方案。请注意，它不进行任何搜索 - 它只是推出解决方案：

import itertools

def perm_lists(d, names, ix):
    if ix == len(names):
        yield d.copy()
        return

    name = names[ix]
    for m in itertools.permutations(d[name]):
        d[name] = m
        yield from perm_lists(d, names, ix+1)

def f(p, names, numbers):
    d = {name : [] for name in names}
    for i, j in enumerate(p):
        if j >= 0:
            d[names[j]].append(numbers[i])

    yield from perm_lists(d, names, 0)

def val_gen(names, numbers):
    p_iter = itertools.product(range(-1, len(names)), repeat=len(numbers))

    for p in p_iter:
        yield from f(p, names, numbers)

这实现了一个生成器，因此如果您只想遍历值，则不必支付整个顶级列表的成本，但如果需要，您当然可以将其转换为列表。

另请注意，这使用元组代替值列表。这些比列表更节省内存，并且从实现中自然脱落，但如果需要，将它们转换为列表是微不足道的。

举个例子：

names = ['a', 'b']
numbers = [1, 2]

for d in val_gen(names, numbers):
    print(d)

这会产生：

{'a': (), 'b': ()}
{'a': (2,), 'b': ()}
{'a': (), 'b': (2,)}
{'a': (1,), 'b': ()}
{'a': (1, 2), 'b': ()}
{'a': (2, 1), 'b': ()}
{'a': (1,), 'b': (2,)}
{'a': (), 'b': (1,)}
{'a': (2,), 'b': (1,)}
{'a': (), 'b': (1, 2)}
{'a': (), 'b': (2, 1)}

如果您希望值列表是列表而不是元组，只需更改：

d[name] = m

至：

d[name] = list(m)

在

perm_lists

。这将产生：

{'a': [], 'b': []}
{'a': [2], 'b': []}
{'a': [], 'b': [2]}
{'a': [1], 'b': []}
{'a': [1, 2], 'b': []}
{'a': [2, 1], 'b': []}
{'a': [1], 'b': [2]}
{'a': [], 'b': [1]}
{'a': [2], 'b': [1]}
{'a': [], 'b': [1, 2]}
{'a': [], 'b': [2, 1]}

如果您想创建完整的顶级列表，而不是使用生成器对其进行迭代，您可以使用：

full_list = list(val_gen(names, numbers))

我建议做一些计时实验。我相信这在用于大量数据时会很快。