Introduction

Selecting one random combination sounds simple until you define what "fair" means. If you need one subset of size k from n values, every valid k-combination must have the same probability; if you allow any subset size, the probability model changes again.

Define the Combination Space First

There are two common interpretations of this problem:

1. Pick exactly k distinct items from a list of n items.
2. Pick any subset, including the empty subset and the full set.

Those are different problems. For fixed-size combinations, the sample space has n choose k possibilities. For arbitrary subsets, the sample space has 2^n possibilities because each element is either included or excluded.

If you skip this distinction, you can accidentally bias the result. A routine that flips a coin for each element produces a uniform random subset over all subset sizes, but it does not produce a uniform random k-combination.

Uniform Selection for a Fixed Size

For the fixed-size case, the most practical solution is to sample without replacement. In Python, random.sample already does that efficiently.

1import random
2
3def random_combination(values, k):
4    if k < 0 or k > len(values):
5        raise ValueError("k must be between 0 and len(values)")
6    return random.sample(values, k)
7
8colors = ["red", "blue", "green", "yellow", "black"]
9print(random_combination(colors, 3))

This works because every group of k unique positions is equally likely. If the input contains duplicate values and you care about positions rather than value labels, sampling the list directly is still correct. If duplicates should collapse into one logical value, deduplicate before sampling.

For a language without a built-in helper, reservoir-style selection is a good mental model. Walk the array once and decide whether to keep each item while preserving a final sample size of k.

1import random
2
3def random_combination_manual(values, k):
4    if k < 0 or k > len(values):
5        raise ValueError("invalid k")
6
7    chosen = []
8    remaining_to_pick = k
9    remaining_items = len(values)
10
11    for value in values:
12        if remaining_to_pick == 0:
13            break
14
15        pick_probability = remaining_to_pick / remaining_items
16        if random.random() < pick_probability:
17            chosen.append(value)
18            remaining_to_pick -= 1
19
20        remaining_items -= 1
21
22    return chosen

The key invariant is that after each step, the algorithm still has enough remaining items to finish with exactly k picks.

Uniform Selection for Any Subset Size

If every subset is allowed, the simplest correct algorithm is to decide independently for each item whether it is included.

1import random
2
3def random_subset(values):
4    return [value for value in values if random.choice([True, False])]
5
6nums = [1, 2, 3, 4]
7print(random_subset(nums))

This is equivalent to generating a random bit mask. For n elements there are 2^n masks, and each one appears with probability 1 / 2^n.

You can also implement that idea explicitly:

1import random
2
3def random_subset_bitmask(values):
4    mask = random.randrange(1 << len(values))
5    result = []
6
7    for index, value in enumerate(values):
8        if mask & (1 << index):
9            result.append(value)
10
11    return result

The bitmask version is useful when you later need to store or compare the chosen subset compactly.

Complexity and Practical Limits

You do not need to generate all combinations to pick one random combination. That would be catastrophic once n grows.

The fixed-size sampling approach runs in linear time or close to linear time depending on the helper used, and it uses only the memory required for the output. The subset approach is also linear because you inspect each input item once.

The real limit is not time spent generating combinations, but whether your randomness source is appropriate. For simulations, the default pseudo-random generator is usually fine. For security-sensitive selection, use a cryptographically secure generator such as Python's secrets module.

1import secrets
2
3def secure_random_subset(values):
4    return [value for value in values if secrets.randbits(1)]

Common Pitfalls

The most common mistake is shuffling the whole list and taking the first k items when the input contains repeated logical values. That samples positions correctly, but not unique value labels.

Another mistake is generating a random integer between 0 and 2^n - 1 and then filtering down to subsets of size k. That approach wastes work and becomes biased if you "retry until size matches" without thinking through the distribution.

Developers also sometimes confuse combinations with permutations. If order does not matter, ["a", "b"] and ["b", "a"] are the same combination and should not be counted twice.

Finally, avoid materializing all combinations with helpers like itertools.combinations just to pick one random entry. That turns a sampling problem into an enumeration problem.

Summary

• Decide whether you need a fixed-size combination or any subset at all.
• For exactly k items, sample without replacement instead of generating all combinations.
• For arbitrary subsets, include or exclude each element independently.
• Do not enumerate the entire combination space unless the input is tiny.
• Use a secure randomness source only when the selection has security implications.