?
Solved

Permutations - Can't figure this one out

Posted on 2003-03-27
4
Medium Priority
?
190 Views
Last Modified: 2010-04-15
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
Comment
Question by:clarki68
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
4 Comments
 
LVL 6

Expert Comment

by:gj62
ID: 8222116
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
 

Author Comment

by:clarki68
ID: 8222147
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
 
LVL 6

Expert Comment

by:gj62
ID: 8222222
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
 
LVL 8

Accepted Solution

by:
akshayxx earned 150 total points
ID: 8222333
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

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
Suggested Courses

752 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question