Think of a good algorithm for this program

[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.

 

[Future Bruno]

After thinking for a while, I came up with the following algorithm:1. Generate all possible room combinations using powerset (0 to 2^n - 1).2. For each combination, create two separate arrays representing each room.3. Sort the two arrays in descending order.4. Print out the two arrays in the desired format.This algorithm should work for all possible input values of n.

 

[ravenprp]

One possible algorithm for this program could be as follows:

1. Start by taking input from the user for the number of persons (n) and store it in a variable.
2. Create two arrays, room1 and room2, of size n to store the names of persons in each room.
3. Use a loop to generate all possible combinations of 0s and 1s of length n. For example, for n = 3, the combinations would be 000, 001, 010, 011, 100, 101, 110, 111.
4. For each combination, check the number of 1s and 0s and store the names of persons in room1 and room2 accordingly.
5. If the number of persons in room1 and room2 is the same, sort the names in alphabetical order.
6. Print the output in the desired format, with room1 and room2 combinations and the sorted names.
7. Repeat this process for all possible combinations.

This algorithm ensures that all possible combinations are generated and the names are sorted according to the given conditions. It avoids using excessive memory by storing only the names in the arrays and generating combinations on the go.