Я знаю, что эта тема много обсуждается, но я не могу найти никакой реализации, которая бы соответствовала моим потребностям.
У меня есть следующий набор символов:
ABCDEFGH
Я хочу получить все возможные перестановки или комбинации (не повторяющиеся), но на ограниченном (переменном) наборе символов , что означает, что если я вводим символы и число 2 , результаты должны выглядеть так:
ab ba ac ca ad da ae ea af fa ag ga ah ha bc cb bd db be eb bf fb bg gb bh hb cd dc ce ec cf fc cg gc ch hc de ed df fd dg gd dh hd ef fe eg ge eh he fg gf fh hf gh hg
Надеюсь, вы поймете, с чем я это сделаю. В настоящее время у меня есть реализация, которая дает мне перестановки всех символов, но я не могу окунуться в то, как реализовать ограниченное пространство для этих перестановок:
public function getPermutations($letters) { if (strlen($letters) < 2) { return array($letters); } $permutations = array(); $tail = substr($letters, 1); foreach ($this->getPermutations($tail) as $permutation) { $length = strlen($permutation); for ($i = 0; $i <= $length; $i++) { $permutations[] = substr($permutation, 0, $i) . $letters[0] . substr($permutation, $i); } } return $permutations; }
Если вам нужен только один элемент за раз, вы можете сохранить его в памяти, генерируя каждый элемент по отдельности.
Если бы мы хотели создать случайную строку в вашем наборе ожидаемых результатов, мы могли бы использовать этот алгоритм:
Given a set of characters S, and a desired output length K: While the output has less than K characters: Pick a random number P between 1 and |S|. Append the P'th character to the output. Remove the P'th character from S.
где |S| – текущее число элементов в S.
Мы можем фактически кодировать эту последовательность выборов в целое число. Один из способов сделать это – изменить алгоритм как таковой:
Given a set of characters S, and a desired output length K: Let I = 0. While the output has less than K characters: I = I * (|S| + 1). Pick a random number P between 1 and the number of elements in S. I = I + P. Append the P'th character to the output. Remove the P'th character from S.
После запуска этого алгоритма значение I будет однозначно кодировать эту конкретную последовательность вариантов. Он в основном кодирует это как номер смешанного радиуса ; одна цифра использует базу N, а следующая использует N-1 и так далее до последней цифры, которая является базой N-K + 1 (N – количество букв на входе).
Естественно, мы также можем декодировать это снова, и в PHP это будет примерно так:
// Returns the total number of $count-length strings generatable from $letters. function getPermCount($letters, $count) { $result = 1; // k characters from a set of n has n!/(nk)! possible combinations for($i = strlen($letters) - $count + 1; $i <= strlen($letters); $i++) { $result *= $i; } return $result; } // Decodes $index to a $count-length string from $letters, no repeat chars. function getPerm($letters, $count, $index) { $result = ''; for($i = 0; $i < $count; $i++) { $pos = $index % strlen($letters); $result .= $letters[$pos]; $index = ($index-$pos)/strlen($letters); $letters = substr($letters, 0, $pos) . substr($letters, $pos+1); } return $result; }
(Заметим, что для простоты этот конкретный алгоритм декодирования не соответствует точно описанному ранее алгоритму кодирования, но сохраняет желаемое свойство данного сопоставления $index уникальному результату.)
Чтобы использовать этот код, вы бы сделали что-то вроде этого:
$letters = 'abcd'; echo '2 letters from 4:<br>'; for($i = 0; $i < getPermCount($letters, 2); $i++) echo getPerm($letters, 2, $i).'<br>'; echo '<br>3 letters from 4:<br>'; for($i = 0; $i < getPermCount($letters, 3); $i++) echo getPerm($letters, 3, $i).'<br>'; ?>
$strings = get_perm( range('a', 'h'), 4 ); function get_perm( $a, $c, $step = 0, $ch = array(), $result = array() ){ if( $c == 1 ){ //if we have last symbol in chain for( $k = 0; $k < count( $a ); $k++ ){ if( @in_array( $k, $ch ) ) continue; // if $k exist in array we already have such symbol in string $tmp = ''; foreach( $ch as $c ) $tmp .= $a[$c]; // concat chain of previous symbols $result[] = $tmp . $a[$k]; // and adding current + saving to our array to return } }else{ for( $i = 0; $i < count( $a ); $i++ ){ if( @in_array( $i, $ch ) ) continue; $ch[$step] = $i; // saving current symbol for 2 things: check if that this symbol don't duplicate later and to know what symbols and in what order need to be saved get_perm( $a, $c-1, $step+1, $ch, &$result ); // recursion, // decrementing amount of symbols left to create string, // incrementing step to correctly save array or already used symbols, // $ch - array of already used symbols, // &$result - pointer to result array } } return $result; }
УВЕДОМЛЕНИЕ
ах с 6 символами = 20 тыс. значений в массиве
az с 4 символами = 358799 значений в массиве
Таким образом, az с 10 символами точно умрет =) Это потребует слишком много памяти.
Вам нужно попытаться сохранить вывод в файл или базу данных, если вам понадобится большое количество значений. Или ограничьте ограничение памяти до php, но не уверены, что это лучший способ.