Category Archives: Combinatorics

Basics of Combinations

First make sure to read the basics of permutations. So what’s the different between permutations and combinations? Suppose we have set A = {a,b,c,d,e}. A permutation of that set could be abc, and another permutation could be acb. In other words, a permutation is an arrangement of the objects of set A, where order matters. […]

Basics of Permutations

In how many ways can you arrange a group of 4 items? Most people (well, programmers at least) know the answer for that is 24, which is 4!. But what about the more generic case where you have n items and want to permutate only k of them at a time, how many permutations are […]

Generating Permutations in C++

Suppose you have the following set: {0,1,2}. How do you generate all the possible permutations of such set? One possible approach is to use recursion. First we need to break the problem into smaller sub-problems. This could be done by splitting the set into two parts. We keep the right side fixed, and then find […]

Powerset Algorithm in C++

A powerset of a given set is the combination of all subsets, including the empty subset and the set itself. Suppose we have the following set: {1,2,3}. Its powerset would be: {1,2,3} {1,2} {1,3} {2,3} {1} {2} {3} Creating an algorithm to generate a powerset is not trivial. The first idea you can use is […]

Sets, Sequences and Tuples

If you are not sure about the differences between sets, sequences and tuples, here they are: Sequences: A sequence is an ordered list of elements, which can also be infinite (e.g., the sequence composed of the real numbers). Since order of elements matter, the sequence (1,2,3) is different from the sequence (1,3,2) or from the […]