Поиск всех комбинаций двойников (имеющих два элемента) из списка - PullRequest
Новая
       2

Поиск всех комбинаций двойников (имеющих два элемента) из списка

1 голос
/ 19 декабря 2011

Скажите, что мой список {1,2,3,4}

Мой заголовок может быть недостаточно описательным, но вот что я хочу сделать ... Я хочу, чтобы мой код генерировал следующее

{ (1,2) , (3,4) }

{ (1,3) , (2,4) }

{ (1,4) , (2,3) }

{ (2,1) , (4,3) }

{ (3,1) , (4,2) }

{ (4,1) , (3,2) }

т.е. я хочу, чтобы все 4C2 комбинации набора.

Примечание: здесь первые четыре элемента - просто иллюстративное число .. число может варьироваться до 8 или 10.

Теперь, какЯ пишу код для этого (в C или PHP).

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

Наверное, я не очень хорошо это объяснил;на самом деле я не получил проблему сам.я хочу, чтобы у меня было 4 команды, и я хочу сыграть каждую команду против другой, тогда как мне создать все матчи.в моем примере выше;учитывая 1,2,3,4 как 4 команды.и {(1,2), (3,4)} как набор приборов и так далее.Как мне это сделать.следовательно, мне нужно сгенерировать весь набор приборов NC2 / (N / 2).(N = 4 в этом случае)

Ответы [ 2 ]

2 голосов
/ 19 декабря 2011

По сути, я хочу знать алгоритм. не все это, даже Старт будет достаточно хорошим .. Я просто не могу придумать что-либо, чтобы начать с.

Если вам нужен старт, документы Python показывают алгоритм, используемый для реализации функции комбинаций. Замените range () на простой цикл for, а yield на printf , и его будет легко перевести на C или PHP: http://docs.python.org/library/itertools.html#itertools.combinations

Обратите внимание на комбинации четырех вещей, взятых по две одновременно, дает: (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4). Ваш пример вывода также включает в себя дополнение каждого (т. Е. (1, 2) сопровождается (3, 4)).

1 голос
/ 12 апреля 2017

Я сделал это (PHP).Я добавил третий параметр, который можно использовать, чтобы функция возвращала все возможные комбинации независимо от того, имеет ли значение порядок элементов.Начальный набор параметров и возвращаемые комбинации будут массивами 

function every_combinations($set, $n, $order_matters = false) {
    $combinations = [];
    foreach($set AS $k => $e) {
        $subset = $set;
        unset($subset[$k]);
        if($n == 1) $combinations[] = [$e];
        else {
            $subcomb = every_combinations($subset, $n - 1, $order_matters);
            foreach($subcomb AS $s) {
                $comb = array_merge([$e], $s);
                if($order_matters) $combinations[] = $comb;
                else {
                    $needle = $comb;
                    sort($needle);
                    if(!in_array($needle, $combinations)) $combinations[] = $comb;
                }
            }
        }
    }
    return $combinations;
}
...