我想编写一个程序，可以提供 3 人的系列组，以便没有人与同一个人两次在组中。所以我们不能在两个不同的系列中有 123 和 124！
例如：9 人。最多可组成四次：
系列 1：
组 1： 1 2 3
组 2： 4 5 6
组 3： 7 8 9
系列 2：
第 1 组：1 5 9
第 2 组：2 6 7
第 3 组：3 4 8
系列 3：
第 1 组 3 5 7
第 2 组：1 6 8
第 3 组：2 4 9
第 4 组：
第 1 组：3 6 9
第 2 组：2 5 8
第 3 组：1 4 7
但是只有 12 个人，我觉得很难手工完成。可以组成 4-5 个 12 人的系列（绝对最大）。
我只是不知道如何编写这个程序。除了用笔和纸“尝试”之外，我找不到系统的方法。我想和30个人一起做。30人可组成13-14个系列。（绝对最大值）
好的，这是一个使用 c++ 的回溯解决方案：
#include <stdio.h>
using namespace std;
int v[100], n;
int ma[100][100];
void init(int k)
{
v[k] = 0;
}
bool solutionReached( int k )
{
if (k == n + 1)
return true;
return false;
}
void printSolution( int k )
{
for (int i = 1; i < k; i++)
{
printf("%i ", v[i]);
if (i % 3 == 0)
{
printf("\n");
}
}
for (i = 1; i < n; i++)
{
if (i % 3 == 1)
{
for (int j = i + 1; j < i + 3; j++)
{
ma[v[i]][v[j]] = 1;
ma[v[j]][v[i]] = 1;
}
}
for (int j = i + 1; j % 3 == 0; j++)
{
ma[v[i]][v[j]] = 1;
ma[v[j]][v[i]] = 1;
}
}
for (i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
//printf("%d ", ma[i][j]);
}
//printf("\n");
}
printf("\n");
}
bool hasSuccesor( int k )
{
if(v[k] < n)
{
v[k]++;
return true;
}
return false;
}
bool isValid( int k )
{
for (int i = 1; i < k; i++)
{
if (v[i] == v[k])
{
return false;
}
/*if (ma[v[i]][v[k]] == 1)
{
return false;
}*/
}
for (i = 1; i < k; i++)
{
if (i % 3 == 1)
{
for (int j = i + 1; j < i + 3; j++)
{
if (ma[v[i]][v[j]] == 1)
{
return false;
}
}
}
for (int j = i + 1; j % 3 == 0; j++)
{
if (ma[v[i]][v[j]] == 1)
{
return false;
}
}
}
return true;
}
void bkt(int k)
{
if(solutionReached(k))
printSolution(k);
else
{
init(k);
while(hasSuccesor(k))
if(isValid(k))
bkt(k + 1);
}
}
int main(int argc, char* argv[])
{
n = 9;
bkt(1);
return 0;
}
如果您想进行实验，请更改n = 9为除以 的任何数字3，例如12, 15, 21，但即使是很小的数字 (>15) 也会花费很多时间（这取决于计算机）。
编辑：我重做“没有人与同一个人在同一组中两次”，但我只能找到 3 个组而不是 4 个，9 个人。
例如： - 对于 9 个程序给出：
1 2 3
4 5 6
7 8 9
1 4 7
2 5 8
3 6 9
1 5 9
2 6 7
4 3 8
对于 12 程序给出：
1 2 3
4 5 6
7 8 9
10 11 12
1 4 7
2 5 10
3 8 11
6 9 12
1 5 8
2 4 12
3 9 10
7 6 11
对于 15：
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15
1 4 7
2 5 8
3 10 13
6 11 14
9 12 15
1 5 9
2 4 10
3 6 15
7 11 13
8 12 14
1 6 8
2 7 14
4 12 13
5 10 15
11 3 9
18 岁：（一分半钟后 - 所以还有更多 -）
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15
1 4 7
2 5 8
3 10 13
6 11 14
9 12 15
1 5 9
2 4 10
3 6 15
7 11 13
8 12 14
1 6 8
2 7 14
4 12 13
5 10 15
11 3 9
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15
16 17 18
1 4 7
2 5 8
3 6 9
10 13 16
11 14 17
12 15 18
1 5 9
2 4 10
3 7 11
6 13 18
8 15 17
14 12 16
1 6 8
2 7 12
3 4 13
5 10 17
9 14 18
11 15 16
1 10 14
2 6 15
3 5 12
4 9 16
7 13 17
8 11 18
如果要将它们保存到文件中，请包含 fstream 并将 printSolution 修改为：
void printSolution( int k )
{
ofstream cout;
cout.open("date.txt", ios::app);
for (int i = 1; i < k; i++)
{
cout << v[i] << " ";
if (i % 3 == 0)
{
cout << "\n";
}
}
for (i = 1; i < n; i++)
{
if (i % 3 == 1)
{
for (int j = i + 1; j < i + 3; j++)
{
ma[v[i]][v[j]] = 1;
ma[v[j]][v[i]] = 1;
}
}
for (int j = i + 1; j % 3 == 0; j++)
{
ma[v[i]][v[j]] = 1;
ma[v[j]][v[i]] = 1;
}
}
}