Я пытаюсь вывести алгоритм, который генерирует все возможные комбинации определенного размера, что-то вроде функции, которая принимает в качестве параметра массив символов и размер и возвращает массив комбинаций.
Пример: пусть говорят, что у нас есть набор символов: Set A = {A, B, C}
а) Все возможные комбинации размера 2: (3 ^ 2 = 9)
AA, AB, AC BA, BB, BC CA, CB, CC б) Все возможные комбинации размера 3: (3 ^ 3 = 27)
AAA, AAB, AAC, ABA, ABB, ACC, CAA, BAA, BAC, .... ad so on total combinations = 27
Обратите внимание, что размер пары может быть больше, чем общий размер pouplation. Ex. если набор содержит 3 символа, мы также можем создать комбинацию размера 4.
EDIT : Также обратите внимание, что это отличается от перестановки. В перестановке мы не можем повторять символы, например, AA не может прийти, если мы используем алгоритм перестановок. В статистике он известен как выборка.
Я бы использовал рекурсивную функцию. Вот пример (рабочий) с комментариями. Надеюсь, что это работает для вас!
function sampling($chars, $size, $combinations = array()) { # if it's the first iteration, the first set # of combinations is the same as the set of characters if (empty($combinations)) { $combinations = $chars; } # we're done if we're at size 1 if ($size == 1) { return $combinations; } # initialise array to put new values in $new_combinations = array(); # loop through existing combinations and character set to create strings foreach ($combinations as $combination) { foreach ($chars as $char) { $new_combinations[] = $combination . $char; } } # call same function again for the next iteration return sampling($chars, $size - 1, $new_combinations); } // example $chars = array('a', 'b', 'c'); $output = sampling($chars, 2); var_dump($output); /* array(9) { [0]=> string(2) "aa" [1]=> string(2) "ab" [2]=> string(2) "ac" [3]=> string(2) "ba" [4]=> string(2) "bb" [5]=> string(2) "bc" [6]=> string(2) "ca" [7]=> string(2) "cb" [8]=> string(2) "cc" } */
Возможный алгоритм:
$array_elems_to_combine = array('A', 'B', 'C'); $size = 4; $current_set = array(''); for ($i = 0; $i < $size; $i++) { $tmp_set = array(); foreach ($current_set as $curr_elem) { foreach ($array_elems_to_combine as $new_elem) { $tmp_set[] = $curr_elem . $new_elem; } } $current_set = $tmp_set; } return $current_set;
В основном, что вы будете делать, это взять каждый элемент текущего набора и добавить все элементы массива элементов.
На первом этапе вы получите результат ('a', 'b', 'c') после шага секунд: ('aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc') и т. д.
Вы можете сделать это рекурсивно. Обратите внимание, что согласно вашему определению, «комбинации» длины n+1 могут быть сгенерированы из комбинаций длины n , принимая каждую комбинацию длины n и добавляя одну из букв из вашего набора. Если вам интересно, вы можете доказать это математической индукцией .
Так, например, с набором {A,B,C} комбинации длины 1:
A, B, C
Следовательно, комбинации длины 2
(A, B, C) + A = AA, BA, CA (A, B, C) + B = AB, BB, BC (A, B, C) + C = AC, CB, CC
Это будет код, и здесь, на ideone
function comb ($n, $elems) { if ($n > 0) { $tmp_set = array(); $res = comb($n-1, $elems); foreach ($res as $ce) { foreach ($elems as $e) { array_push($tmp_set, $ce . $e); } } return $tmp_set; } else { return array(''); } } $elems = array('A','B','C'); $v = comb(4, $elems);
Вы можете попробовать этот открытый исходный код для этого. Он реализует итератор. Нажмите
Доступно в PHP, Java.