Permutation without recursion? [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 8 years ago.

I was trying to use a for loop to replace the recursion that I usually use, but I found it's harder than I thought. Can anyone tell me how to do it? Thanks!

For example, given a vector of 2, 1, 3. There should be six permutations:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

The vector is below...

vector<int> simple;
simple.push_back(2);
simple.push_back(1);
simple.push_back(3);

EDIT: changed the order from 1 2 3 to random order 2 1 3

Answer 1

I guess you are looking for std::next_permutation():

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

int main()
{
    std::vector<int> simple{1, 2, 3};

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

Here is a live example.

If you do not want to start with a sorted vector, you can use std::next_permutation() the following way:

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

constexpr int factorial(int i)
{
    return i == 0 ? 1 : i * factorial(i-1);
}

int main()
{
    std::vector<int> simple{3, 1, 2};

    for (int i = 0; i < factorial(simple.size()); i++)
    {
        std::next_permutation(simple.begin(), simple.end());
        for (auto e : simple) { std::cout << e << " "; }
        std::cout << std::endl;
    }
}

Here is a live example.

Notice, that if the size of the vector is known at compile-time, as seems to be the case from your example, you could use std::array instead of std::vector, as shown in this live example.