Finding all possible combinations without duplicating selections?

Question

How would you write something that selects all possible combinations of triples from an array {1, 2, 3, ..., N-1, N} without duplicates? This is from a recently-held programming competition. N is a multiple of 3.

Example using array {1,2,3,4,5,6}:

C_1 = { {1,2,3}, {4,5,6} }
C_2 = { {1,2,4}, {3,5,6} }
C_3 = { {1,2,5}, {3,4,6} }

are all valid, but

C_bad1 = { {1,2,3}, {3, 4, 5} }
C_bad2 = { {1,2,4}, {3, 5, 6}, {1, 2, 5} }

are not.

Answer 1

you have (N!) / ( ((3!)^(N/3)) * ((N/3)!)) position (prove) . you can just use recursive algorithm for provide all possible combinations of triples from an array {1, 2, 3, ..., N-1, N} without duplicates. but for produce one of them you can use any idea such as user1952500 idea(though This algorithm also generates (N/3)! position duplicate) or every, for example you invariant last-(N-6)-member and put your solution for first-6-member in start of your result.(this algorithm do not generate duplicate position)

recursive solution:

void combtriples(int begin)
    {
     for(int i=1;i<=(n/3);i++)
      for(int j=1;j<=(n/3);j++)
       for(int k=1;k<=(n/3);k++)
        {
         if ((mark[i]<3) && (mark[j]<3) && (mark[k]<3))
          {
           count-position++;
           c[count][3]=begin;
           c[count][4]=begin+1;
           c[count][5]=begin+2;
           mark[i]++;
           mark[j]++;
           mark[k]++;
           count-member-flase=count-member-flase+3;
           if (count-member-flase > 0)
           {
             combtriples(begin+3);
           }
          }
         }
    }


    int main()
    {
     int mark[];
     int c[][];
     count-position=0;
     count-member-flase=0;
     combtriples(1);
    return 0;
    }

Answer 2

Since N is a multiple of 3 we can solve it using a trick:

1. Generate all permutations of the numbers in ascending order
2. For each permutation, partition the numbers into sets of 3 directly (0-2, 3-6,..., N-2..N)

That should give you your result without much fancy work.

EDIT: I was waiting for someone to spot the issue with the above and it was indeed spotted. The way to fix repetitions is to have an additional step:

Step 3: If any triple is lexicographically unsorted form discard the set. Else continue.