Permutation and combinations functions.
These follow a for_each style: The algorithm calls a user supplied function object (functor) for each combination/permutation in the sequence: f(begin, end). That functor can maintain state. The sequence need not be sorted, nor even contain unique objects. The algorithms do not consider the value of the sequence elements at all. That is, the element type need not support LessThanComparable nor EqualityComparable. Furthermore the algorithms follow three additional rules:
On normal (non-exceptional) completion, the sequence is always left in the original order.
The functor is always called with (first, mid). This enables the functor to also access the elements not in the sequence if it is aware of the sequence: (mid, last). This can come in handy when dealing with nested combination/permutation problems where for each permutation you also need to compute combinations and/or permutations on those elements not selected.
The functor should return true or false: true if the functor wishes to break out of the for_each_ loop, and otherwise false.
Each of the functions return the number of combinations or zero in case of wrong input or overflow.
template <class T, class Functor> uint64 ForEachPermutation(T &data, int mid, Functor f)
Repeatedly permutes the range [data, data.end()) such that the range [data, mid) represents each permutation of the values in [data, data.end()) taken distance (data, mid) at a time.
For each permutation calls f(data, mid). On each call, the range [mid, data.end()) holds the values not in the current permutation. If f returns true then returns immediately without permuting the sequence any further. Otherwise, after the last call to f, and prior to returning, the range [data, data.end()) is restored to its original order. [Note: If f always returns false it is called CountEachPermutation(data, mid) times]
Returns: f.
template <class T, class Functor> uint64 ForEachPermutation(T &data, Functor f)
Repeatedly permutes the range [data, data.end()).
For each permutation calls f(data, data.end()).
If f returns true then returns immediately without permuting the sequence any further. Otherwise, after the last call to f, and prior to returning, the range [data, data.end()) is restored to its original order. [Note: If f always returns false it is called CountEachPermutation(data) times]
Returns: f.
template <class T, class Functor> uint64 ForEachReversiblePermutation(T &data, int mid, Functor f)
Repeatedly permutes the range [data, data.end()) such that the range [data, mid) represents each permutation of the values in [data, data.end()) taken distance (data, mid) at a time, except that f is never called with the reverse of a permutation which has been previously called.
For each permutation calls f(data, mid). On each call, the range [mid, data.end()) holds the values not in the current permutation. If f returns true then returns immediately without permuting the sequence any further. Otherwise, after the last call to f, and prior to returning, the range [data, data.end()) is restored to its original order. [Note: If f always returns false it is called CountEachReversiblePermutation(data, mid) times]
Returns: f.
template <class T, class Functor> uint64 ForEachReversiblePermutation(T &data, Functor f)
Repeatedly permutes the range [data, data.end()), except that f is never called with the reverse of a permutation which has been previously called.
For each permutation calls f(data, data.end()).
If f returns true then returns immediately without permuting the sequence any further. Otherwise, after the last call to f, and prior to returning, the range [data, data.end()) is restored to its original order. [Note: If f always returns false it is called CountEachReversiblePermutation(data) times]
Returns: f.
template <class T, class Functor> uint64 ForEachCircularPermutation(T &data, int mid, Functor f)
Repeatedly permutes the range [data, data.end()) such that the range [data, mid) represents each permutation of the values in [data, data.end()) taken distance (data, mid) at a time, except that f is never called with a circular permutation which has been previously called.
For each permutation calls f(data, mid). On each call, the range [mid, data.end()) holds the values not in the current permutation. If f returns true then returns immediately without permuting the sequence any further. Otherwise, after the last call to f, and prior to returning, the range [data, data.end()) is restored to its original order. [Note: If f always returns false it is called CountEachCircularPermutation(data, mid) times]
Returns: f.
template <class T, class Functor> uint64 ForEachCircularPermutation(T &data, Functor f)
Repeatedly permutes the range [data, data.end()), except that f is never called with a circular permutation which has been previously called.
For each permutation calls f(data, data.end()).
If f returns true then returns immediately without permuting the sequence any further. Otherwise, after the last call to f, and prior to returning, the range [data, data.end()) is restored to its original order. [Note: If f always returns false it is called CountEachCircularPermutation(data) times]
Returns: f.
template <class T, class Functor> uint64 ForEachReversibleCircularPermutation(T &data, int mid, Functor f)
Repeatedly permutes the range [data, data.end()) such that the range [data, mid) represents each permutation of the values in [data, data.end()) taken distance (data, mid) at a time, except that f is never called with a circular permutation which has been previously called, or the reverse of that permutation.
For each permutation calls f(data, mid). On each call, the range [mid, data.end()) holds the values not in the current permutation. If f returns true then returns immediately without permuting the sequence any further. Otherwise, after the last call to f, and prior to returning, the range [data, data.end()) is restored to its original order. [Note: If f always returns false it is called CountEachCircularPermutation(data, mid) times]
Returns: f.
template <class T, class Functor> uint64 ForEachReversibleCircularPermutation(T &data, Functor f)
Repeatedly permutes the range [data, data.end()), except that f is never called with a circular permutation which has been previously called, or the reverse of that permutation.
For each permutation calls f(data, data.end()).
If f returns true then returns immediately without permuting the sequence any further. Otherwise, after the last call to f, and prior to returning, the range [data, data.end()) is restored to its original order. [Note: If f always returns false it is called CountEachReversibleCircularPermutation(data) times]
Returns: f.
template <class T, class Functor> uint64 ForEachCombination(T &data, int mid, Functor f)
Repeatedly permutes the range [data, data.end()) such that the range [data, mid) represents each combination of the values in [data, data.end()) taken distance (data, mid) at a time.
For each permutation calls f(data, mid). On each call, the range [mid, data.end()) holds the values not in the current permutation. If f returns true then returns immediately without permuting the sequence any further. Otherwise, after the last call to f, and prior to returning, the range [data, data.end()) is restored to its original order. [Note: If f always returns false it is called CountEachCombination(data, mid) times]
Returns: f.
template <class T, class Functor> uint64 ForEachCombination(T &data, Functor f)
Repeatedly combines the range [data, data.end()).
For each permutation calls f(data, data.end()).
If f returns true then returns immediately without permuting the sequence any further. Otherwise, after the last call to f, and prior to returning, the range [data, data.end()) is restored to its original order. [Note: If f always returns false it is called CountEachReversibleCircularPermutation(data) times]
Returns: f.
template <class T> uint64 CountEachPermutation(const T &data, int mid)
Returns CountEachPermutation(std::distance(data, mid), std::distance(mid, data.end())) .
template <class T> uint64 CountEachPermutation(const T &data)
Returns CountEachPermutation(std::distance(data, data.end()), std::distance(data, data.end()))
template <class T> uint64 CountEachReversiblePermutation(const T &data, int mid)
Returns CountEachReversiblePermutation(std::distance(data, mid), std::distance(mid, data.end())) .
template <class T> uint64 CountEachReversiblePermutation(const T &data)
Returns CountEachReversiblePermutation(std::distance(data, data.end()), std::distance(data, data.end()))
template <class T> uint64 CountEachCircularPermutation(const T &data, int mid)
Returns CountEachCircularPermutation(std::distance(data, mid), std::distance(mid, data.end())) .
template <class T> uint64 CountEachCircularPermutation(const T &data)
Returns CountEachCircularPermutation(std::distance(data, data.end()), std::distance(data, data.end()))
template <class T> uint64 CountEachReversibleCircularPermutation(const T &data, int mid)
Returns CountEachReversibleCircularPermutation(std::distance(data, mid), std::distance(mid, data.end())) .
template <class T> uint64 CountEachReversibleCircularPermutation(const T &data)
Returns CountEachReversibleCircularPermutation(std::distance(data, data.end()), std::distance(data, data.end()))
template <class T> uint64 CountEachCombinationPermutation(const T &data, int mid)
Returns CountEachCombinationPermutation(std::distance(data, mid), std::distance(mid, data.end())) .
template <class T> uint64 CountEachCombinationPermutation(const T &data)
Returns CountEachCombinationPermutation(std::distance(data, data.end()), std::distance(data, data.end()))
template <class UInt> UInt CountEachPermutation(UInt d1, UInt d2)
Returns (d1 + d2!)/d2!.
If the computed value is not representable in the type UInt, returns 0.
If d1 < UInt(0) or d2 < UInt(0), returns 0.
template <class UInt> UInt CountEachReversiblePermutation(UInt d1, UInt d2)
Returns: If d1 <= 1 returns (d1 + d2)!/d2!. Else returns (d1 + d2)!/(2*d2!).
If the computed value is not representable in the type UInt, returns 0.
If d1 < UInt(0) or d2 < UInt(0), returns 0.
template <class UInt> UInt CountEachCircularPermutation(UInt d1, UInt d2)
If d1 == 0 returns 1. Else returns (d1 + d2)!/(d1*d2!).
If the computed value is not representable in the type UInt, returns 0.
If d1 < UInt(0) or d2 < UInt(0), returns 0.
template <class UInt> UInt CountEachReversibleCircularPermutation(UInt d1, UInt d2)
If d1 == 0 returns 1. Else if d1<= 2 returns (d1 + d2)!/(d1*d2!). Else returns (d1+ d2)!/(2*d1*d2!).
If the computed value is not representable in the type UInt, returns 0.
If d1 < UInt(0) or d2 < UInt(0), returns 0.
template <class UInt> UInt CountEachCombination(UInt d1, UInt d2)
Returns: (d1 + d2)!/(d1!*d2!).
If the computed value is not representable in the type UInt, returns 0.
If d1 < UInt(0) or d2 < UInt(0), returns 0.
|