Permutations and Combinations
sal/algo/perm.h
| perm | indexed permutation of a sequence |
| allperms | all permutations of a sequence |
| allperms_distinct | all distinct permutations of a sequence |
| combine | all pairwise combinations using given operator |
| count_combos | number of ways to reach a sum given a set of values (change-making problem) |
Permutation ¶
Declaration
template <typename Indexable>
void perm(Indexable& s, unsigned long long k);Parameters
| s | any indexable sequence - operator[] is defined. |
| k | permutation index - from 0 to s.size()! - 1 |
Example
std::string word {"Hello"};
perm(word, 0);
std::cout << word;
// word becomes "oHell"Discussion
Perm modifies the sequence without returing. Θ(s.size()) time complexity with no comparisons,
but the permutation indices do not correspond to any order. (for lexicographic ordered permutation,
such as generating numbers in order, use std::next_permutation or std::prev_permutation). The algorithm has high parallelism as the interval [0,s.size()!-1] could be arbitrarily divided
and run on separate cores.
All Permutations ¶
Declaration
template <typename Indexable>
std::vector<Indexable> allperms(const Indexable& s);
template <typename Indexable>
std::set<Indexable> allperms_distinct(const Indexable& s);Parameters
| s | any indexable sequence - operator[] is defined. |
Example
std::string word {"Hello"};
allperms(words);
// vector<std::string> (120 permutations of "Hello")
allperms_distinct(words);
// set<std::string> (60 distinct permutations of "Hello")Discussion
A simple wrapper for perm above; generating
permutations and storing them in std::vector and std::set for distinct.
Combinations ¶
Declaration
template <typename Iter, typename Op>
set<Iter_value<Iter>> combine(Iter start, Iter end, Op op);
template <typename Iter, typename Op, typename Pred>
set<Iter_value<Iter>> combine(Iter start, Iter end, Op op, Pred pred);
// overloads for containers
template <typename Container, typename Op>
set<typename Container::value_type> combine(Container& c, Op op);
template <typename Container, typename Op, typename Pred>
set<typename Container::value_type> combine(Container& c, Op op, Pred pred);Parameters
| op | callable object - val operator()(val, val) is defined |
| prep | filtering object - bool operator()(val, val) is defined to filter out combinations |
Example
std::vector<int> ints {1,2,3,4,5,6};
combine(ints, <a href="int a, int b"></a>{return a + b;});// set<int> 2 3 4 5 6 7 8 9 10 11 12 handshake by adding
combine(ints,
<a href="int a, int b"></a>{return a + b;}, <a href="int a, int b"></a>{return (a & 1) && (b & 1);});// set<int> 2 4 6 8 10 handshake by adding odd elementsDiscussion
Functions taking iterators are generally more memory efficient and conforms to the style of the C++ standard library. Note that the filtering predicate filters on the combination of 2 elements, which gives more freedom such as accepting when the first element is odd and second element is even.
Counting Combinations ¶
Declaration
template <typename T>
size_t count_combos(const vector<T>& vals, T sum);Parameters
| vals | sequence of usable values in ascending order of value |
| sum | target to reach by summing up elements of vals |
Example
std::vector<int> coins {1, 2, 5, 10, 20, 50, 100, 200};
count_combos(coins, 200);
// size_t 73682 (ways to sum up to 200 using coins)Discussion
Dynamic programming is used with O(vals.size() * sum) work.
The change-making problem is a classic situation to use this algorithm -
how many ways can you make a certain amount of change given certain coins (unlimited amount of each).