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.
Since N is a multiple of 3 we can solve it using a trick:
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.
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;
}
#include <stdio.h>
#define SEL_NUM 3
#define LIST_SIZE 6
void printset(int *list, int *map, int size);
void select(int *list, int *map, int n, int size, int start);
int main(int argc, const char **argv) {
int list[LIST_SIZE] = {1, 2, 3, 4, 5, 6};
int map[LIST_SIZE] = {0};
select(list, map, SEL_NUM, LIST_SIZE, 0);
return 0;
}
void select(int *list, int *map, int n, int size, int start) {
if (n == 0) {
printset(list, map, size);
return;
}
for (int i = start; i < size; i++) {
map[i] = 1;
select(list, map, n - 1, size, i + 1);
map[i] = 0;
}
}
void printset(int *list, int *map, int size) {
int list1[SEL_NUM], list2[SEL_NUM], list1cnt = 0, list2cnt = 0;
for (int i = 0; i < size; i++)
if (map[i])
list1[list1cnt++] = list[i];
else
list2[list2cnt++] = list[i];
for (int i = 0; i < list1cnt; i++)
printf(" %d ", list1[i]);
printf(" -- ");
for (int i = 0; i < list2cnt; i++)
printf(" %d ", list2[i]);
printf("\n");
}
Let's consider how many such distinct triplet-sets exist for N. First define T = floor(N/3) as the number of triplets in each set supported by N elements. Then note that since duplicate triplets are not desired, the triplets in each triplet set can be sorted ascending by first element without loss of generality. Then the total number of triplet-sets for N is:
product as t: 0 -> T-1 of ( (N - 3*t - 1) * (N - 3*t - 2) / 2 )
From this formula it is straightforward to see how to build the (brute-force) algorithm to generate the triplets.
Update: The above works only for N % 3 == 0. I am working on a generalization now. Forced; see comment by OP
Cases:
As you are in a programming competition, I assume you dont need any code.
Update #2: Note that to automatically eliminate duplicates, the first element of each triplet must be forced to the lowest numbered unselected element .
