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.

Member Avatar for iamthwee

kindly show us what you have done.

#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.

Member Avatar for iamthwee

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.