C 中球队的球员组合

Question

我正在尝试生成所有球员组合以组成一支篮球队。假设有 5 个位置(SG、PG、SF、PF、C)，我需要用 9 名球员填充一只公鸡，每个位置 2 个，除了中锋位置只有 1 个。

假设每个位置有 10 个球员，我如何生成所有可能排列的列表。

我想从一个 csv 文件中导入 excel 中的名称，然后将所有组合输出回另一个 csv 文件中的 excel。

我可以弄清楚如何导入和导出 csv 内容，但我对执行上述排列的最佳算法更感兴趣。

如果更容易生成排列，那很好，而且我可以轻松消除 excel 中的重复项。

谢谢!

Answer 1

您可以使用一种称为 backtracking 的算法技术.

或者，根据您有多少玩家，您可以使用蛮力并只是循环。例如，您可以使用以下方法选择 2 个前锋和 1 个中锋的所有组合(这是一个 C++ 示例，只是为了说明该技术)。

    #include <iostream>
    #include <fstream>
    #include <algorithm>
    #include <numeric>
    #include <iostream>
    #include <sstream>
    #include <string>
    #include <vector>
    using namespace std;

    int main() {
      vector< string > centers;
      vector< string > forwards;
      centers.push_back("joey");
      centers.push_back("rick");
      centers.push_back("sam");

      forwards.push_back("steve");
      forwards.push_back("joe");
      forwards.push_back("harry");
      forwards.push_back("william");

      for(int i = 0; i < centers.size(); ++i) {
        for(int j = 0; j < forwards.size(); ++j) {
          for(int k = j+1; k < forwards.size(); ++k) {
            printf("%s %s %s\n",centers[i].c_str(), forwards[j].c_str(), forwards[k].c_str());
          }
        }
      }
      return 0;
    }

输出:

---------- Capture Output ----------
> "c:\windows\system32\cmd.exe" /c c:\temp\temp.exe
joey steve joe
joey steve harry
joey steve william
joey joe harry
joey joe william
joey harry william
rick steve joe
rick steve harry
rick steve william
rick joe harry
rick joe william
rick harry william
sam steve joe
sam steve harry
sam steve william
sam joe harry
sam joe william
sam harry william

> Terminated with exit code 0.

然而，重要的是要记住，如果你有很多玩家，那么你所做的任何事情都是“蛮力”，其中包括回溯(回溯与我上面使用的循环的想法相同，只是它使用递归)是将在运行时间中呈指数增长。因此，例如对于一个 5 人名单，如果你有 10 个中锋、20 个前锋和 18 个后卫，那么运行时间基本上是:

10 * 20 * 20 * 18 * 18 = 1,296,000

(20 * 20 因为我们需要 2 个前锋，18 * 18 因为我们需要 2 个后卫)。

1,296,000 对于运行时间来说并不算太糟糕，但是当你开始谈论 9 人名单时，你会得到更高的运行时间，因为现在你要处理更多的组合。

所以这是否可行取决于您拥有多少数据。