c - 在不重复选择的情况下找到所有可能的组合？

Question

您将如何编写从数组 {1, 2, 3, ..., N-1, N} 中选择所有可能的三元组组合而不重复的东西？这是来自最近举行的编程比赛。 N 是 3 的倍数。

使用数组 {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} }

都是有效的，但是

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

不是。

Answer 1

你有 (N!)/( ((3!)^(N/3)) * ((N/3)!)) 位置 ( prove ) 。您可以只使用递归算法来提供数组 {1, 2, 3, ..., N-1, N} 中所有可能的三元组组合，而不重复。但是要制作其中一个，您可以使用任何想法，例如 user1952500想法(虽然这个算法也会生成(N/3)!位置重复)或每个，例如你不变的最后一个(N-6)成员并将你的第一个6成员的解决方案放在结果的开头。(这个算法不会产生重复位置)

递归解决方案:

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;
    }