0
# Combinatorics
1
2
Functions for generating permutations, combinations, and related structures.
3
4
## Capabilities
5
6
### Basic Combinatorics
7
8
Generate combinations and permutations with various constraints.
9
10
```python { .api }
11
def powerset(iterable):
12
"""
13
Generate powerset of iterable (all possible subsets).
14
15
Args:
16
iterable: Input iterable
17
18
Returns:
19
Iterator of tuples representing all subsets
20
"""
21
22
def distinct_combinations(iterable, r):
23
"""
24
Generate combinations of distinct items only.
25
26
Args:
27
iterable: Input iterable
28
r: Length of combinations
29
30
Returns:
31
Iterator of r-tuples with distinct items only
32
"""
33
34
def distinct_permutations(iterable, r=None):
35
"""
36
Generate permutations of distinct items only.
37
38
Args:
39
iterable: Input iterable
40
r: Length of permutations (None for full length)
41
42
Returns:
43
Iterator of r-tuples representing distinct permutations
44
"""
45
```
46
47
**Usage Examples:**
48
49
```python
50
from more_itertools import powerset, distinct_combinations, distinct_permutations
51
52
# Powerset
53
ps = list(powerset([1, 2, 3]))
54
# Result: [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
55
56
# Distinct combinations
57
dc = list(distinct_combinations([1, 1, 2], 2))
58
# Result: [(1, 2)] (removes duplicate (1, 1))
59
60
# Distinct permutations
61
dp = list(distinct_permutations([1, 1, 2]))
62
# Result: [(1, 1, 2), (1, 2, 1), (2, 1, 1)]
63
```
64
65
### Set Operations
66
67
Specialized combinatorics for sets and partitions.
68
69
```python { .api }
70
def powerset_of_sets(iterable):
71
"""
72
Generate powerset where each subset is a frozenset.
73
74
Args:
75
iterable: Input iterable
76
77
Returns:
78
Iterator of frozensets representing all subsets
79
"""
80
81
def set_partitions(iterable, k=None):
82
"""
83
Generate all set partitions of iterable.
84
85
Args:
86
iterable: Input iterable to partition
87
k: Number of parts (None for all possible)
88
89
Returns:
90
Iterator of set partitions (each partition is tuple of frozensets)
91
"""
92
93
def partitions(n, m=None):
94
"""
95
Generate integer partitions of n.
96
97
Args:
98
n: Integer to partition
99
m: Maximum part size (None for unlimited)
100
101
Returns:
102
Iterator of tuples representing integer partitions
103
"""
104
```
105
106
### Cyclic and Circular Operations
107
108
Functions for cyclic arrangements and circular shifts.
109
110
```python { .api }
111
def circular_shifts(iterable):
112
"""
113
Generate all circular shifts of iterable.
114
115
Args:
116
iterable: Input iterable to shift
117
118
Returns:
119
Iterator of tuples representing all circular shifts
120
"""
121
122
def derangements(iterable, r=None):
123
"""
124
Generate all derangements (permutations with no fixed points).
125
126
Args:
127
iterable: Input iterable
128
r: Length of derangements (None for full length)
129
130
Returns:
131
Iterator of derangement tuples
132
"""
133
```
134
135
**Usage Examples:**
136
137
```python
138
from more_itertools import circular_shifts, partitions
139
140
# Circular shifts
141
shifts = list(circular_shifts([1, 2, 3]))
142
# Result: [(1, 2, 3), (2, 3, 1), (3, 1, 2)]
143
144
# Integer partitions of 4
145
parts = list(partitions(4))
146
# Result: [(4,), (3, 1), (2, 2), (2, 1, 1), (1, 1, 1, 1)]
147
```
148
149
### Product Operations
150
151
Cartesian product variations and outer products.
152
153
```python { .api }
154
def gray_product(*iterables):
155
"""
156
Cartesian product in Gray code order.
157
158
Args:
159
*iterables: Iterables to take product of
160
161
Returns:
162
Iterator of tuples in Gray code order
163
"""
164
165
def outer_product(func, xs, ys):
166
"""
167
Compute outer product using binary function.
168
169
Args:
170
func: Binary function to apply
171
xs: First iterable
172
ys: Second iterable
173
174
Returns:
175
Iterator of outer product results
176
"""
177
178
def partial_product(*iterables):
179
"""
180
Generate partial products of iterables.
181
182
Args:
183
*iterables: Iterables to take partial products of
184
185
Returns:
186
Iterator of partial product tuples
187
"""
188
```
189
190
### Indexed Combinatorics
191
192
Functions that work with combinatorial indices.
193
194
```python { .api }
195
def combination_index(element, iterable):
196
"""
197
Get lexicographic index of combination.
198
199
Args:
200
element: Combination tuple
201
iterable: Source iterable
202
203
Returns:
204
Index of combination in lexicographic order
205
"""
206
207
def combination_with_replacement_index(element, iterable):
208
"""
209
Get index of combination with replacement.
210
211
Args:
212
element: Combination tuple (with replacement)
213
iterable: Source iterable
214
215
Returns:
216
Index in lexicographic order
217
"""
218
219
def permutation_index(element, iterable):
220
"""
221
Get lexicographic index of permutation.
222
223
Args:
224
element: Permutation tuple
225
iterable: Source iterable
226
227
Returns:
228
Index of permutation in lexicographic order
229
"""
230
231
def product_index(element, *iterables, repeat=1):
232
"""
233
Get index of element in Cartesian product.
234
235
Args:
236
element: Product tuple
237
*iterables: Source iterables
238
repeat: Number of repetitions
239
240
Returns:
241
Index in product ordering
242
"""
243
```
244
245
### Nth Combinatorial Elements
246
247
Generate specific combinatorial elements by index.
248
249
```python { .api }
250
def nth_combination(iterable, r, index):
251
"""
252
Get nth combination in lexicographic order.
253
254
Args:
255
iterable: Source iterable
256
r: Combination length
257
index: Index of desired combination
258
259
Returns:
260
Tuple representing nth combination
261
"""
262
263
def nth_permutation(iterable, r, index):
264
"""
265
Get nth permutation in lexicographic order.
266
267
Args:
268
iterable: Source iterable
269
r: Permutation length
270
index: Index of desired permutation
271
272
Returns:
273
Tuple representing nth permutation
274
"""
275
276
def nth_product(index, *args):
277
"""
278
Get nth element of Cartesian product by index.
279
280
Args:
281
index: Index of desired element
282
*args: Source iterables for product
283
284
Returns:
285
Tuple representing nth product element
286
"""
287
288
def nth_combination_with_replacement(iterable, r, index):
289
"""
290
Get nth combination with replacement.
291
292
Args:
293
iterable: Source iterable
294
r: Combination length
295
index: Index of desired combination
296
297
Returns:
298
Tuple representing nth combination with replacement
299
"""
300
```
301
302
### Random Combinatorics
303
304
Generate random combinatorial selections.
305
306
```python { .api }
307
def random_product(*iterables, repeat=1):
308
"""
309
Generate random element from Cartesian product.
310
311
Args:
312
*iterables: Source iterables
313
repeat: Number of repetitions
314
315
Returns:
316
Random tuple from product
317
"""
318
319
def random_permutation(iterable, r=None):
320
"""
321
Generate random permutation.
322
323
Args:
324
iterable: Source iterable
325
r: Permutation length (None for full length)
326
327
Returns:
328
Random permutation tuple
329
"""
330
331
def random_combination(iterable, r):
332
"""
333
Generate random combination.
334
335
Args:
336
iterable: Source iterable
337
r: Combination length
338
339
Returns:
340
Random combination tuple
341
"""
342
343
def random_combination_with_replacement(iterable, r):
344
"""
345
Generate random combination with replacement.
346
347
Args:
348
iterable: Source iterable
349
r: Combination length
350
351
Returns:
352
Random combination tuple (with replacement)
353
"""
354
```
355
356
**Usage Examples:**
357
358
```python
359
from more_itertools import nth_combination, random_combination
360
361
# Get 3rd combination of length 2 from [1,2,3,4]
362
combo = nth_combination([1, 2, 3, 4], 2, 3)
363
# Result: (2, 4)
364
365
# Random combination
366
import random
367
random.seed(42)
368
rand_combo = random_combination([1, 2, 3, 4, 5], 3)
369
# Result: Random 3-element combination
370
```