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


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

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

30 148

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) записи в списке.

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

#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;
}

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

\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-количество символов, из которых мы выбираем, если я правильно вас понимаю. Вы должны определенно генерировать их по мере необходимости, а не становиться небрежными и говорить, генерировать powerset, а затем фильтровать длина строк.

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

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

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

нерекурсивное решение согласно Кнуту, пример 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)

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

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

некоторые рабочие 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;
        }
    }

есть много хороших ответов здесь. Я также предлагаю очень простое рекурсивное решение на 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;
    });
}

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

Я просто быстро взбитые это в 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 языка для встроенных функций типа перестановки, и вы можете написать более оптимизированный код, но если числа настолько высоки, я не уверен, что есть много способов обойти много результатов.

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

это перевод версии Майка 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)))))

вот простое слово 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);

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

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

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

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

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

void permute(const char *s, char *out, int *used, int len, int lev)
{
    if (len == lev) {
        out[lev] = '';
        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;
}

перестановки (АВС) -> А. Пермь(БК) -> А. Пермь[Б. Пермь(с)] -> А. Пермь[( * BC), (CB*)] -> [( * ABC), (BAC), (BCA*), ( * ACB), (CA B), (CBA*)] Чтобы удалить дубликаты при вставке каждого алфавита, проверьте, заканчивается ли предыдущая строка тем же алфавитом (почему? -упражнение)

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;
}

печатает все перестановки без повторений

Ruby ответ, который работает:

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")

рекурсивное решение в 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;
            }
        }
}

следующая рекурсия 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);
    }
}

Ниже приведена обновленная версия вышеуказанного метода "перестановки", который делает 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()));
   }
}

Я не уверен, почему вы хотели бы сделать это в первую очередь. Результирующий набор для любых умеренно больших значений 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);
            }
        }
    }
}
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;
    }
}

вот нерекурсивная версия, которую я придумал, в 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;
}

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

вот реализация с использованием метода кучи. Длина массива должна быть не менее 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

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

в ruby:

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

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

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

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

этот код в 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()

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

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

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

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

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

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

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

в 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;
    }

существует итеративная реализация Java в UncommonsMaths (работает для списка объектов):

/**
 * Generate the indices into the elements array for the next permutation. The
 * algorithm is from Kenneth H. Rosen, Discrete Mathematics and its 
 * Applications, 2nd edition (NY: McGraw-Hill, 1991), p. 284)
 */
private void generateNextPermutationIndices()
{
    if (remainingPermutations == 0)
    {
        throw new IllegalStateException("There are no permutations " +
             "remaining. Generator must be reset to continue using.");
    }
    else if (remainingPermutations < totalPermutations)
    {
        // Find largest index j with 
        // permutationIndices[j] < permutationIndices[j + 1]
        int j = permutationIndices.length - 2;
        while (permutationIndices[j] > permutationIndices[j + 1])
        {
            j--;
        }

        // Find index k such that permutationIndices[k] is smallest integer 
        // greater than permutationIndices[j] to the right
        // of permutationIndices[j].
        int k = permutationIndices.length - 1;
        while (permutationIndices[j] > permutationIndices[k])
        {
            k--;
        }

        // Interchange permutation indices.
        int temp = permutationIndices[k];
        permutationIndices[k] = permutationIndices[j];
        permutationIndices[j] = temp;

        // Put tail end of permutation after jth position in increasing order.
        int r = permutationIndices.length - 1;
        int s = j + 1;

        while (r > s)
        {
            temp = permutationIndices[s];
            permutationIndices[s] = permutationIndices[r];
            permutationIndices[r] = temp;
            r--;
            s++;
        }
    }
    --remainingPermutations;
}

/**
 * Generate the next permutation and return a list containing
 * the elements in the appropriate order.  This overloaded method
 * allows the caller to provide a list that will be used and returned.
 * The purpose of this is to improve performance when iterating over
 * permutations.  If the {@link #nextPermutationAsList()} method is
 * used it will create a new list every time.  When iterating over
 * permutations this will result in lots of short-lived objects that
 * have to be garbage collected.  This method allows a single list
 * instance to be reused in such circumstances.
 * @param destination Provides a list to use to create the
 * permutation.  This is the list that will be returned, once
 * it has been filled with the elements in the appropriate order.
 * @return The next permutation as a list.
 */
public List<T> nextPermutationAsList(List<T> destination)
{
    generateNextPermutationIndices();
    // Generate actual permutation.
    destination.clear();
    for (int i : permutationIndices)
    {
        destination.add(elements[i]);
    }
    return destination;
}

полный текст

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
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

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

решение питона:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]