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.
Lloyd_3
- 4 Contributors
- forum4 Replies
- 30 Views
- 4 Years Discussion Span
- comment Latest Post by iamthwee
iamthwee 1,547
kindly show us what you have done.
Gonbe 32
#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;
}
Hiroshe 499
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
by Hiroshe
iamthwee 1,547
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.