kindly help me in making program in the permutaion of 1,2,3,4,5.
Permutation means the arrangements of the numbers 1,2,3,4,5.
ex. 1,2,3,5,4
1,2,4,5,3 and so on.. there are 120 results.

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

using namespace std;

/* Just a helper function that prints the contents of the vector, separated by a space */
void print_vector(vector<int> data)
{
    for (auto elem : data)
        cout << elem << ' ';
}


/* Uses the <algorithm> function to generate permutations */
void print_permutations_cheesy(vector<int> data)
{
    /* Permutations are generated in lexicographical order, sort to start with the "smallest" value */
    sort(data.begin(), data.end());

    do /* For every permutation.. */
    {
        /* Print the vector */
        print_vector(data);

        /* End the line */
        cout << endl;
    } 
    /* Calculate the next permutation */
    while (next_permutation(data.begin(), data.end()));
}



/* The function that actually generates the permutations, and releases the "f" function on each one of them */
void permute(vector<int> data, const unsigned begin, const unsigned end, function<void(const vector<int>&)> f)
{
    /* If begin equals end, it means we only look at a single element; there is nothing left to permute */
    if (begin == end)
    {
        f(data);
    }
    else
    {
        /* Go past every element in the range [begin,end] */
        for (unsigned i = begin; i <= end; i++)
        {
            /* Swap the first element with the i-th element */
            swap(data[i], data[begin]);

            /* Recursively permute the rest of the range */
            permute(data, begin + 1, end, f);

            /* Restore the array to it's original (as in: how it was supplied to this function) state */
            swap(data[i], data[begin]);
        }
    }
}

/* Generate the permutations ourselves, this is just a wrapper function to keep the signature the same 
   as "print_permutations_cheesy", the real work happens in "permute" */
void print_permutations_manual(vector<int> data)
{
    permute(data, 0, data.size() - 1, [](const vector<int>& data) {
        print_vector(data);
        cout << endl;
    });
}

/* A fac function to calculate the amount of results */
unsigned fac (const unsigned n)
{
    if (n == 0)
        return 1;
    else
        return n * fac(n - 1);
}

/* Application starting point */
int main()
{
    vector<int> data { 1, 2, 3, 4, 5 };

    cout << "Our data, consisting of n = " << data.size() << " elements, has n! = " << fac(data.size()) << " permutations:\n\n";
    print_permutations_manual(data);

    return 0;
}

I think using <algorthim> and <function> is a little overkill.

The set of all permutations can be set up as a simple tree. The most natural way to iterate through all of the permutations would be a little recursion.

If you wanted to, you would be able to optimise it using a stack+iteration (or tail recursion if your compiler supports the optimization) if you wished too.

Edited 2 Years Ago by Hiroshe

Gobne

Celary yuo aer a gineus who not olny cna qukcily slove teh hmorweok of ohters threbey hdaning tehm a sulotoin on a palte, but yuo cna aslo raed tihs gabrbled meassge in nomral tmie. Jsut in csae yuo hdan't geussed I dwon repeepd yuo as yuo dno't apaeppr to hvae laernt why tihs is worng.

This article has been dead for over six months. Start a new discussion instead.