• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 192
  • Last Modified:

Permutations - Can't figure this one out

Hi!

I'm trying to print out all permutations of 1,2,3...n where the permutations can only be of length r.  So if I had n=5 and r=3:

123
213
321
423
523
ect...

I have tried a few things and they didn't work quite right =( I have the number of permutations and I'm getting all those listed there except I'm also getting repeat customers (got 123 a bunch of times).
0
clarki68
Asked:
clarki68
  • 2
1 Solution
 
gj62Commented:
Sounds like homework, please post your code and we'll help you over the rough spots, but we can't do this for you from scratch (against board policy, you know...)
0
 
clarki68Author Commented:
Ok well here is the function I have so far (which does not work properly).

void Combinatorics::printP(int k,int l)
{
     int perm[10];
     int temp;
     for(int x=0;x<n;x++)
     {
          perm[x]=x+1;
     }
     temp = perm[k];
     perm[k] = perm[l];
     perm [l] = temp;
     for(x=0;x<r;x++)
     {
          cout << perm[x];
     }
     cout << endl;
     l++;
     if(l==n)
     {
          l=0;
          k++;
     }
     if(k<n)
     {
          printP(k,l);
     }
     return;
}
The whole program involves finding Permutations and Combinations.  I'm fine with the others but I can't figure out Permutations quite right.  

n and r are already declared as data members of the class.

C++ is more of a hobby because I love it however my brain doesn't get along well with math so this one is a real doozy for me =)  
0
 
gj62Commented:
No worries, but you might try the C++ forum - this is the C forum.  Now, since alot of us overlap, and of course you can use C source in C++, you'll probably get an answer here, but just thought I'd mention it...
0
 
akshayxxCommented:
as gj62 asked , u shud try c++ forum, but if u r ready to accept c answer , then u can continue here, u can get c++ answer also,

and about the problem, u say u can get the combinations , but cant figure out the permutations,
well if u can get combinations then u are almost there.
for each combination generated u just have to rotate the elements of a combination..
 here is a quick trick in calculating permutations from already generated combinations.

since while calculating nCr, and nPr  u have all the nCr of the length r,
so all u have to do is..
 generate  permutations of 1...r  rPr ( permutations of indices)
and for each  combination of nCr, take the permutation of indices from rPr , and print the components of the particular combination in that order..

here is an example
for the numbers 1 2 3  n = 3 and r =2.
permutations of indices ( 1...2) are .. 12 21  ( u shud drop the 11 and 22 (all digits same) )
combinations nCr are    12 13 23

hence for the particular combination 13 ,,
(combination 13 can be stored in an array as.. a[0]=1 a[1]=3.. ( indices a1 and a2) )
the permutations are
 a1a2 a2a1  =  13 31

do this for all the combinations..

and u'll have all the nPr permutations as

 12 21
 13 31
 23 32

now u can add to it 11 22 and 33 also.

0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now