# Think of a good algorithm for this program

1. Sep 14, 2006

### Gagan A

I just can't think of a good algorithm for this program after two days.
There are n persons (you take n from the user) and you have to permute them in room 1 and room 2 for all possible number of permutations. If the number of persons in a room are same then they should be sorted according to their alphabetical order.
eg: for input 3
output should be-

1 2

- abc

a bc
b ac
c ab

ab c
ac b
bc a

abc -

I first tried doing it using powersets i.e. generating the numbers in binary form from 0 to 2^n - 1 (000,001,010,011,100,101,110,111) but it doesn't match the output given for a. Of course, I could have done it by storing the combinations in arrays and sorting them accordingly but it will cross memory limits for the valid possible inputs (2<=n<=26) very soon.

Then another method I thought of was generating the initial possibility of i (0<=i<=n) and then permute accordingly (eg: generate 000,100,110,111 then permute these four). But the problem with it is that I am unable to permute them in the given order (the order of numbers must be decreasing for the same number, that's for sure) in a simple manner, I tried two failed algorithms for this thing but both have failed.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted