За последние 24 часа нас посетили 18805 программистов и 1612 роботов. Сейчас ищут 912 программистов ...

[РЕШЕНО] Генерация наборов комбинаций

Тема в разделе "Прочие вопросы по PHP", создана пользователем neverlose, 10 апр 2013.

  1. neverlose

    neverlose Активный пользователь

    С нами с:
    27 авг 2008
    Сообщения:
    1.112
    Симпатии:
    20
    Прошу помощи с алгоритмом.
    Необходимо написать функцию генерации наборов комбинаций.

    Пример:
    На вход поступает массив из 3 элементов:
    Код (Text):
    1. {a,b,c}
    На выходе имеем массив из 6 элементов (3! [факториал]), каждый элемент которого есть набор входного массива:
    Код (Text):
    1. {
    2.     {a,b,c},
    3.     {a,c,b},
    4.     {b,a,c},
    5.     {b,c,a},
    6.     {c,a,b},
    7.     {c,b,a},
    8. }
    Код писать не обязательно, желательно только объяснить алгоритм или дать ссылку на источник с информацией, спасибо.

    -----------------------------
    Решил задачу, ниже предоставляю код, может кому-то понадобится:
    Код (Text):
    1.  
    2.     private function swap(&$a, &$b) {
    3.         $c = $a;
    4.         $a = $b;
    5.         $b = $c;
    6.     }
    7.  
    8.     private function getPermutations($arr, $start = 0, $count = false) {
    9.  
    10.       $result = array();
    11.  
    12.       if ($count === false) {
    13.           $count = count($arr);
    14.       }
    15.  
    16.        if ($start == $count) {
    17.  
    18.            $result[] = $arr;
    19.        }
    20.        else {
    21.             for ($current = $start; $current < $count; $current++) {
    22.               $this->swap($arr[$start],$arr[$current]);
    23.               $result = array_merge($result, $this->getPermutations($arr, $start+1, $count));
    24.               $this->swap($arr[$start],$arr[$current]);
    25.            }
    26.        }
    27.  
    28.        return $result;
    29.     }
    30.  
    31.     private function getSets($str)
    32.     {
    33.         $parts = explode(' ', $str);
    34.         $parts = array_unique($parts);
    35.         $cnt = count($parts);
    36.  
    37.         return ($cnt <= 1) ? $parts : $this->getPermutations($parts, 0, $cnt);
    38.     }
     
  2. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    11.131
    Симпатии:
    1.251
    Адрес:
    там-сям