4

您将如何编写从数组 {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} }

不是。

4

4 回答 4

2

你有 (N!) / ( ((3!)^(N/3)) * ((N/3)!)) 位置（证明）。您可以使用递归算法从数组 {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;
    }
于 2013-03-15T12:18:34.867 回答
2

由于 N 是 3 的倍数，我们可以使用一个技巧来解决它：

  1. 按升序生成数字的所有排列
  2. 对于每个排列，将数字直接划分为 3 个集合（0-2、3-6、...、N-2..N）

这应该会给你你的结果，而不需要太多花哨的工作。

编辑：我正在等待有人发现上述问题，并且确实发现了。解决重复的方法是有一个额外的步骤：

第 3 步：如果任何三元组在字典上是未排序的形式，则丢弃该集合。否则继续。

于 2013-03-15T07:29:49.207 回答
1 
#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");
}
于 2013-03-15T07:49:13.527 回答
0

让我们考虑 N 存在多少这样不同的三元组。首先将 T = floor(N/3) 定义为 N 个元素支持的每个集合中的三元组数。然后注意，由于不需要重复的三元组，每个三元组中的三元组可以按第一个元素升序排序，而不失一般性。那么 N 的三元组总数为：

产品为 t: 0 -> T-1 of ( (N - 3*t - 1) * (N - 3*t - 2) / 2 )

从这个公式可以直接看出如何构建（蛮力）算法来生成三元组。

更新：以上仅适用于 N % 3 == 0。我现在正在进行概括。强制；见 OP 的评论

案例：

  1. N<3 产生 0
  2. N=3 产生 1
  3. N=6 产生 (5 * 4 / 2) * (2 * 1 / 2) = 10
  4. N=9 产生 (8 * 7 / 2) * (5 * 4 / 2) * (2 * 1 / 2) = 28 * 10 = 280

当您参加编程比赛时，我假设您不需要任何代码。

更新 #2： 请注意，要自动消除重复项，每个三元组的第一个元素必须强制为编号最小的未选择元素。

于 2013-03-15T13:20:00.473 回答