How to Generate Combinations Up to Size N in Python

When you need all possible subgroups of a list, such as pairs, triples, or any size up to N, Python's itertools module provides efficient, production-ready solutions.

This guide covers standard approaches, memory-efficient patterns, and practical applications for combinatorial generation.

Using itertools.combinations (Standard Approach)

To get all combinations up to size N, iterate through each length from 1 to N:

from itertools import combinations

items = ['A', 'B', 'C']
max_size = 2

results = []
for r in range(1, max_size + 1):
    for combo in combinations(items, r):
        results.append(combo)

print(results)
# [('A',), ('B',), ('C',), ('A', 'B'), ('A', 'C'), ('B', 'C')]

note

combinations() returns tuples in lexicographic order based on input position. Elements are not repeated within a single combination.

Using chain.from_iterable (Memory Efficient)

For cleaner code and better memory efficiency, chain the iterators into a single lazy stream:

from itertools import combinations, chain

items = [1, 2, 3]
max_size = 2

# Creates a single iterator that yields all combinations
combos = chain.from_iterable(
    combinations(items, r) for r in range(1, max_size + 1)
)

print(list(combos))
# [(1,), (2,), (3,), (1, 2), (1, 3), (2, 3)]

Why Use chain.from_iterable?

This pattern processes elements lazily, yielding one combination at a time. For large datasets, this prevents memory exhaustion since all combinations are never held in memory simultaneously.

Creating a Reusable Function

Wrap the logic in a function for cleaner code:

from itertools import combinations, chain

def combinations_up_to_n(items, max_size):
    """Generate all combinations from size 1 to max_size."""
    return chain.from_iterable(
        combinations(items, r) for r in range(1, max_size + 1)
    )

# Usage
items = ['red', 'green', 'blue']

for combo in combinations_up_to_n(items, 2):
    print(combo)

Output:

('red',)
('green',)
('blue',)
('red', 'green')
('red', 'blue')
('green', 'blue')

Generating the Power Set

When you generate combinations up to the full length of the list (including the empty set), you get the power set (all possible subsets):

from itertools import combinations, chain

def power_set(iterable):
    """Generate all subsets including empty set."""
    items = list(iterable)
    return chain.from_iterable(
        combinations(items, r) for r in range(len(items) + 1)
    )

print(list(power_set([1, 2, 3])))
# [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

Power Set Size

The power set of n elements contains 2^n subsets. For a list of 20 items, that's over 1 million combinations. Use generators to handle large sets.

Including vs Excluding Empty Set

Depending on your use case, you may or may not want the empty combination:

from itertools import combinations, chain

def subsets(items, include_empty=False):
    """Generate subsets with optional empty set."""
    start = 0 if include_empty else 1
    items = list(items)
    return chain.from_iterable(
        combinations(items, r) for r in range(start, len(items) + 1)
    )

items = ['a', 'b']

print("With empty:", list(subsets(items, include_empty=True)))
# With empty: [(), ('a',), ('b',), ('a', 'b')]

print("Without empty:", list(subsets(items, include_empty=False)))
# Without empty: [('a',), ('b',), ('a', 'b')]

Practical Example: Feature Selection

A common use case is testing combinations of features in machine learning:

from itertools import combinations, chain

def evaluate_feature_combinations(features, max_features, evaluate_fn):
    """Test all feature combinations up to max_features."""
    results = []
    
    for combo in chain.from_iterable(
        combinations(features, r) for r in range(1, max_features + 1)
    ):
        score = evaluate_fn(combo)
        results.append((combo, score))
    
    return sorted(results, key=lambda x: x[1], reverse=True)

# Example usage
features = ['age', 'income', 'location', 'history']

def mock_evaluate(feature_set):
    # Simulate model accuracy
    return len(feature_set) * 0.1 + 0.5

best_combinations = evaluate_feature_combinations(features, 3, mock_evaluate)
print("Top 3 feature sets:")
for combo, score in best_combinations[:3]:
    print(f"  {combo}: {score:.2f}")

Output:

Top 3 feature sets:
  ('age', 'income', 'location'): 0.80
  ('age', 'income', 'history'): 0.80
  ('age', 'location', 'history'): 0.80

Counting Combinations Without Generating

To count combinations without generating them, use the mathematical formula:

from math import comb

def count_combinations_up_to_n(num_items, max_size):
    """Count total combinations without generating them."""
    return sum(comb(num_items, r) for r in range(1, max_size + 1))

items = 10
max_size = 3

total = count_combinations_up_to_n(items, max_size)
print(f"Total combinations: {total}")  
# Total combinations: 175

tip

Use math.comb() (Python 3.8+) to calculate combination counts before generating them. This helps estimate memory requirements and processing time.

Summary

Method	Syntax	Memory Usage
Nested loop	for r in range: for c in combinations	High (stores all)
chain.from_iterable	chain.from_iterable(combinations(...) for r in range)	Low (lazy)
List comprehension	[c for r in range for c in combinations]	High (stores all)

Best Practice

Use the chain.from_iterable pattern for combination generation. It is the idiomatic Python approach for flattening nested iterators and scales efficiently for large combinatorial tasks. Only convert to a list when you need random access or multiple iterations.