7
\$\begingroup\$

The task is to compute all the permutations for a given vector of integers (but of course the specific integer type is not relevant for the solution)

The strategy is based on recursion + iterations

At each recursion, the state consists of

  • the root sequence a which is the set of elements already placed

  • the remaining elements set b which is the set of elements still to be placed

Inside the recursion, a loop places the N(i) (with i recursion index and) remaining elements producing the same amount of new root sequences and a new recursion is started so that N(i+1)=N(i)-1 hence meaning the overall complexity is O(N!) as expected

The recursion ends when there are no more elements to place hence b.empty() is true

Each recursion set ends with a valid sequence hence they are all merged together in a final list of sequences

Here is my CPP solution

#include <iostream>
#include <vector>
using namespace std;

vector<int> remove_item (const vector<int>& a, const unsigned int id)
{
    vector<int> res; 
    for(unsigned int i=0; i<a.size(); ++i) if(i!=id) res.push_back(a[i]); 
    return res;
}


vector<int> add_item(const vector<int>& a, const int b)
{
    vector<int> res=a; 
    res.push_back(b); 
    return res;
}

vector< vector<int> > merge(const vector< vector<int> >& a, const vector< vector<int> >& b)
{
    vector< vector<int> > res=a; 
    for(const auto& e : b) res.push_back(e); 
    return res;
}



vector< vector<int> > permutations(const vector<int>& b, const vector<int>& a={})
{

    if(b.empty()) return { a }; 

    vector< vector<int> > res; 
    for(unsigned int i=0; i<b.size(); ++i) res=merge(res, permutations(remove_item(b,i), add_item(a, b[i]))); 
    return res; 
}

int main() {
    // your code goes here

    auto res = permutations({1,2,3,4,5}); 
    cout << "Sol Num = " << res.size() << endl; 
    for(const auto& a : res) 
    {
        for(const auto& b : a) cout << to_string(b) << " "; 
        cout << endl; 
    }
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Not only the time complexity, but also the memory complexity is \$O(n!)\$ – because that's the size of your output. For \$n\$ greater than tiny this may be a serious disadvantage... \$\endgroup\$ – CiaPan Apr 24 at 12:05
  • \$\begingroup\$ The number of permutations is N! which means eventually you need to store all of them so you need O(N!) memory, unless you are allowed to print them as soon as you discover them \$\endgroup\$ – Nicola Bernini Apr 24 at 12:12
  • \$\begingroup\$ That's it: unless. You never said they must be delivered all at once. So it's a valid supposition you can find them one by one and utilize (for example: print) iteratively... \$\endgroup\$ – CiaPan Apr 24 at 12:59
6
\$\begingroup\$

A cleaner solution is to trust the standard library and try to re-use the generic components already available there. Your problem is solved by std::next_permutation, so you can proceed along the lines of:

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> v = { 1, 2, 3, 4, 5 };

    do
    {
        for (auto e : v)
            std::cout << e << " ";
        std::cout << "\n";
    } 
    while (std::next_permutation(v.begin(), v.end()));
}

For pedagogical purposes, if you wanted to keep your current structure, you could also use standard functions there. In particular, remove_item and merge could be rewritten to:

std::vector<int> remove_item(const std::vector<int>& a, int id)
{
    assert(id >= 0 && id < a.size());

    std::vector<int> res(a.begin(), a.begin() + id);
    res.insert(res.end(), a.begin() + id + 1, a.end());
    return res;
}

std::vector<std::vector<int> > merge(const std::vector<std::vector<int> >& a, const std::vector<std::vector<int> >& b)
{
    std::vector<std::vector<int> > res(a);
    std::copy(b.begin(), b.end(), std::back_inserter(res));
    return res;
}

Whatever you do, as general comments:

\$\endgroup\$
  • 2
    \$\begingroup\$ Sure, but using the standard library makes it trivial My goal was to develop a working algo \$\endgroup\$ – Nicola Bernini Apr 23 at 13:57
  • \$\begingroup\$ @NicolaBernini Indeed, I hope that nobody is discouraged from reviewing your code beyond my answer. \$\endgroup\$ – Juho Apr 23 at 13:58
  • 1
    \$\begingroup\$ @NicolaBernini Trust Juho, you will be able to write better algorithms if you learn the standard library. \$\endgroup\$ – WooWapDaBug Apr 23 at 15:02
  • \$\begingroup\$ @WooWapDaBug I already know it (at least at some extent, there is always room for improvement) but I hope it is clear it was not the point of the exercise \$\endgroup\$ – Nicola Bernini Apr 23 at 15:15
  • \$\begingroup\$ @NicolaBernini It wasn't, but now the relevant tag is added so it is. \$\endgroup\$ – Mast Apr 23 at 17:09
3
\$\begingroup\$

I understand the need to reinvent the wheel but in this case you reinvented an other kind of wheel: functional-style combinatorics aren't very well suited to C++ and the high-performance / low-memory usage it is well known for. I mean, that's a bike wheel for a car.

Now if you want to reinvent the C++ wheel, the best thing would be to re-implement std::next_permutation: an algorithm that does its work incrementally, in place, and with iterators (meaning that you can compute the permutations of strings, arrays, double-linked lists and everything that exposes bidirectional iterators).

Interestingly, there's an example of implementation on cppreference.com:

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    if (first == last) return false;
    BidirIt i = last;
    if (first == --i) return false;

    while (true) {
        BidirIt i1, i2;

        i1 = i;
        if (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

This implementation is a good example of "C++-sprinkled" C code. It's rather elegant but difficult to understand. If you reverse-engineer it though, you'll see it's quite simple:

  • first, beginning from the end, find the first adjacent items in increasing order. Let's call the lesser item's position the permutation point. If there are none, that was the last permutation: reverse and return false;

  • then, also beginning from the end, find the first item whose value is superior to that of the permutation point. Swap those two, reverse the range (permutation_point, last) and return true.

Now we're ready to reinvent a C++ wheel the C++ way:

#include <algorithm>
#include <iterator>

template <typename Iterator>
bool permute(Iterator first, Iterator last) {
    // check if there are at least two elements
    if (first == last || std::next(first) == last) return false;

    // first step: first adjacent elements in increasing order, starting from the end
    const auto r_first = std::reverse_iterator(last);
    const auto r_last  = std::reverse_iterator(first);
    auto position = std::adjacent_find(r_first, r_last, [](auto lhs, auto rhs) {
        return lhs > rhs;
    });
    // check if it was the last permutation
    if (position == r_last) {
        std::reverse(first, last);
        return false;
    }
    ++position; // advance position to the lesser item

    // second step: swap the permutation point and the first greater value from the end
    std::iter_swap(position, std::find_if(r_first, position, [position](auto value) {
        return value > *position;
    }));
    std::reverse(r_first, position);
    return true;
}
\$\endgroup\$
  • \$\begingroup\$ I understand your point and thanks for sharing it, but I have to do bias disclosure now: I (strongly) favour functional style over imperative (which does not mean I’m a purist, otherwise I would not have used loops, I’m just trying to take the best of both worlds) Certainly it can have a performance cost (depends how smart the compiler is) but I think it is not necessary for me to list the joys functional programming \$\endgroup\$ – Nicola Bernini Apr 24 at 9:25
  • \$\begingroup\$ @NicolaBernini: well, you can always put next_permutation into a functional shell (like you do with insert, push_back, etc. in your helper functions). I also like functional programming a lot, and have tried a few times to adopt functional idioms in C++ but there's always a point where you understand C++ won't ever be Haskell. But yeah, sure! \$\endgroup\$ – papagaga Apr 24 at 9:44
  • \$\begingroup\$ This is the strategy I adopt typically for my hybrid functional style, but not in this case as I was trying to reimplement next_permutation but in production code that’s what I tend to do. C++ does not need be Haskell, but some C++ programmer would certainly take benefit from some exposure to Haskell :) \$\endgroup\$ – Nicola Bernini Apr 24 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.