如何在Python中创建所有可能的元素组合作为列表的列表

Question

如何在Python中创建所有可能的元素组合作为列表的列表

3

假设我有以下列表： data = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'] 如何创建所有可能的三个列表组合，每个组合中没有重复？示例输出将是：

```python [('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'b', 'e'), ..., ('g', 'h', 'i')] ```

[[['a','b','c'],['d','e','f'],['g','h','i']],[['a','b','e'],['c','d','g'],['f','h','i']]...] etc

编辑：代码中不应该重复。例如，如果代码输出 [['a','b','c'],['d','e','f'],['g','h','i']] 那么它不应该输出类似 [['a','b','c'],['g','h','i'],['d','e','f']] 或者 [['c','b','a'],['d','e','f'],['g','h','i']] 的变体。

- West

@PM2Ring 抱歉我没有澄清这一点。如果代码输出[['a','b','c'],['d','e','f'],['g','h','i']]，那么它不应该输出像[['a','b','c'],['g','h','i'],['d','e','f']]或者[['c','b','a'],['d','e','f'],['g','h','i']]这样的变体。谢谢。 - West

那么，返回3组集合是否可以，还是需要将它们放回列表并保持原始顺序？ - abarnert

我仍然不确定我是否正确理解了您的要求。您能告诉我们您期望得到多少结果吗？或者，更好的方法是做2x2版本并详细列出它们吗？ - abarnert

@abarnert 集合也很好。我不确定有多少组合，我只需要所有可能的组合。 - West

4个回答

0

一个显而易见的做法是使用三个嵌套的选择-3循环。(好吧，实际上只需要两个，因为最后一个将从3个中选择3个...)

如果您的输入长度是动态的，我会使用product或递归来完成，但我认为对于3x3的情况，明确循环可能更简单：

def part3s(data):
    data = set(data)
    for c1 in combinations(data, 3):
        for c2 in combinations(data-set(c1), 3):
            yield (c1, c2, data-set(c1)-set(c2))
for part3 in part3s(data):
    print(part3)

- abarnert

运行代码时出现语法错误：'yield'在函数外。 - West

@West 是的，这是一个函数体。如果不够明显，我会编辑以展示如何使用它；抱歉。 - abarnert

这段代码产生了重复，这不是我要找的。例如，输出了 (('d', 'c', 'g'), ('e', 'b', 'a'), {'h', 'i', 'f'}) 和 (('e', 'b', 'a'), ('d', 'c', 'g'), {'h', 'i', 'f'}。 - West

@West 那就是我一直在试图弄清楚你需要1680、560还是280个结果，因为有三到四种不同的方法可以解释“无重复项”，我不确定你想要哪一种。我认为你想要PM2Ring的答案。 - abarnert

当然，我意识到我没有解释清楚，抱歉。PM2Ring的方法几乎是我要找的，但我无法弄清如何将每个列表转换为列表的列表。 - West

0

import itertools
data= ['a','b','c','d','e','f','g','h','i']
d=itertools.permutations(data,9)
for i in d:print(i[:3],i[3:6],i[6:])

- Smart Manoj

我认为原帖作者并不想要所有这些重复，尽管这一点并不明确。 - abarnert

0

输入数据

data= ['a','b','c','d','e','f','g','h','i']

创建所有元素的排列，并将它们分成三个一组。

permutation_list = permutations(data, 3)

创建所有分组元素的列表。

out = []
for i in permutation_list:
    out.append(i)

将列表再次分成3组

def split(out_list, count):
    return [out_list[i::count] for i in range(count)]

result = split(out, int(len(out)/3))

输出：

[[('a', 'b', 'c'), ('d', 'a', 'b'), ('g', 'a', 'b')], [('a', 'b', 'd'), ('d', 'a', 'c'), ('g', 'a', 'c')],.....

- user7313188

这不是 OP 想要的。例如，你的 [('a', 'b', 'c'), ('d', 'a', 'b'), ('g', 'a', 'b')] 没有涵盖从 'a' 到 'i' 的所有字母，并且重复了 'a' 和 'b'。 - PM 2Ring

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- PM 2Ring · Accepted Answer

一种攻击此问题的方法是将其视为精确覆盖问题。正如维基百科所述，解决这类问题的标准方法是使用Knuth的X算法。在其他语言中，可以使用Knuth的“跳跃链接”算法实现。我们可以在Python中做到这一点，但由于没有指针，这有点繁琐。但Ali Assaf已经展示了如何使用Python的dict和set对象执行X算法。

下面的代码执行所需的分区，无重复，保持data字符串中使用的字母顺序。

"""
    Partition a list into equal parts

    Uses Knuth's Algorithm X for the exact cover problem.
    The Algorithm X code, using dicts instead of doubly-linked
    circular lists was written by Ali Assaf.
    See http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
    and http://www.cs.mcgill.ca/~aassaf9/python/sudoku.txt
"""

from itertools import product, combinations

#Algorithm X functions
def solve(X, Y, solution):
    if X:
        c = min(X, key=lambda c: len(X[c]))
        for r in list(X[c]):
            solution.append(r)
            cols = select(X, Y, r)
            yield from solve(X, Y, solution)
            deselect(X, Y, r, cols)
            solution.pop()
    else:
        yield list(solution)

def select(X, Y, r):
    cols = []
    for j in Y[r]:
        for i in X[j]:
            for k in Y[i]:
                if k != j:
                    X[k].remove(i)
        cols.append(X.pop(j))
    return cols

def deselect(X, Y, r, cols):
    for j in reversed(Y[r]):
        X[j] = cols.pop()
        for i in X[j]:
            for k in Y[i]:
                if k != j:
                    X[k].add(i)

#Invert subset collection
def exact_cover(X, Y):
    newX = {j: set() for j in X}
    for i, row in Y.items():
        for j in row:
            newX[j].add(i)
    return newX

#----------------------------------------------------------------------

data = 'abcdefghi'
Y = {''.join(t): t for t in combinations(data, 3)}
X = exact_cover(data, Y)

for i, solution in enumerate(solve(X, Y, []), 1):
    print(i, solution)

output

1 ['aei', 'bgh', 'cdf']
2 ['aei', 'bch', 'dfg']
3 ['aei', 'bcf', 'dgh']
4 ['aei', 'bfh', 'cdg']
5 ['aei', 'bcg', 'dfh']
6 ['aei', 'bdg', 'cfh']
7 ['aei', 'bfg', 'cdh']
8 ['aei', 'bdf', 'cgh']
9 ['aei', 'bdh', 'cfg']
10 ['aei', 'bcd', 'fgh']
11 ['abf', 'cgh', 'dei']
12 ['abf', 'ceh', 'dgi']
13 ['abf', 'dgh', 'cei']
14 ['abf', 'cdh', 'egi']
15 ['abf', 'chi', 'deg']
16 ['abf', 'egh', 'cdi']
17 ['abf', 'ghi', 'cde']
18 ['abf', 'deh', 'cgi']
19 ['abf', 'ehi', 'cdg']
20 ['abf', 'dhi', 'ceg']
21 ['ace', 'bgh', 'dfi']
22 ['ace', 'dgi', 'bfh']
23 ['ace', 'dgh', 'bfi']
24 ['ace', 'dfg', 'bhi']
25 ['ace', 'fgh', 'bdi']
26 ['ace', 'fgi', 'bdh']
27 ['ace', 'ghi', 'bdf']
28 ['ace', 'bdg', 'fhi']
29 ['ace', 'bfg', 'dhi']
30 ['ace', 'bgi', 'dfh']
31 ['ach', 'dfi', 'beg']
32 ['ach', 'dfg', 'bei']
33 ['ach', 'bfi', 'deg']
34 ['ach', 'def', 'bgi']
35 ['ach', 'fgi', 'bde']
36 ['ach', 'efg', 'bdi']
37 ['ach', 'efi', 'bdg']
38 ['ach', 'bfg', 'dei']
39 ['ach', 'bdf', 'egi']
40 ['ach', 'bef', 'dgi']
41 ['afh', 'bei', 'cdg']
42 ['afh', 'dgi', 'bce']
43 ['afh', 'egi', 'bcd']
44 ['afh', 'cei', 'bdg']
45 ['afh', 'cgi', 'bde']
46 ['afh', 'dei', 'bcg']
47 ['afh', 'bdi', 'ceg']
48 ['afh', 'bgi', 'cde']
49 ['afh', 'bci', 'deg']
50 ['afh', 'cdi', 'beg']
51 ['aci', 'deg', 'bfh']
52 ['aci', 'bgh', 'def']
53 ['aci', 'beg', 'dfh']
54 ['aci', 'dgh', 'bef']
55 ['aci', 'dfg', 'beh']
56 ['aci', 'fgh', 'bde']
57 ['aci', 'bdg', 'efh']
58 ['aci', 'efg', 'bdh']
59 ['aci', 'bfg', 'deh']
60 ['aci', 'egh', 'bdf']
61 ['abh', 'dfi', 'ceg']
62 ['abh', 'cef', 'dgi']
63 ['abh', 'cfi', 'deg']
64 ['abh', 'dfg', 'cei']
65 ['abh', 'def', 'cgi']
66 ['abh', 'fgi', 'cde']
67 ['abh', 'efg', 'cdi']
68 ['abh', 'efi', 'cdg']
69 ['abh', 'cfg', 'dei']
70 ['abh', 'cdf', 'egi']
71 ['ahi', 'cdg', 'bef']
72 ['ahi', 'deg', 'bcf']
73 ['ahi', 'ceg', 'bdf']
74 ['ahi', 'beg', 'cdf']
75 ['ahi', 'dfg', 'bce']
76 ['ahi', 'bcg', 'def']
77 ['ahi', 'bdg', 'cef']
78 ['ahi', 'efg', 'bcd']
79 ['ahi', 'bfg', 'cde']
80 ['ahi', 'cfg', 'bde']
81 ['adi', 'cef', 'bgh']
82 ['adi', 'ceg', 'bfh']
83 ['adi', 'bce', 'fgh']
84 ['adi', 'beg', 'cfh']
85 ['adi', 'ceh', 'bfg']
86 ['adi', 'efh', 'bcg']
87 ['adi', 'beh', 'cfg']
88 ['adi', 'efg', 'bch']
89 ['adi', 'bef', 'cgh']
90 ['adi', 'egh', 'bcf']
91 ['acg', 'dfi', 'beh']
92 ['acg', 'bfh', 'dei']
93 ['acg', 'fhi', 'bde']
94 ['acg', 'bfi', 'deh']
95 ['acg', 'efh', 'bdi']
96 ['acg', 'def', 'bhi']
97 ['acg', 'efi', 'bdh']
98 ['acg', 'bdf', 'ehi']
99 ['acg', 'bef', 'dhi']
100 ['acg', 'dfh', 'bei']
101 ['acd', 'bei', 'fgh']
102 ['acd', 'egi', 'bfh']
103 ['acd', 'fhi', 'beg']
104 ['acd', 'bfi', 'egh']
105 ['acd', 'fgi', 'beh']
106 ['acd', 'ghi', 'bef']
107 ['acd', 'efi', 'bgh']
108 ['acd', 'ehi', 'bfg']
109 ['acd', 'bhi', 'efg']
110 ['acd', 'bgi', 'efh']
111 ['aeg', 'cfh', 'bdi']
112 ['aeg', 'bch', 'dfi']
113 ['aeg', 'chi', 'bdf']
114 ['aeg', 'cdh', 'bfi']
115 ['aeg', 'bfh', 'cdi']
116 ['aeg', 'fhi', 'bcd']
117 ['aeg', 'bhi', 'cdf']
118 ['aeg', 'bdh', 'cfi']
119 ['aeg', 'dfh', 'bci']
120 ['aeg', 'dhi', 'bcf']
121 ['abc', 'dfi', 'egh']
122 ['abc', 'dfg', 'ehi']
123 ['abc', 'fgh', 'dei']
124 ['abc', 'fhi', 'deg']
125 ['abc', 'efh', 'dgi']
126 ['abc', 'def', 'ghi']
127 ['abc', 'fgi', 'deh']
128 ['abc', 'efg', 'dhi']
129 ['abc', 'efi', 'dgh']
130 ['abc', 'dfh', 'egi']
131 ['abg', 'dfi', 'ceh']
132 ['abg', 'cfi', 'deh']
133 ['abg', 'chi', 'def']
134 ['abg', 'cei', 'dfh']
135 ['abg', 'fhi', 'cde']
136 ['abg', 'dei', 'cfh']
137 ['abg', 'efi', 'cdh']
138 ['abg', 'ehi', 'cdf']
139 ['abg', 'cdi', 'efh']
140 ['abg', 'dhi', 'cef']
141 ['adf', 'bei', 'cgh']
142 ['adf', 'ceg', 'bhi']
143 ['adf', 'bce', 'ghi']
144 ['adf', 'ceh', 'bgi']
145 ['adf', 'beg', 'chi']
146 ['adf', 'egi', 'bch']
147 ['adf', 'cei', 'bgh']
148 ['adf', 'beh', 'cgi']
149 ['adf', 'ehi', 'bcg']
150 ['adf', 'egh', 'bci']
151 ['agi', 'cfh', 'bde']
152 ['agi', 'cef', 'bdh']
153 ['agi', 'bch', 'def']
154 ['agi', 'bce', 'dfh']
155 ['agi', 'ceh', 'bdf']
156 ['agi', 'cde', 'bfh']
157 ['agi', 'bcf', 'deh']
158 ['agi', 'cdh', 'bef']
159 ['agi', 'bcd', 'efh']
160 ['agi', 'cdf', 'beh']
161 ['abi', 'cfh', 'deg']
162 ['abi', 'cgh', 'def']
163 ['abi', 'ceh', 'dfg']
164 ['abi', 'dgh', 'cef']
165 ['abi', 'cdh', 'efg']
166 ['abi', 'fgh', 'cde']
167 ['abi', 'efh', 'cdg']
168 ['abi', 'egh', 'cdf']
169 ['abi', 'deh', 'cfg']
170 ['abi', 'dfh', 'ceg']
171 ['aeh', 'cdg', 'bfi']
172 ['aeh', 'dgi', 'bcf']
173 ['aeh', 'dfg', 'bci']
174 ['aeh', 'cgi', 'bdf']
175 ['aeh', 'fgi', 'bcd']
176 ['aeh', 'bcg', 'dfi']
177 ['aeh', 'bdg', 'cfi']
178 ['aeh', 'bfg', 'cdi']
179 ['aeh', 'bgi', 'cdf']
180 ['aeh', 'cfg', 'bdi']
181 ['ade', 'cfi', 'bgh']
182 ['ade', 'chi', 'bfg']
183 ['ade', 'fhi', 'bcg']
184 ['ade', 'bfi', 'cgh']
185 ['ade', 'cgi', 'bfh']
186 ['ade', 'fgi', 'bch']
187 ['ade', 'ghi', 'bcf']
188 ['ade', 'bhi', 'cfg']
189 ['ade', 'bgi', 'cfh']
190 ['ade', 'bci', 'fgh']
191 ['afi', 'bgh', 'cde']
192 ['afi', 'cgh', 'bde']
193 ['afi', 'bch', 'deg']
194 ['afi', 'ceh', 'bdg']
195 ['afi', 'dgh', 'bce']
196 ['afi', 'cdh', 'beg']
197 ['afi', 'beh', 'cdg']
198 ['afi', 'deh', 'bcg']
199 ['afi', 'bdh', 'ceg']
200 ['afi', 'egh', 'bcd']
201 ['adh', 'cef', 'bgi']
202 ['adh', 'ceg', 'bfi']
203 ['adh', 'bce', 'fgi']
204 ['adh', 'cfi', 'beg']
205 ['adh', 'bcf', 'egi']
206 ['adh', 'cei', 'bfg']
207 ['adh', 'cgi', 'bef']
208 ['adh', 'bcg', 'efi']
209 ['adh', 'bci', 'efg']
210 ['adh', 'cfg', 'bei']
211 ['abd', 'cfi', 'egh']
212 ['abd', 'chi', 'efg']
213 ['abd', 'egi', 'cfh']
214 ['abd', 'cei', 'fgh']
215 ['abd', 'fhi', 'ceg']
216 ['abd', 'cgi', 'efh']
217 ['abd', 'fgi', 'ceh']
218 ['abd', 'ghi', 'cef']
219 ['abd', 'efi', 'cgh']
220 ['abd', 'ehi', 'cfg']
221 ['acf', 'deg', 'bhi']
222 ['acf', 'bgh', 'dei']
223 ['acf', 'dgi', 'beh']
224 ['acf', 'beg', 'dhi']
225 ['acf', 'dgh', 'bei']
226 ['acf', 'egi', 'bdh']
227 ['acf', 'ghi', 'bde']
228 ['acf', 'bdg', 'ehi']
229 ['acf', 'bgi', 'deh']
230 ['acf', 'egh', 'bdi']
231 ['abe', 'dfi', 'cgh']
232 ['abe', 'dgi', 'cfh']
233 ['abe', 'cfi', 'dgh']
234 ['abe', 'chi', 'dfg']
235 ['abe', 'fhi', 'cdg']
236 ['abe', 'cgi', 'dfh']
237 ['abe', 'fgi', 'cdh']
238 ['abe', 'ghi', 'cdf']
239 ['abe', 'cdi', 'fgh']
240 ['abe', 'dhi', 'cfg']
241 ['adg', 'cfh', 'bei']
242 ['adg', 'cef', 'bhi']
243 ['adg', 'cfi', 'beh']
244 ['adg', 'bcf', 'ehi']
245 ['adg', 'bfh', 'cei']
246 ['adg', 'fhi', 'bce']
247 ['adg', 'bfi', 'ceh']
248 ['adg', 'efh', 'bci']
249 ['adg', 'efi', 'bch']
250 ['adg', 'bef', 'chi']
251 ['agh', 'bei', 'cdf']
252 ['agh', 'dfi', 'bce']
253 ['agh', 'cfi', 'bde']
254 ['agh', 'cei', 'bdf']
255 ['agh', 'bfi', 'cde']
256 ['agh', 'dei', 'bcf']
257 ['agh', 'efi', 'bcd']
258 ['agh', 'bdi', 'cef']
259 ['agh', 'bci', 'def']
260 ['agh', 'cdi', 'bef']
261 ['afg', 'bei', 'cdh']
262 ['afg', 'bce', 'dhi']
263 ['afg', 'ceh', 'bdi']
264 ['afg', 'cde', 'bhi']
265 ['afg', 'cei', 'bdh']
266 ['afg', 'bde', 'chi']
267 ['afg', 'beh', 'cdi']
268 ['afg', 'deh', 'bci']
269 ['afg', 'dei', 'bch']
270 ['afg', 'ehi', 'bcd']
271 ['aef', 'cdg', 'bhi']
272 ['aef', 'dgi', 'bch']
273 ['aef', 'dgh', 'bci']
274 ['aef', 'cdh', 'bgi']
275 ['aef', 'bdg', 'chi']
276 ['aef', 'bdh', 'cgi']
277 ['aef', 'bdi', 'cgh']
278 ['aef', 'cdi', 'bgh']
279 ['aef', 'dhi', 'bcg']
280 ['aef', 'bcd', 'ghi']

请注意，算法X并不一定是找到给定问题解决方案的最有效方法。在许多情况下，更具体的解决方案会有更好的性能表现。