1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Think of a good algorithm for this program

  1. Sep 14, 2006 #1
    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.
  2. jcsd
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

Similar Discussions: Think of a good algorithm for this program