找到所有排列组合 – 甚至多对一

huangapple
go评论56阅读模式
英文:

Two lists - find all permutations - even multiple to one

问题

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

关键是可以分配多个“number”项（如下面的示例），也可以不分配。

所以这个：

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

会变成这样（列表顺序无关紧要，所以 [1, 2] = [2, 1]）：

[
    "不仅如此"
    {'a': [1], 'b': [2]},
    {'a': [2], 'b': [1]},
    "而且还"
    {'a': [1], 'b': []},
    {'a': [2], 'b': []},
    {'a': [1, 2], 'b': []},
    {'a': [], 'b': [1]},
    {'a': [], 'b': [2]},
    {'a': [], 'b': [1, 2]},

]

或者例如这个：

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

会变成：

[
    {'a': [], 'b': []},
    {'a': [1], 'b': [2]},
    {'a': [1], 'b': [3]},
    {'a': [2], 'b': [1]},
    {'a': [2], 'b': [3]},
    {'a': [3], 'b': [1]},
    {'a': [3], 'b': [2]},
    "而且还"
    {'a': [], 'b': [1]},
    {'a': [], 'b': [1, 2]},
    {'a': [], 'b': [1, 2, 3]},
    {'a': [1], 'b': []},
    {'a': [1], 'b': [2]},
    {'a': [1], 'b': [2, 3]},
    {'a': [1, 2], 'b': []},
    {'a': [1, 2], 'b': [3]},
    {'a': [1, 2, 3], 'b': []},
    {'a': [2], 'b': []},
    {'a': [2], 'b': [1]},
    {'a': [2], 'b': [1, 3]},
    {'a': [2, 3], 'b': []},
    {'a': [2, 3], 'b': [1]},
    "等等..."
]
英文:

I have two lists and I need to find all permutations.

The kicker is that multiple "number" items (as per example below) can be assigned. No assignments are also allowed.

So this:

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

Would become this (the list order doesn't matter, so [1, 2] = [2, 1]:

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

]

Or for example this:

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

Would go something along the lines of:

[
    {'a': [], 'b': []},
    {'a': [1], 'b': [2]},
    {'a': [1], 'b': [3]},
    {'a': [2], 'b': [1]},
    {'a': [2], 'b': [3]},
    {'a': [3], 'b': [1]},
    {'a': [3], 'b': [2]},
    "but also"
    {'a': [], 'b': [1]},
    {'a': [], 'b': [1, 2]},
    {'a': [], 'b': [1, 2, 3]},
    {'a': [1], 'b': []},
    {'a': [1], 'b': [2]},
    {'a': [1], 'b': [2, 3]},
    {'a': [1, 2], 'b': []},
    {'a': [1, 2], 'b': [3]},
    {'a': [1, 2, 3], 'b': []},
    {'a': [2], 'b': []},
    {'a': [2], 'b': [1]},
    {'a': [2], 'b': [1, 3]},
    {'a': [2, 3], 'b': []},
    {'a': [2, 3], 'b': [1]},
    "etc..."
]

Created a separate question for when the list order does matter.

答案1

得分: 3

这将执行你想要的操作：

import itertools

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

    return r

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

    return [f(p, names, numbers) for p in p_iter]

你可以调用get_vals来获得所需的列表。以下是一个小例子：

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

r = get_vals(names, numbers)

for d in r:
    print(d)

这会打印：

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

这里是一个更大的示例：

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

r = get_vals(names, numbers)

for d in r:
    print(d)

这会打印：

{'a': [], 'b': []}
{'a': [3], 'b': []}
{'a': [], 'b': [3]}
{'a': [2], 'b': []}
{'a': [2, 3], 'b': []}
{'a': [2], 'b': [3]}
{'a': [], 'b': [2]}
{'a': [3], 'b': [2]}
{'a': [], 'b': [2, 3]}
{'a': [1], 'b': []}
{'a': [1, 3], 'b': []}
{'a': [1], 'b': [3]}
{'a': [1, 2], 'b': []}
{'a': [1, 2, 3], 'b': []}
{'a': [1, 2], 'b': [3]}
{'a': [1], 'b': [2]}
{'a': [1, 3], 'b': [2]}
{'a': [1], 'b': [2, 3]}
{'a': [], 'b': [1]}
{'a': [3], 'b': [1]}
{'a': [], 'b': [1, 3]}
{'a': [2], 'b': [1]}
{'a': [2, 3], 'b': [1]}
{'a': [2], 'b': [1, 3]}
{'a': [], 'b': [1, 2]}
{'a': [3], 'b': [1, 2]}
{'a': [], 'b': [1, 2, 3]}
英文:

This should do what you want:

import itertools

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

    return r

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

    return [f(p, names, numbers) for p in p_iter]

You can call get_vals to return the desired list. Here's the small example:

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

r = get_vals(names, numbers)

for d in r:
    print(d)

This prints:

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

Here's the larger example:

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

r = get_vals(names, numbers)

for d in r:
    print(d)

This prints:

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

答案2

得分: 2

以下是您要翻译的代码部分：

from itertools import combinations, product

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

perm_list = [list(perm) for perm_len in range(len(numbers)+1) for perm in combinations(numbers, perm_len)]   # generate permutations

perm_dict = [{names[0]: perm1, names[1]: perm2} for perm1, perm2 in product(perm_list, perm_list) if not set(perm1) & set(perm2)]   # get all possible non-overlapping combinations

for perm_combination in perm_dict:
    print(perm_combination)

Output:

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

以下是第二段代码的翻译部分：

```python
from itertools import combinations, product

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

perm_list = [list(perm) for perm_len in range(len(numbers)+1) for perm in combinations(numbers, perm_len)]   # generate permutations

name_perm_list = [perm_list for _ in names]

perm_dict = [{names[i]: perms[i] for i in range(len(names))} for perms in product(*name_perm_list) if len(set().union(*perms)) == sum([len(set(perm)) for perm in perms])]   # get all possible non-overlapping combinations

for perm_combination in perm_dict:
    print(perm_combination)

Output:

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

这些是您提供的代码的翻译部分。

英文:

A better answer was already posted, but this was a good exercise for using itertools and this also works:

from itertools import combinations, product

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

perm_list = [list(perm) for perm_len in range(len(numbers)+1) for perm in combinations(numbers, perm_len)]   # generate permutations

perm_dict = [{names[0]: perm1, names[1]: perm2} for perm1, perm2 in product(perm_list, perm_list) if not set(perm1) & set(perm2)]   # get all possible non-overlapping combinations

for perm_combination in perm_dict:
    print(perm_combination)

Output:

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

Edit: an even less pretty, but functional version that allows for an arbitrary number of names:

from itertools import combinations, product

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

perm_list = [list(perm) for perm_len in range(len(numbers)+1) for perm in combinations(numbers, perm_len)]   # generate permutations

name_perm_list = [perm_list for _ in names]

perm_dict = [{names[i]: perms[i] for i in range(len(names))} for perms in product(*name_perm_list) if len(set().union(*perms)) == sum([len(set(perm)) for perm in perms])]   # get all possible non-overlapping combinations

for perm_combination in perm_dict:
    print(perm_combination)

Output:

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

The overlap check is pretty ugly because I couldn't think of a better way to get the overlap of multiple sets since intersection won't cut it.

答案3

得分: 2

不使用itertools...对于每个数字，将其附加到名称的列表之一：

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

ds = [{name: [] for name in names}]
for number in numbers:
    ds += [
        {k: v[:] + [number] * (k == name)
         for k, v in d.items()}
        for d in ds
        for name in names
    ]

for d in ds:
    print(d)

输出：

{'a': [], 'b': []}
{'a': [1], 'b': []}
{'a': [], 'b': [1]}
{'a': [2], 'b': []}
{'a': [], 'b': [2]}
{'a': [1, 2], 'b': []}
{'a': [1], 'b': [2]}
{'a': [2], 'b': [1]}
{'a': [], 'b': [1, 2]}
{'a': [3], 'b': []}
{'a': [], 'b': [3]}
{'a': [1, 3], 'b': []}
{'a': [1], 'b': [3]}
{'a': [3], 'b': [1]}
{'a': [], 'b': [1, 3]}
{'a': [2, 3], 'b': []}
{'a': [2], 'b': [3]}
{'a': [3], 'b': [2]}
{'a': [], 'b': [2, 3]}
{'a': [1, 2, 3], 'b': []}
{'a': [1, 2], 'b': [3]}
{'a': [1, 3], 'b': [2]}
{'a': [1], 'b': [2, 3]}
{'a': [2, 3], 'b': [1]}
{'a': [2], 'b': [1, 3]}
{'a': [3], 'b': [1, 2]}
{'a': [], 'b': [1, 2, 3]}
英文:

Without itertools... for each number, append it to either name's list:

names = ['a', 'b']
numbers = [1, 2, 3]
ds = [{name: [] for name in names}]
for number in numbers:
ds += [
{k: v[:] + [number] * (k == name)
for k, v in d.items()}
for d in ds
for name in names
]
for d in ds:
print(d)

Output:

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

huangapple
  • 本文由 发表于 2023年3月4日 00:35:32
  • 转载请务必保留本文链接：https://go.coder-hub.com/75629666.html
  • permutation
  • python
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定