# 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

Parameters

s | any indexable sequence - `operator[]` is defined. |

k | permutation index - from 0 to s.size()! - 1 |

Example

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

Parameters

s | any indexable sequence - `operator[]` is defined. |

Example

Discussion

A simple wrapper for `perm`

above; generating
permutations and storing them in `std::vector`

and `std::set`

for distinct.

### Combinations ¶

Declaration

Parameters

op | callable object - `val operator()(val, val)` is defined |

prep | filtering object - `bool operator()(val, val)` is defined to filter out combinations |

Example

Discussion

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

Parameters

vals | sequence of usable values in ascending order of value |

sum | target to reach by summing up elements of vals |

Example

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