PHP: перестановки из 26 букв в символах X - PullRequest
Новая
       9

PHP: перестановки из 26 букв в символах X

0 голосов
/ 29 июля 2011

У меня есть алфавитный массив с 26 символами A..Z.

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

Примеры:

X = 3.Целевой массив: _ _ _

Перестановки ABC до ZYX.

X = 4.Целевой массив: _ _ _ _

Перестановки ABCD до ZYXW

X = 5.Целевой массив: _ _ _ _ _

Перестановки ABCDE до ZYXWV

(Извините, я не знаю, как называется этот вид алгоритма)

Заранее спасибо.

Код на C, Delphi или Java тоже в порядке, поскольку его легко перевести.

Ответы [ 3 ]

1 голос
/ 29 июля 2011

Простое решение является рекурсивным. 

char current_combination[27];
int char_used[26];

void enumerate(int i, int n)
{
    for (int j=0; j<26; j++)
    {
        if (!char_used[j])
        {
            char_used[j] = 1;
            current_combination[i] = 'A' + j;
            if (i+1 == n)
            {
                puts(current_combination);
            }
            else
            {
                enumerate(i+1, n);
            }
            char_used[j] = 0;
        }
    }
}

. Вышеприведенная функция принимает индекс i вычисляемого символа и общее количество n символов в комбинации (код предполагаетi<n).Он сохраняет текущую комбинацию и массив флагов для уже используемых переменных в глобальных переменных, чтобы избежать их копирования.

Чтобы сгенерировать, например, все комбинации длины 5, вызовите enumerate(0, 5).

Обратите внимание, чтообщее число комбинаций растет очень быстро.Например, для n=6 существует 165,765,600 комбинаций, с выходом более 1 ГБ.

0 голосов
/ 29 июля 2011

Вы уверены, что хотите увидеть все перестановки?Если у вас X = 3, у вас будет 26 * 25 * 24 комбинаций = 15600. А если X = 5, то количество комбинаций равно 7893600.

Вам нужно случайным образом выбрать одну букву (или индекс массива)и сохраните его где-нибудь, и на каждой итерации вы должны проверить, была ли эта буква (или индекс) уже выбрана на одной из предыдущих итераций.После этого вы получите случайную последовательность длиной X символов.Вы должны хранить это тоже.Затем необходимо повторить все операции, выполненные на предыдущем шаге, а также проверить, есть ли случайная последовательность с подпоследовательностью, которую вы генерировали сейчас.

Или вы можете использовать прямое перечисление.

Извините за неудовлетворительный английский.Я пытался быть ясным.

Надеюсь, это будет полезно.

0 голосов
/ 29 июля 2011

Я бы выбрал простой метод грубой силы, хотя понимаю, что число перестановок может возрасти, поскольку число равно 26! / (26-x)!который может быть довольно большим, так как для 3 - 15 600 перестановок, а для 5 - 7 893 600 перестановок, что не совсем мало.По сути, вы можете просто просмотреть все значения с помощью циклов в циклах, которые, к сожалению, будут равны O (n ^ x), где x - это количество символов с момента размещения циклов, вызывающих сложность.

Что-торассмотреть, насколько хорошо вы исследуете сложность здесь.Например, в то время как вы могли бы подумать о том, как стать хитрее в первой паре циклов, чтобы избежать дублирования, третий цикл становится немного сложнее, хотя, если вы начали со Списка из 26 букв и удалили предыдущие, это приведет кпоследний цикл будет просто итеративным, поскольку вы знаете, что дубликатов не существует, хотя это может быть дорого с точки зрения использования памяти при создании копий списка при каждом проходе из внешнего цикла.Таким образом, в первый раз вы пройдете через AB_, а затем AC_ и т. Д., Но копирование списка может оказаться там, где это будет дорогостоящим с точки зрения операций, поскольку тысячи раз копировался бы список, что могло бы задаться вопросомесли это более эффективно, чем сравнение.

...