Создать список всех возможных перестановок строки

Как бы я пошел о создании списка всех возможных перестановок строки между символами x и y длиной, содержащей список переменных символов.

Любой язык будет работать, но он должен быть переносимым.

hippietrail 29.06.2017 12:33:26
30 ОТВЕТОВ
РЕШЕНИЕ

Есть несколько способов сделать это. Обычные методы используют рекурсию, запоминание или динамическое программирование. Основная идея заключается в том, что вы создаете список всех строк длины 1, а затем в каждой итерации для всех строк, созданных в последней итерации, добавляете эту строку, объединенную с каждым символом в строке по отдельности. (индекс переменной в приведенном ниже коде отслеживает начало последней и следующей итерации)

Какой-то псевдокод:

list = originalString.split('')
index = (0,0)
list = [""]
for iteration n in 1 to y:
  index = (index[1], len(list))
  for string s in list.subset(index[0] to end):
    for character c in originalString:
      list.add(s + c)

Затем вам нужно будет удалить все строки, длина которых меньше x, они будут первыми (x-1) * len (originalString) записями в списке.

70
27.07.2015 02:58:18
Зачем сначала хранить список элементов, а затем очищать его? (ссылаясь на строки 1 и 3 в псевдокоде).
Håvard Geithus 26.05.2012 17:25:47
Что такое у (строка 4)?
Джасим 23.09.2012 21:13:32
@Jaseem Из вопроса: «все возможные перестановки строки длиной от x до y символов »
ck_ 28.03.2013 23:06:14

Лучше использовать возврат

#include <stdio.h>
#include <string.h>

void swap(char *a, char *b) {
    char temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void print(char *a, int i, int n) {
    int j;
    if(i == n) {
        printf("%s\n", a);
    } else {
        for(j = i; j <= n; j++) {
            swap(a + i, a + j);
            print(a, i + 1, n);
            swap(a + i, a + j);
        }
    }
}

int main(void) {
    char a[100];
    gets(a);
    print(a, 0, strlen(a) - 1);
    return 0;
}
39
20.01.2017 17:58:23
Лучшее решение из когда-либо существовавших
GrowinMan 11.03.2015 04:16:25

Вы получите много строк, это точно ...

\ Sum_ {я = х} ^ у {\ гидроразрыва {г!} {{(П)}!}}
Где x и y - это то, как вы их определяете, а r - количество символов, из которых мы выбираем - если я вас правильно понимаю. Вы должны определенно генерировать их по мере необходимости и не становиться неряшливыми, скажем, генерировать powerset, а затем фильтровать длину строк.

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

Кнут (том 4, глава 2, 7.2.1.3) говорит нам, что (s, t) -комбинация эквивалентна s + 1 вещам, взятым t одновременно, с повторением - (s, t) -комбинация - это обозначение, используемое Кнут, который равен {t \ choose {s + t}. Мы можем выяснить это, сначала сгенерировав каждую (s, t) -комбинацию в двоичной форме (т.е. длины (s + t)) и посчитав количество нулей слева от каждого 1.

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

25
10.10.2019 16:38:39

Нерекурсивное решение по примеру Кнута, Python:

def nextPermutation(perm):
    k0 = None
    for i in range(len(perm)-1):
        if perm[i]<perm[i+1]:
            k0=i
    if k0 == None:
        return None

    l0 = k0+1
    for i in range(k0+1, len(perm)):
        if perm[k0] < perm[i]:
            l0 = i

    perm[k0], perm[l0] = perm[l0], perm[k0]
    perm[k0+1:] = reversed(perm[k0+1:])
    return perm

perm=list("12345")
while perm:
    print perm
    perm = nextPermutation(perm)
15
9.11.2010 13:58:06
На самом деле, это не работает, когда строка не отсортирована. Если вы попытаетесь с "54321"только ОДНА строкой предъявляются (сам).
tonjo 2.08.2015 12:35:36
Что интересно, это то, что он не nextPermutation()имеет состояния - для перестановки требуется только ввод, и индексы не поддерживаются от итерации к итерации. Он может сделать это, предполагая, что начальный ввод был отсортирован, и найдя индексы ( k0и l0) сам по себе, в зависимости от того, где поддерживается порядок. Сортировка ввода типа «54321» -> «12345» позволит этому алгоритму найти все ожидаемые перестановки. Но так как он проделывает большую дополнительную работу по поиску этих индексов для каждой генерируемой перестановки, существуют более эффективные способы сделать это нерекурсивно.
spaaarky21 1.05.2017 03:15:51

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

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

13
14.11.2008 19:36:49

Некоторый рабочий Java-код, основанный на ответе Sarp :

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);
    }
}
13
23.05.2017 11:54:37
В качестве комментария обратите внимание, что для строки с повторяющимися символами это не приведет к уникальным перестановкам. Это можно решить с помощью хэша, но это может быть проблемой с длинными строками.
Гленн 29.10.2010 19:17:39
Возможно, вы захотите использовать массивы символов вместо строк, чтобы сделать это быстрее, так как строки неизменяемы в Java.
Абхиджит Кашня 1.07.2012 07:06:15

Вот простое решение в 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;
        }
    }
13
5.07.2010 09:06:37

Здесь много хороших ответов. Я также предлагаю очень простое рекурсивное решение в C ++.

#include <string>
#include <iostream>

template<typename Consume>
void permutations(std::string s, Consume consume, std::size_t start = 0) {
    if (start == s.length()) consume(s);
    for (std::size_t i = start; i < s.length(); i++) {
        std::swap(s[start], s[i]);
        permutations(s, consume, start + 1);
    }
}

int main(void) {
    std::string s = "abcd";
    permutations(s, [](std::string s) {
        std::cout << s << std::endl;
    });
}

Примечание : строки с повторяющимися символами не будут генерировать уникальные перестановки.

12
8.01.2014 11:00:51

Я просто быстро взбил это в 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 и т. Д.).

9
2.08.2008 07:56:07
Этот код НЕПРАВИЛЬНЫЙ. Он будет генерировать недопустимые перестановки, например, с повторяющимися символами. Например, для строки «abc» он генерирует следующие перестановки размером 3: [«aaa», «aab», «aac», «aba», «abb», «abc», «aca», «acb», "acc", "baa", "bab", "bac", "bba", "bbb", "bcc", "bca", "bcb", "bcc", "caa", "cab", "cac "," cba "," cbb "," cbc "," cca "," ccb "," ccc "]. Это неверно
pmc255 2010 года 14.10.2010 03:07:40

Это перевод версии Майка для Ruby на 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)))))
8
16.09.2008 05:15:26

Вот простое слово 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);
8
20.10.2008 00:17:50

... а вот версия C:

void permute(const char *s, char *out, int *used, int len, int lev)
{
    if (len == lev) {
        out[lev] = '\0';
        puts(out);
        return;
    }

    int i;
    for (i = 0; i < len; ++i) {
        if (! used[i])
            continue;

        used[i] = 1;
        out[lev] = s[i];
        permute(s, out, used, len, lev + 1);
        used[i] = 0;
    }
    return;
}
8
7.02.2011 21:56:58

перестановка (ABC) -> A.perm (BC) -> A.perm [B.perm (C)] -> A.perm [( * B C), (C B * )] -> [( * A BC) ), (B A C), (BC A * ), ( * A CB), (C A B), (CB A * )] Чтобы удалить дубликаты при вставке каждого алфавита, проверьте, заканчивается ли предыдущая строка тем же алфавитом (почему? - упражнение)

public static void main(String[] args) {

    for (String str : permStr("ABBB")){
        System.out.println(str);
    }
}

static Vector<String> permStr(String str){

    if (str.length() == 1){
        Vector<String> ret = new Vector<String>();
        ret.add(str);
        return ret;
    }

    char start = str.charAt(0);
    Vector<String> endStrs = permStr(str.substring(1));
    Vector<String> newEndStrs = new Vector<String>();
    for (String endStr : endStrs){
        for (int j = 0; j <= endStr.length(); j++){
            if (endStr.substring(0, j).endsWith(String.valueOf(start)))
                break;
            newEndStrs.add(endStr.substring(0, j) + String.valueOf(start) + endStr.substring(j));
        }
    }
    return newEndStrs;
}

Печатает все перестановки без дубликатов

8
22.02.2011 22:39:57

Рекурсивное решение в 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;
            }
        }
}
8
11.07.2012 21:09:43

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

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

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

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

7
15.02.2009 10:02:43

Рубиновый ответ, который работает:

class String
  def each_char_with_index
    0.upto(size - 1) do |index|
      yield(self[index..index], index)
    end
  end
  def remove_char_at(index)
    return self[1..-1] if index == 0
    self[0..(index-1)] + self[(index+1)..-1]
  end
end

def permute(str, prefix = '')
  if str.size == 0
    puts prefix
    return
  end
  str.each_char_with_index do |char, index|
    permute(str.remove_char_at(index), prefix + char)
  end
end

# example
# permute("abc")
7
20.04.2012 00:21:53
Для
любопытного dojosto 9.09.2014 04:59:07
import java.util.*;

public class all_subsets {
    public static void main(String[] args) {
        String a = "abcd";
        for(String s: all_perm(a)) {
            System.out.println(s);
        }
    }

    public static Set<String> concat(String c, Set<String> lst) {
        HashSet<String> ret_set = new HashSet<String>();
        for(String s: lst) {
            ret_set.add(c+s);
        }
        return ret_set;
    }

    public static HashSet<String> all_perm(String a) {
        HashSet<String> set = new HashSet<String>();
        if(a.length() == 1) {
            set.add(a);
        } else {
            for(int i=0; i<a.length(); i++) {
                set.addAll(concat(a.charAt(i)+"", all_perm(a.substring(0, i)+a.substring(i+1, a.length()))));
            }
        }
        return set;
    }
}
6
24.10.2010 23:32:05

Следующая рекурсия Java печатает все перестановки данной строки:

//call it as permut("",str);

public void permut(String str1,String str2){
    if(str2.length() != 0){
        char ch = str2.charAt(0);
        for(int i = 0; i <= str1.length();i++)
            permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
                     str2.substring(1,str2.length()));
    }else{
    System.out.println(str1);
    }
}

Ниже приводится обновленная версия вышеупомянутого метода "permut", который делает n! (n факториал) менее рекурсивные вызовы по сравнению с вышеуказанным методом

//call it as permut("",str);

public void permut(String str1,String str2){
   if(str2.length() > 1){
       char ch = str2.charAt(0);
       for(int i = 0; i <= str1.length();i++)
          permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
                 str2.substring(1,str2.length()));
   }else{
    char ch = str2.charAt(0);
    for(int i = 0; i <= str1.length();i++)
        System.out.println(str1.substring(0,i) + ch +    str1.substring(i,str1.length()),
                 str2.substring(1,str2.length()));
   }
}
6
16.08.2016 23:15:05
Это самое чистое решение, и я полагаю, что я видел его раньше в книге «Взлом интервью»
Дао Чжан 13.08.2016 04:21:57
@TaoZhang спасибо за дополнение, я нигде не копировал его, однако возможно, что кто-то создал подобный алгоритм. В любом случае я обновил код выше для менее рекурсивных звонков
Рами 16.08.2016 23:18:12

Я не уверен, почему вы хотели бы сделать это в первую очередь. Результирующий набор для любых умеренно больших значений 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);
            }
        }
    }
}
5
2.08.2008 09:40:54
Давно, но разве вы не генерируете их с повторением?
Какира 11.05.2014 05:07:19

Вот нерекурсивная версия, которую я придумал, в javascript. Это не основано на нерекурсивном Кнуте выше, хотя у него есть некоторые сходства в обмене элементами. Я проверил его правильность для входных массивов до 8 элементов.

Быстрая оптимизация - это предварительная проверка outмассива и избежание push().

Основная идея:

  1. Для одного исходного массива создайте первый новый набор массивов, которые поочередно меняют первый элемент на каждый последующий, каждый раз оставляя невозмущенные другие элементы. например: дано 1234, сгенерировано 1234, 2134, 3214, 4231.

  2. Используйте каждый массив из предыдущего прохода в качестве начального числа для нового прохода, но вместо замены первого элемента меняйте местами второй элемент с каждым последующим элементом. Кроме того, на этот раз не включайте исходный массив в вывод.

  3. Повторите шаг 2, пока не будет сделано.

Вот пример кода:

function oxe_perm(src, depth, index)
{
    var perm = src.slice();     // duplicates src.
    perm = perm.split("");
    perm[depth] = src[index];
    perm[index] = src[depth];
    perm = perm.join("");
    return perm;
}

function oxe_permutations(src)
{
    out = new Array();

    out.push(src);

    for (depth = 0; depth < src.length; depth++) {
        var numInPreviousPass = out.length;
        for (var m = 0; m < numInPreviousPass; ++m) {
            for (var n = depth + 1; n < src.length; ++n) {
                out.push(oxe_perm(out[m], depth, n));
            }
        }
    }

    return out;
}
5
10.04.2016 19:13:43

В рубине:

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

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

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

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

3
15.09.2008 17:39:43
Проблема с вашим предложением заключается в том, что str.next! не будет перебирать все печатные символы. Ваш пример будет генерировать только строчные буквы - без знаков препинания или заглавных букв.
Ярсен 29.10.2010 19:00:38

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

Вот реализация, использующая метод Heap. Длина массива должна быть не менее 3, а по практическим соображениям - не более 10 или около того, в зависимости от того, что вы хотите сделать, терпения и тактовой частоты.

Перед тем, как ввести свой цикл инициализацию Perm(1 To N)с первой перестановкой, Stack(3 To N)с нулями * и Levelс 2**. В конце вызова цикла NextPerm, который вернет false, когда мы закончим.

* VB сделает это за вас.

** Вы можете немного изменить NextPerm, чтобы сделать это ненужным, но это более понятно.

Option Explicit

Function NextPerm(Perm() As Long, Stack() As Long, Level As Long) As Boolean
Dim N As Long
If Level = 2 Then
    Swap Perm(1), Perm(2)
    Level = 3
Else
    While Stack(Level) = Level - 1
        Stack(Level) = 0
        If Level = UBound(Stack) Then Exit Function
        Level = Level + 1
    Wend
    Stack(Level) = Stack(Level) + 1
    If Level And 1 Then N = 1 Else N = Stack(Level)
    Swap Perm(N), Perm(Level)
    Level = 2
End If
NextPerm = True
End Function

Sub Swap(A As Long, B As Long)
A = A Xor B
B = A Xor B
A = A Xor B
End Sub

'This is just for testing.
Private Sub Form_Paint()
Const Max = 8
Dim A(1 To Max) As Long, I As Long
Dim S(3 To Max) As Long, J As Long
Dim Test As New Collection, T As String
For I = 1 To UBound(A)
    A(I) = I
Next
Cls
ScaleLeft = 0
J = 2
Do
    If CurrentY + TextHeight("0") > ScaleHeight Then
        ScaleLeft = ScaleLeft - TextWidth(" 0 ") * (UBound(A) + 1)
        CurrentY = 0
        CurrentX = 0
    End If
    T = vbNullString
    For I = 1 To UBound(A)
        Print A(I);
        T = T & Hex(A(I))
    Next
    Print
    Test.Add Null, T
Loop While NextPerm(A, S, J)
J = 1
For I = 2 To UBound(A)
    J = J * I
Next
If J <> Test.Count Then Stop
End Sub

Другие методы описаны различными авторами. Кнут описывает два, один дает лексический порядок, но сложен и медленен, другой известен как метод простых изменений. Цзе Гао и Дяньцзюнь Ван также написали интересную статью.

3
2.10.2011 09:13:57

Этот код в python, когда вызывается с allowed_charactersустановленным в [0,1]и максимум 4 символами, генерирует 2 ^ 4 результата:

['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']

def generate_permutations(chars = 4) :

#modify if in need!
    allowed_chars = [
        '0',
        '1',
    ]

    status = []
    for tmp in range(chars) :
        status.append(0)

    last_char = len(allowed_chars)

    rows = []
    for x in xrange(last_char ** chars) :
        rows.append("")
        for y in range(chars - 1 , -1, -1) :
            key = status[y]
            rows[x] = allowed_chars[key] + rows[x]

        for pos in range(chars - 1, -1, -1) :
            if(status[pos] == last_char - 1) :
                status[pos] = 0
            else :
                status[pos] += 1
                break;

    return rows

import sys


print generate_permutations()

Надеюсь, что это полезно для вас. Работает с любым персонажем, а не только с цифрами

2
10.04.2016 19:28:49
Это не перестановки, а выбор подмножества, то есть ABC & 001 = C, в то время как допустимая перестановка должна иметь все три символа.
Schultz9999 24.08.2012 04:52:17
э? извините, я не понимаю, что вы говорите. Если вы исправите его, оставьте исправленную версию, я сделаю это в сообществе
droope 3.09.2012 03:32:38

Вот ссылка, которая описывает, как распечатать перестановки строки. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

2
21.08.2016 07:50:11

Хотя это не дает точного ответа на ваш вопрос, вот один из способов генерировать каждую перестановку букв из ряда строк одинаковой длины: например, если ваши слова были «coffee», «joomla» и «moodle», вы можете ожидайте вывод, как "coodle", "joodee", "joffle" и т. д.

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

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

Если вам нужны все перестановки, просто выполните цикл от 0 до 728. Конечно, если вы выбираете только одно случайное значение, гораздо более простой и менее запутанный способ будет заключаться в переборе букв. Этот метод позволяет вам избежать рекурсии, если вам нужны все перестановки, плюс он заставляет вас выглядеть так, как будто вы знаете Maths (tm) !

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

0
16.09.2008 05:33:25

C # итеративный:

public List<string> Permutations(char[] chars)
    {
        List<string> words = new List<string>();
        words.Add(chars[0].ToString());
        for (int i = 1; i < chars.Length; ++i)
        {
            int currLen = words.Count;
            for (int j = 0; j < currLen; ++j)
            {
                var w = words[j];
                for (int k = 0; k <= w.Length; ++k)
                {
                    var nstr = w.Insert(k, chars[i].ToString());
                    if (k == 0)
                        words[j] = nstr;
                    else
                        words.Add(nstr);
                }
            }
        }
        return words;
    }
0
26.07.2012 15:20:23
def gen( x,y,list): #to generate all strings inserting y at different positions
list = []
list.append( y+x )
for i in range( len(x) ):
    list.append( func(x,0,i) + y + func(x,i+1,len(x)-1) )
return list 

def func( x,i,j ): #returns x[i..j]
z = '' 
for i in range(i,j+1):
    z = z+x[i]
return z 

def perm( x , length , list ): #perm function
if length == 1 : # base case
    list.append( x[len(x)-1] )
    return list 
else:
    lists = perm( x , length-1 ,list )
    lists_temp = lists #temporarily storing the list 
    lists = []
    for i in range( len(lists_temp) ) :
        list_temp = gen(lists_temp[i],x[length-2],lists)
        lists += list_temp 
    return lists
0
22.08.2013 17:51:53
def permutation(str)
  posibilities = []
  str.split('').each do |char|
    if posibilities.size == 0
      posibilities[0] = char.downcase
      posibilities[1] = char.upcase
    else
      posibilities_count = posibilities.length
      posibilities = posibilities + posibilities
      posibilities_count.times do |i|
        posibilities[i] += char.downcase
        posibilities[i+posibilities_count] += char.upcase
      end
    end
  end
  posibilities
end

Вот мой взгляд на нерекурсивную версию

0
23.01.2014 03:28:19

Питоническое решение:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
0
13.07.2014 07:51:36

Вот элегантное нерекурсивное решение O (n!):

public static StringBuilder[] permutations(String s) {
        if (s.length() == 0)
            return null;
        int length = fact(s.length());
        StringBuilder[] sb = new StringBuilder[length];
        for (int i = 0; i < length; i++) {
            sb[i] = new StringBuilder();
        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int times = length / (i + 1);
            for (int j = 0; j < times; j++) {
                for (int k = 0; k < length / times; k++) {
                    sb[j * length / times + k].insert(k, ch);
                }
            }
        }
        return sb;
    }
0
27.06.2015 08:44:42