permutations.cpp

#include <bitset>
#include <iostream>
#include <list>
#include <vector>

// Function to compute all permutations using iterators. It's still ugly, does a lot of copy and need some
// cleanup

/**
 *  \brief Computes permutations of the elements between the range (begin, end)
 *
 *  \tparam IterType iterator type
 *  \param begin begin iterator
 *  \param end end iterator
 *  \return a vector containing all permutations as lists
 */
template <class IterType>
std::vector<std::list<typename IterType::value_type>> permutations(IterType begin, IterType end)
{
    typedef typename IterType::value_type ReturnType;
    std::vector<std::list<ReturnType>> perms;  // This will be the output
    auto size = std::distance(begin, end);

    if (size < 2) {  // Edge case, just return the list
        std::list<ReturnType> lst1(begin, end);
        perms.push_back(lst1);
        return perms;
    }
    if (size == 2) {  // Recursive stop condition
        std::list<ReturnType> lst1(begin, end);
        perms.push_back(lst1);
        std::list<ReturnType> lst2(lst1);
        lst2.reverse();
        perms.push_back(lst2);
        return perms;
    }
    IterType next = begin;
    while (next != end) {
        // There must be a better way to remove one element from the list, but list.erase doesn't work...
        std::list<ReturnType> sublist(begin, next++);  // Wow...
        std::list<ReturnType> sublist2(next--, end);   // Gosh...
        sublist.insert(sublist.end(), sublist2.begin(), sublist2.end());

        std::vector<std::list<typename IterType::value_type>> child_perms =
            permutations(sublist.begin(), sublist.end());
        for (auto&& p : child_perms) {
            p.push_front(*next);
            perms.push_back(p);
        }
        ++next;
    }
    return perms;
}

int main(int argc, char* argv[])
{
    std::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);

    std::string s = "Tibo";

    double d[] = { 2.3, 2.4, 5.3, 6.66 };
    // auto perms = permutations(d, d+4);
    // auto perms = permutations(v.begin(), v.end());
    auto perms = permutations(s.begin(), s.end());
    for (auto p : perms) {
        for (auto e : p) {
            std::cout << e << " ";
        }
        std::cout << "\n";
    }

    return 0;
}