комбинации игроков для команды в C - PullRequest
Новая
       11

комбинации игроков для команды в C

1 голос
/ 07 февраля 2011

Я пытаюсь создать все комбинации игроков, чтобы составить команду баскетболистов. Допустим, есть 5 позиций (SG, PG, SF, PF, C), и мне нужно заполнить петуха 9 игроками, по 2 на каждую позицию, кроме центральной позиции, для которой есть только 1.

Допустим, у меня есть 10 игроков на каждую позицию, как я могу сгенерировать список всех возможных перестановок.

Я бы хотел импортировать имена из Excel в CSV-файл, а затем вывести все комбинации обратно в Excel в другом CSV-файле.

Я могу понять, как делать импорт и экспорт CSV-файлов, но меня больше интересует лучший алгоритм для выполнения приведенных выше перестановок.

Если проще генерировать перестановки, это хорошо, а я могу легко исключить дубликаты в Excel.

Спасибо!

1 Ответ

1 голос
/ 07 февраля 2011

Вы можете использовать алгоритмическую технику под названием 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 человек, вы получаете намного большее время выполнения, потому что теперь вы имеете дело с большим количеством комбинаций.

Так что это зависит от того, сколько данных у вас есть, насколько это возможно.

...