Skip to content
Tutorial Reference

How to Generate Combinations Up to Size N in Python

Learn how to efficiently generate all combinations of a list up to size N in Python using itertools, including memory-efficient patterns and practical use cases like feature selection.

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)

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

combos = chain.from_iterable(
    combinations(items, r) for r in range(1, max_size + 1)
)

print(list(combos))

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)
    )

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])))

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)))

print("Without empty:", list(subsets(items, include_empty=False)))

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)

features = ['age', 'income', 'location', 'history']

def mock_evaluate(feature_set):
    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}")

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)
Navigation