Combinations

In mathematics, a combination is a selection of items from a larger set, where the order of the selected items does not matter. Combinations are used in various fields such as combinatorics, probability, and statistics to solve problems involving selecting items from a set without regard to the order.

We can use Binomial Coefficients to solve problems involving combinations. The binomial coefficient C(n, k) represents the number of ways to choose k elements from a set of n elements without regard to the order.

Binomial Coefficient

The binomial coefficient, denoted as C[n][k] represents the number of ways to choose k elements from a set of n elements without regard to the order.

It is used in combinatorics to solve problems where you need to select subsets from larger sets.

C(n,k)=(nk)=n!k!(n−k)!C(n, k) = \binom{n}{k} = \frac{n!}{k!(n - k)!}

Combinations vs Permutations

Combinations and permutations are both ways to select items from a collection, but they differ in how they treat the order of the selected items.

Combinations

A combination is a selection of items from a collection where the order does not matter.

For example, for the same 3 letters (A, B, C) and selecting 2 of them, the combinations are: AB, AC, BC (BA and AB are considered the same, because the order doesn’t matter).

Permutations

A permutation is a selection of items from a collection where the order matters.

For example, for the set {A, B, C}, the permutations of size 2 are: (A, B), (B, A), (A, C), (C, A), (B, C), (C, B)

(A, B) is different from (B, A) in permutations because the order matters.

In general, the number of combinations is less than the number of permutations because combinations do not consider the order of the items.

Python Implementation using built-in itertools module

from itertools import combinations

arr = [1, 2, 3, 4]
comb_length = 2

comb = combinations(arr, comb_length)

for ch in comb:
    print(ch)

Output is:

(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)

Custom Python Implementation

def combinations_backtracking(arr, k):
    result = []
    combination = []

    def backtrack(start):
        if len(combination) == k:
            result.append(combination.copy())
            return

        for i in range(start, len(arr)):
            combination.append(arr[i])
            backtrack(i + 1)
            combination.pop()

    backtrack(0)
    return result

# Example usage:
arr = [1, 2, 3, 4]
k = 2
combinations = combinations_backtracking(arr, k)
print(combinations)

Problems

Related Posts