Permutation without recursion?

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:

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

Solution

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.