CODEWITHSUNDEEP
carraysnestednested-loops
dannysood
dannysood

Reputation: 1139

Find all combinations in 2d array to seat variable amount of people in theater in C?

I have an array of R rows and C columns (Max value of R and C is 50). The program requires that the user inputs the number of number of rows, number of columns of theatre, number people that will view the movie and the program prints all the possible seating combinations.

For example for 2 people , 3 rows , 3 columns

PP*
***
***

P*P
***
***

P**
P**
***

and so on...

The only thing I could figure out is using variable amount of nested loops depending on number of people user inputs and still no idea how to implement it.

Can anyone explain me how to achieve/implement this logic in C?

Upvotes: 0

Views: 492

Answers (2)

user3526368
user3526368

Reputation: 36

It seems He doesn't need to distinct between peoples, so it's selecting n seats of R*C seats whose number of possible cases is C(R*C,n)

so for R=2,C=2 and n=2 there should be 6 combinations: 00,11; 01,01; 10,01; 01,10; 10,10; 11,00;

EDIT: nested loop solution:

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

void OutSeats(int *seats,int R, int C, int n)
{
    int i,j,k=0;
#ifdef DEBUG
    for (i=1;i<=n;i++)
        printf("%d,",seats[i]);
    putchar('\n');
#else
    /* It should be alloced only once */
    static int* actual=0;    
    if (!actual)
        actual = calloc(R*C,sizeof(int));
    memset(actual,0,R*C*sizeof(int));
    for (i=1;i<=n;i++)
        actual[seats[i]-1] = 1;

    for (i=0;i<R;i++)
    {
        for (j=0;j<C;j++,k++)
            printf("%d",actual[k]);
        putchar('\n');
    }
    putchar('\n');
#endif
}
/***********************************/
void GenCombination(int R, int C, int n)
{
    int *seats = (int*)malloc((n+1)*sizeof(int));
    int i,sub;
    for (i=1;i<=n;i++)
        seats[i]=i;

    while (1)
    {
        OutSeats(seats,R,C,n);
        if (seats[n]<R*C)
            seats[n]++;
        else
        {
            sub=1;
            while ((sub<n) && (seats[n-sub]>=R*C-sub))
                sub++;
            if (sub<n)
            {
                seats[n-sub]++;
                for (i=n-sub+1 ; i<=n ; i++)
                    seats[i] = seats[i-1] + 1;
            }
            else
                break;
        }
    }

    free(seats);
}
/***********************************/
void main()
{
    int R,C,n;
    printf("Give R,C,n:");
    scanf("%d%d%d",&R,&C,&n);
    GenCombination(R,C,n);
}

Array seats holds seats assigned to each person. GenCombination works like a clock. It increases the last item till it reaches the maximum boundary then moves back and try to increase previous items and again get to the last item. Sequence of assigned seats is always increasing so that unique combinations will be generated. function OutSeats prints seats arrangement by converting assigned seats to actual seats.

Upvotes: 1

Mahonri Moriancumer
Mahonri Moriancumer

Reputation: 6013

Perhaps you could output something like this:

1 rows of 1 seats per row, and 1 person.

   1

1 combination.

Now one rows of two seats per row and one person:

   10   01

2 combinations.

Now, 1 rows of two seats per row and two persons:

   12   21

2 combinations.

2 rows of two seats and 1 person:

   10 01 00 00
   00 00 10 01

4 combinations

2 rows of two seats and 2 persons:

   21 20 20    12 02 02    10 01 00    10 01 00
   00 10 01    00 10 01    20 20 21    02 02 12

24 combinations.

3 rows of 2 seats and one person:

 100 010 001 000 000 000 000 000 000
 000 000 000 100 010 001 000 000 000
 000 000 000 000 000 000 100 010 001

9 combinations total;

(Plane is landing... gotta go for now...)

Upvotes: 1

Related Questions