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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?