Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Factoradic permutation generator (http://en.wikipedia.org/wiki/Factorial_number_system)
#include <iostream>
#include <list>
#include <algorithm>
#include <string>
#include <sstream>
std::string getFactoradic(unsigned int n) {
std::vector<unsigned long> factos ={1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 8717829120};
// Just cover the case when n is either equal to 0 or 1, if negative also return '0'
if (n-- <= 1) return std::string("0");
size_t elements = factos.size();
size_t i = 0;
for (; i < elements; ++i) if (factos[i] > n) break;
std::stringstream str;
while (--i > 0) {
str << n / factos[i];
n %= factos[i];
}
str << n << '0';
return str.str();
}
template <typename T>
void printPermutation(int index, const std::list<T>& elements) {
std::string factoradic = getFactoradic(index);
std::list<T> copy(elements);
if (elements.size() > factoradic.size())
factoradic.insert(0, elements.size() - factoradic.size(), '0');
size_t size = factoradic.size();
for (size_t i = 0; i < size; ++i) {
typename std::list<T>::iterator ite = copy.begin();
int index = factoradic[i] - 48;
std::advance(ite, index);
std::cout << *ite << ',';
copy.erase(ite);
}
}
@higuaro

This comment has been minimized.

Copy link
Owner Author

@higuaro higuaro commented Jan 13, 2014

Example of usage:

int main() {
    std::list<int> elems = {1, 2, 3, 4, 5};
    int NUM_PERMUTATIONS = 5 * 4 * 3 * 2 - 1;
    for (int i = 0; i < NUM_PERMUTATIONS; i++) {
        printPermutation(i, elems);
        std::cout << std::endl;
    }
    return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.