Hasilkan daftar semua kemungkinan permutasi string

Bagaimana cara saya membuat daftar semua permutasi yang mungkin dari string antara panjang karakter x dan y, yang berisi daftar variabel karakter.

Bahasa apa pun bisa digunakan, tetapi harus portabel.

Ada beberapa cara untuk melakukan ini. Metode umum menggunakan rekursi, memoisasi, atau pemrograman dinamis. Ide dasarnya adalah Anda membuat daftar semua string dengan panjang 1, lalu di setiap iterasi, untuk semua string yang dihasilkan dalam iterasi terakhir, tambahkan string yang digabungkan dengan setiap karakter dalam string secara individual. (indeks variabel dalam kode di bawah ini melacak awal iterasi terakhir dan berikutnya)

Beberapa pseudocode:

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)

Anda kemudian harus menghapus semua string yang panjangnya kurang dari x, mereka akan menjadi entri pertama (x-1) * len (originalString) dalam daftar.

Lebih baik menggunakan 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;
}

Anda akan mendapatkan banyak string, itu pasti ...

Di mana x dan y adalah bagaimana Anda mendefinisikannya dan r adalah jumlah karakter yang kami pilih dari - jika saya memahami Anda dengan benar. Anda harus menghasilkan ini sesuai kebutuhan dan tidak menjadi ceroboh dan berkata, hasilkan powerset dan kemudian filter panjang string.

Yang berikut ini jelas bukan cara terbaik untuk menghasilkan ini, tapi ini yang menarik, tidak ada yang kurang.

Knuth (volume 4, fascicle 2, 7.2.1.3) memberi tahu kita bahwa (s, t) -kombinasi sama dengan s + 1 hal yang diambil t sekaligus dengan pengulangan - an (s, t) -kombinasi adalah notasi yang digunakan oleh Knuth itu sama dengan . Kita dapat mengetahui hal ini dengan pertama-tama menghasilkan masing-masing (s, t) -kombinasi dalam bentuk biner (jadi, dengan panjang (s + t)) dan menghitung jumlah 0 di sebelah kiri masing-masing 1.

10001000011101 -> menjadi permutasi: {0, 3, 4, 4, 4, 1}

Solusi non rekursif menurut Knuth, contoh 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)

Anda mungkin melihat " Menghitung Subset Set Secara Efisien ", yang menggambarkan algoritma untuk melakukan bagian dari apa yang Anda inginkan - dengan cepat menghasilkan semua subset karakter N dari panjang x ke y. Ini berisi implementasi dalam C.

Untuk setiap subset, Anda masih harus menghasilkan semua permutasi. Misalnya jika Anda menginginkan 3 karakter dari "abcde", algoritme ini akan memberi Anda "abc", "abd", "abe" ... tetapi Anda harus mengubah setiap karakter untuk mendapatkan "acb", "bac", "bca", dll.

Beberapa kode Java yang berfungsi berdasarkan jawaban 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);
    }
}

Berikut adalah solusi sederhana dalam C #.

Ini hanya menghasilkan permutasi yang berbeda dari string yang diberikan.

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

Ada banyak jawaban bagus di sini. Saya juga menyarankan solusi rekursif yang sangat sederhana di 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;
    });
}

Catatan : string dengan karakter yang diulang tidak akan menghasilkan permutasi unik.

Saya baru saja menyiapkan ini dengan cepat di 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

Anda mungkin melihat ke dalam API bahasa untuk fungsi tipe permutasi bawaan, dan Anda mungkin dapat menulis kode yang lebih optimal, tetapi jika angkanya terlalu tinggi, saya tidak yakin ada banyak cara untuk mendapatkan banyak hasil .

Bagaimanapun, ide di balik kode dimulai dengan string dengan panjang 0, kemudian melacak semua string dengan panjang Z di mana Z adalah ukuran saat ini dalam iterasi. Lalu, buka setiap string dan tambahkan setiap karakter ke setiap string. Akhirnya di akhir, hapus semua yang di bawah ambang x dan kembalikan hasilnya.

Saya tidak mengujinya dengan input yang berpotensi tidak berarti (daftar karakter nol, nilai aneh x dan y, dll).

Ini adalah terjemahan dari versi Mike's Ruby, ke 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)))))

Dan versi lain, sedikit lebih pendek dan menggunakan lebih banyak fitur fasilitas loop:

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

Inilah kata sederhana solusi rekursif C #:

Metode:

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

Panggilan:

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

... dan ini adalah versi 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;
}

permute (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 * )] Untuk menghapus duplikat saat memasukkan setiap alfabet, periksa untuk melihat apakah string sebelumnya berakhir dengan alfabet yang sama (mengapa?

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

Mencetak semua permutasi tanpa duplikat

Solusi rekursif dalam 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;
            }
        }
}

Di Perl, jika Anda ingin membatasi diri ke alfabet huruf kecil, Anda dapat melakukan ini:

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

Ini memberikan semua string yang mungkin antara 1 dan 4 karakter menggunakan karakter huruf kecil. Untuk huruf besar, ubah "a"ke "A"dan "zzzz"ke "ZZZZ".

Untuk case campuran itu menjadi jauh lebih sulit, dan mungkin tidak bisa dilakukan dengan salah satu operator builtin Perl seperti itu.

Jawaban Ruby yang berfungsi:

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

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

Rekursi Java berikut ini mencetak semua permutasi dari string yang diberikan:

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

Berikut ini adalah versi terbaru dari metode "permut" di atas yang membuat n! (n faktorial) panggilan kurang rekursif dibandingkan dengan metode di atas

//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()));
   }
}

Saya tidak yakin mengapa Anda ingin melakukan ini sejak awal. Himpunan yang dihasilkan untuk setiap nilai x dan y yang cukup besar akan menjadi besar, dan akan tumbuh secara eksponensial ketika x dan / atau y bertambah besar.

Katakanlah set karakter Anda yang mungkin adalah 26 huruf kecil dari alfabet, dan Anda meminta aplikasi Anda untuk menghasilkan semua permutasi di mana panjang = 5. Dengan asumsi Anda tidak kehabisan memori Anda akan mendapatkan 11.881.376 (yaitu 26 pangkat dari 5) string kembali. Bump sepanjang itu hingga 6, dan Anda akan mendapatkan 308.915.776 string kembali. Jumlah ini menjadi sangat besar, sangat cepat.

Inilah solusi yang saya kumpulkan di Jawa. Anda harus memberikan dua argumen runtime (sesuai dengan x dan y). Selamat bersenang-senang.

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

Berikut adalah versi non-rekursif yang saya buat, dalam javascript. Itu tidak didasarkan pada yang non-rekursif Knuth di atas, meskipun memiliki beberapa kesamaan dalam pertukaran elemen. Saya telah memverifikasi kebenarannya untuk input array hingga 8 elemen.

Optimalisasi cepat akan melakukan pre-flighting pada outarray dan menghindaripush() .

Ide dasarnya adalah:

1. Diberikan array sumber tunggal, buat satu set array baru pertama yang menukar elemen pertama dengan setiap elemen berikutnya secara berurutan, setiap kali membiarkan elemen lain tidak terganggu. mis: diberikan 1234, hasilkan 1234, 2134, 3214, 4231.

2. Gunakan setiap larik dari pass sebelumnya sebagai seed untuk pass baru, tetapi alih-alih menukar elemen pertama, tukar elemen kedua dengan setiap elemen berikutnya. Juga, kali ini, jangan sertakan array asli dalam output.

3. Ulangi langkah 2 sampai selesai.

Berikut ini contoh kode:

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

Dalam ruby:

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

Ini cukup cepat, tetapi akan memakan waktu =). Tentu saja, Anda bisa mulai dari "aaaaaaaa" jika string pendek tidak menarik bagi Anda.

Saya mungkin telah salah menafsirkan pertanyaan yang sebenarnya - di salah satu posting itu terdengar seolah-olah Anda hanya membutuhkan perpustakaan string bruteforce, tetapi dalam pertanyaan utama itu terdengar seperti Anda perlu permutasi string tertentu.

Masalah Anda agak mirip dengan yang ini: http://beust.com/weblog/archives/000491.html (daftar semua bilangan bulat di mana tidak ada angka yang berulang, yang mengakibatkan banyak bahasa menyelesaikannya, dengan ocaml guy menggunakan permutasi, dan beberapa cowok java menggunakan solusi lain).

Saya membutuhkan ini hari ini, dan meskipun jawaban yang sudah diberikan mengarahkan saya ke arah yang benar, mereka tidak seperti yang saya inginkan.

Berikut ini adalah implementasi menggunakan metode Heap. Panjang array harus minimal 3 dan untuk pertimbangan praktis tidak boleh lebih dari 10 atau lebih, tergantung pada apa yang ingin Anda lakukan, kesabaran dan kecepatan clock.

Sebelum Anda memasukkan loop, inisialisasi Perm(1 To N)dengan permutasi pertama, Stack(3 To N)dengan nol *, dan Leveldengan 2**. Di akhir panggilan loop NextPerm, yang akan mengembalikan false ketika kita selesai.

* VB akan melakukannya untuk Anda.

** Anda dapat mengubah NextPerm sedikit untuk membuat ini tidak perlu, tetapi lebih jelas seperti ini.

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

Metode lain dijelaskan oleh berbagai penulis. Knuth menjelaskan dua, satu memberikan urutan leksikal, tetapi rumit dan lambat, yang lain dikenal sebagai metode perubahan biasa. Jie Gao dan Dianjun Wang juga menulis makalah yang menarik.

Kode ini dalam python, ketika dipanggil dengan allowed_charactersset ke [0,1]dan 4 karakter maks, akan menghasilkan 2 ^ 4 hasil:

['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()

Semoga ini berguna bagi Anda. Bekerja dengan karakter apa pun, tidak hanya angka

Berikut ini tautan yang menjelaskan cara mencetak permutasi string. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

Meskipun ini tidak menjawab pertanyaan Anda dengan tepat, inilah salah satu cara untuk menghasilkan setiap permutasi huruf dari sejumlah string yang sama panjangnya: misalnya, jika kata-kata Anda adalah "kopi", "joomla" dan "moodle", Anda dapat mengharapkan output seperti "coodle", "joodee", "joffle", dll.

Pada dasarnya, jumlah kombinasi adalah (jumlah kata) dengan kekuatan (jumlah huruf per kata). Jadi, pilih angka acak antara 0 dan jumlah kombinasi - 1, konversikan angka itu menjadi basis (jumlah kata), lalu gunakan setiap digit angka itu sebagai indikator dari mana kata untuk mengambil huruf berikutnya.

misalnya: dalam contoh di atas. 3 kata, 6 huruf = 729 kombinasi. Pilih nomor acak: 465. Konversikan ke basis 3: 122020. Ambil huruf pertama dari kata 1, 2 dari kata 2, 3 dari kata 2, 4 dari kata 0 ... dan Anda mendapatkan ... "joofle".

Jika Anda menginginkan semua permutasi, hanya loop dari 0 hingga 728. Tentu saja, jika Anda hanya memilih satu nilai acak, cara yang jauh lebih sederhana dan tidak membingungkan adalah dengan mengulangi huruf-huruf. Metode ini memungkinkan Anda menghindari rekursi, jika Anda ingin semua permutasi, plus itu membuat Anda terlihat seperti Anda tahu Matematika ^(tm) !

Jika jumlah kombinasi berlebihan, Anda dapat memecahnya menjadi serangkaian kata yang lebih kecil dan menyatukannya di akhir.

c # iterative:

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

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

Ini adalah pendapat saya tentang versi non rekursif

Solusi pythonic:

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

Nah, inilah solusi yang elegan, non-rekursif, 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;
    }