Генерируйте список всех возможных перестановок строки

Вы могли бы посмотреть" Эффективно Перечисление Подмножеств Набора ", который описывает алгоритм, чтобы внести свой вклад того, что Вы хотите - быстро генерируют все подмножества символов N от длины x к y. Это содержит реализацию в C.

Для каждого подмножества, необходимо было бы все еще генерировать все перестановки. Например, если бы Вы хотели 3 символа от "abcde", этот алгоритм дал бы Вам "abc", "abd", "abe"..., но необходимо будет переставить каждого для получения "acb", "баккара", "bca", и т.д.

Вы собираетесь получить много строк, это наверняка...

\sum_ {i=x} ^y {\\frac {r!} {{(r-i)}! }} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey%20%7B%20%5Cfrac%7Br!%7D%7B%7B (r-i) %7D! %7D%20%7D
, Где, X и Y - то, как Вы определяете их, и r является количеством символов, которые мы выбираем из - если я понимаю Вас правильно. Необходимо определенно генерировать их по мере необходимости и не стать неаккуратными и сказать, генерировать степенное множество и затем отфильтровать длину строк.

следующим определенно не является лучший способ генерировать их, но это - интересное в стороне, тем не менее.

Knuth (объем 4, гроздь 2, 7.2.1.3) говорит нам, что (s, t) - комбинация эквивалентна s+1 вещам взятый t за один раз с повторением - (s, t) - комбинация является нотацией, используемой Knuth, который равен {t \choose {s+t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D . Мы можем понять это первой генерацией каждого (s, t) - комбинация в двоичной форме (так, длины (s+t)) и подсчет количества 0 налево от каждого 1.

10001000011101-> становится перестановкой: {0, 3, 4, 4, 4, 1}

Некоторый рабочий код Java на основе ответа Сарпа :

public class permute {

    static void permute(int level, String permuted,
                    boolean used[], String original) {
        int length = original.length();
        if (level == length) {
            System.out.println(permuted);
        } else {
            for (int i = 0; i < length; i++) {
                if (!used[i]) {
                    used[i] = true;
                    permute(level + 1, permuted + original.charAt(i),
                       used, original);
                    used[i] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        String s = "hello";
        boolean used[] = {false, false, false, false, false};
        permute(0, "", used, s);
    }
}

Вот простое решение на C #.

Он генерирует только различные перестановки данной строки.

    static public IEnumerable<string> permute(string word)
    {
        if (word.Length > 1)
        {

            char character = word[0];
            foreach (string subPermute in permute(word.Substring(1)))
            {

                for (int index = 0; index <= subPermute.Length; index++)
                {
                    string pre = subPermute.Substring(0, index);
                    string post = subPermute.Substring(index);

                    if (post.Contains(character))
                            continue;                       

                    yield return pre + character + post;
                }

            }
        }
        else
        {
            yield return word;
        }
    }

В рубине:

str = "a"
100_000_000.times {puts str.next!}

Это довольно быстро, но это собирается занять время =). Конечно, можно запустить в "aaaaaaaa", если короткие строки не интересны Вам.

я, возможно, неправильно истолковал фактический вопрос, хотя - в одном из сообщений казалось будто Вам просто была нужна библиотека "в лоб" строк, но в основном вопросе это кажется, что необходимо переставить конкретную строку.

Ваша проблема несколько подобна этому: http://beust.com/weblog/archives/000491.html (перечисляют все целые числа, в которых ни одна из цифр не повторяет себя, которые привели к большому количеству языков, решив его с ocaml парнем, использующим перестановки и некоторого парня Java, использующего еще одно решение).

Хотя это не отвечает на Ваш вопрос точно, вот один способ генерировать каждую перестановку букв от многих строк той же длины: например, если Ваши слова были "кофе", "joomla" и "Moodle", можно ожидать вывод как "coodle", "joodee", "joffle", и т.д.

В основном, количество комбинаций (количество слов) к питанию (количество букв на слово). Так, выберите случайное число между 0 и количество комбинаций - 1, преобразуйте то число для базирования (количество слов), затем используйте каждую цифру того числа как индикатор для который слово взять следующую букву от.

, например: в вышеупомянутом примере. 3 слова, 6 букв = 729 комбинаций. Выберите случайное число: 465. Преобразуйте в основу 3: 122020. Возьмите первую букву от Word 1, 2-го от Word 2, 3-го от Word 2, 4-го от Word 0..., и Вы добираетесь... "joofle".

, Если Вы хотели все перестановки, просто цикл от 0 до 728. Конечно, если бы Вы просто выбираете одно случайное значение, много <забастовка>, более простая , меньше запутывающий путь состоял бы в том, чтобы циклично выполниться по буквам. Этот метод позволяет Вам избежать рекурсии, должны, Вы хотеть все перестановки, плюс он делаете, Вы быть похожими на Вас знаете Математику <глоток> (TM) !

, Если количество комбинаций является чрезмерным, можно разбить его в серию меньших слов и связать их в конце.

Я не уверен, почему Вы хотели бы сделать это во-первых. Получающийся набор для любых умеренно больших значений X и Y будет огромен, и вырастет экспоненциально как x, и/или y становятся больше.

Позволяет, говорят, что Ваш набор возможных символов является 26 строчными буквами алфавита, и Вы просите, чтобы Ваше приложение генерировало все перестановки где длина = 5. Принятие Вас не исчерпывает память, которую Вы получите 11,881,376 (т.е. 26 к питанию 5) строки назад. Удар, что длина до 6, и Вы вернете 308 915 776 строк. Эти числа становятся крайне большими, очень быстро.

Вот решение, которое я соединил в Java. Необходимо будет обеспечить два аргумента во время выполнения (соответствующий X и Y). Весело провести время.

public class GeneratePermutations {
    public static void main(String[] args) {
        int lower = Integer.parseInt(args[0]);
        int upper = Integer.parseInt(args[1]);

        if (upper < lower || upper == 0 || lower == 0) {
            System.exit(0);
        }

        for (int length = lower; length <= upper; length++) {
            generate(length, "");
        }
    }

    private static void generate(int length, String partial) {
        if (length <= 0) {
            System.out.println(partial);
        } else {
            for (char c = 'a'; c <= 'z'; c++) {
                generate(length - 1, partial + c);
            }
        }
    }
}

Я просто сделал это на скорую руку быстрое в Ruby:

def perms(x, y, possible_characters)
  all = [""]
  current_array = all.clone
  1.upto(y) { |iteration|
    next_array = []
    current_array.each { |string|
      possible_characters.each { |c|
        value = string + c
        next_array.insert next_array.length, value
        all.insert all.length, value
      }
    }
    current_array = next_array
  }
  all.delete_if { |string| string.length < x }
end

Вы могли бы изучить API языка для созданного в функциях типа перестановки, и Вы могли бы быть в состоянии записать больше оптимизированного кода, но если числа - весь, что высоко, я не уверен, что существует большая часть пути вокруг наличия большого количества результатов.

Так или иначе, идея позади кода является запуском со строкой длины 0, затем отслеживайте все строки длины Z, где Z является текущим размером в повторении. Затем пройдите каждую строку и добавьте каждый символ на каждую строку. Наконец в конце, удалите любого, которые были ниже x порога и возвращают результат.

я не протестировал его с потенциально бессмысленным входом (список нулевого символа, странные значения X и Y, и т.д.).

Это - перевод версии Ruby Mike's в язык Common LISP:

(defun perms (x y original-string)
  (loop with all = (list "")
        with current-array = (list "")
        for iteration from 1 to y
        do (loop with next-array = nil
                 for string in current-array
                 do (loop for c across original-string
                          for value = (concatenate 'string string (string c))
                          do (push value next-array)
                             (push value all))
                    (setf current-array (reverse next-array)))
        finally (return (nreverse (delete-if #'(lambda (el) (< (length el) x)) all)))))

И другая версия, немного короче и использующий больше функций средства цикла:

(defun perms (x y original-string)
  (loop repeat y
        collect (loop for string in (or (car (last sets)) (list ""))
                      append (loop for c across original-string
                                   collect (concatenate 'string string (string c)))) into sets
        finally (return (loop for set in sets
                              append (loop for el in set when (>= (length el) x) collect el)))))

В Perl, если Вы хотите ограничить себя алфавитом нижнего регистра, можно сделать это:

my @result = ("a" .. "zzzz");

Это дает все возможные строки между 1 и 4 символами с помощью символов нижнего регистра. Для верхнего регистра, изменение "a" к "A" и "zzzz" к "ZZZZ".

Для смешанного случая это становится намного более твердым, и вероятно не выполнимое с одним из встроенных операторов Perl как этот.

Рекурсивное решение в C++

int main (int argc, char * const argv[]) {
        string s = "sarp";
        bool used [4];
        permute(0, "", used, s);
}

void permute(int level, string permuted, bool used [], string &original) {
    int length = original.length();

    if(level == length) { // permutation complete, display
        cout << permuted << endl;
    } else {
        for(int i=0; i<length; i++) { // try to add an unused character
            if(!used[i]) {
                used[i] = true;
                permute(level+1, original[i] + permuted, used, original); // find the permutations starting with this string
                used[i] = false;
            }
        }
}

Вот является простое слово C# рекурсивное решение:

Метод:

public ArrayList CalculateWordPermutations(string[] letters, ArrayList words, int index)
        {
            bool finished = true;
            ArrayList newWords = new ArrayList();
            if (words.Count == 0)
            {
                foreach (string letter in letters)
                {
                    words.Add(letter);
                }
            }

            for(int j=index; j<words.Count; j++)
            {
                string word = (string)words[j];
                for(int i =0; i<letters.Length; i++)
                {
                    if(!word.Contains(letters[i]))
                    {
                        finished = false;
                        string newWord = (string)word.Clone();
                        newWord += letters[i];
                        newWords.Add(newWord);
                    }
                }
            }

            foreach (string newWord in newWords)
            {   
                words.Add(newWord);
            }

            if(finished  == false)
            {
                CalculateWordPermutations(letters, words, words.Count - newWords.Count);
            }
            return words;
        }

Вызов:

string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);