Générer la liste de toutes les permutations possibles d'une chaîne

il est préférable d'utiliser le retracage

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

vous allez avoir beaucoup de ficelles, c'est sûr...

\ 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

Où, x et y est la façon dont vous les définissez et r est le nombre de caractères que nous sélectionnons, si je vous comprends bien. Vous devriez certainement générer ces derniers au besoin et ne pas être négligent et dire, générez un powerset et filtrez la longueur des chaînes.

ce qui suit n'est certainement pas la meilleure façon de générer ceux-ci, mais c'est un côté intéressant, néanmoins.

Knuth (volume 4, fascicule 2, 7.2.1.3) nous dit que (s,t)-combinaison est équivalente à s+1 choses prises t à un moment avec répétition -- an (s, t) - combinaison est notation utilisée par Knuth qui est égale à {t \choose {s+t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D % 7D . Nous pouvons comprendre cela en générant d'abord chaque (s,t)-combinaison sous forme binaire (donc de longueur (s+t)) et en comptant le nombre de " 0 " à gauche de chaque 1.

10001000011101 -- > devient la permutation: {0, 3, 4, 4, 4, 1}

Non récursif de la solution en fonction de Knuth, Python exemple:

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)

vous pourriez regarder" énumérer efficacement les sous - ensembles d'un ensemble ", qui décrit un algorithme pour faire une partie de ce que vous voulez-générer rapidement tous les sous-ensembles de n caractères de la longueur x à Y. Il contient une implémentation en C.

pour chaque sous-ensemble, vous devez encore générer toutes les permutations. Par exemple, si vous vouliez 3 caractères de "abcde", cet algorithme vous donnerait "abc","abd", "abe"... mais vous auriez à permuter chacun d'obtenir "pbr", "bac", "bca", etc.

travail code Java basé sur de la Sarp réponse :

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

Voici une solution simple en C#.

Il ne génère que les permutations distinctes d'une chaîne donnée.

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

Il y a beaucoup de bonnes réponses ici. Je suggère aussi une solution récursive très simple en 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;
    });
}

Note : les chaînes à caractères répétés ne produiront pas de permutations uniques.

je viens de le faire en 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

vous pourriez regarder dans L'API de langue pour Construit dans les fonctions de type de permutation, et vous pourriez être en mesure d'écrire du code plus optimisé, mais si les nombres sont tous si élevés, Je ne suis pas sûr qu'il ya beaucoup de chemin autour d'avoir beaucoup de résultats.

de toute façon, l'idée derrière le code est de commencer par la chaîne de longueur 0, puis garder la trace de toutes les chaînes de longueur Z où Z est la taille actuelle dans itération. Ensuite, passez en revue chaque chaîne et ajoutez chaque caractère à chaque chaîne. Enfin, à la fin, supprimez ceux qui se situent sous le seuil x et retournez le résultat.

Je ne l'ai pas testé avec des entrées potentiellement dénuées de sens (liste de caractères nuls, valeurs bizarres de x et y, etc.).

il s'agit d'une traduction de la version Ruby de Mike, en 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)))))

et une autre version, légèrement plus courte et utilisant plus de caractéristiques de facilité de boucle:

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

voici un simple mot C # solution récursive:

méthode:

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

appel:

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

en Perl, si vous voulez vous limiter à l'alphabet en minuscules, vous pouvez le faire:

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

cela donne toutes les chaînes possibles entre 1 et 4 caractères en utilisant des caractères minuscules. En majuscule, remplacer "a" par "A" et "zzzz" par "ZZZZ" .

pour mixte-cas il devient beaucoup plus difficile,et probablement pas faisable avec un des opérateurs de Perl comme cela.

... et voici la version C:

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

permuter (ABC) -> A. perm(colombie-britannique) -> A. perm[B. perm(C)] -> A. perm[( *B C), (C B* )] -> [( *UN BC), (B UN C"), (BC UN* ), ( *UN CB), (C UN B), (CB A* )] De supprimer les doublons lors de l'insertion de chaque alphabet vérifier si la chaîne précédente se termine avec le même alphabet (pourquoi? -l'exercice)

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

Imprime toutes les permutations sans doublons

réponse de Ruby qui fonctionne:

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

solution Récursive en 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;
            }
        }
}

la récursion Java suivante imprime toutes les permutations d'une chaîne donnée:

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

ci-dessous est la version mise à jour de la méthode "permut" ci-dessus qui rend n! (n factoriel) moins d'appels récursifs par rapport à la méthode ci-dessus

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

Je ne sais pas pourquoi vous voudriez faire ça. L'ensemble résultant pour n'importe quelles valeurs modérément grandes de x et y sera énorme, et croîtra exponentiellement que x et/ou y deviennent plus grand.

permet de dire que votre ensemble de caractères possibles est les 26 lettres minuscules de l'alphabet, et vous demandez à votre application de générer toutes les permutations où longueur = 5. En supposant que vous ne manquiez pas de mémoire, vous obtiendrez 11 881 376 (soit 26 à la puissance de 5) cordes de retour. Passez cette longueur à 6, et vous obtiendrez 308 915 776 cordes de retour. Ces nombres deviennent douloureusement grands, très rapidement.

Voici une solution que j'ai mise en place en Java. Vous devrez fournir deux arguments d'exécution (correspondant à x et y). Amuser.

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

Voici une version non-récursive que j'ai créée, en javascript. Il n'est pas basé sur le non-récursif de Knuth ci-dessus, bien qu'il ait quelques similitudes dans l'échange d'éléments. J'ai vérifié son exactitude pour les tableaux d'entrée jusqu'à 8 éléments.

une optimisation rapide serait de pré-Flighter le tableau out et d'éviter push() .

l'idée de base est:

1. à source unique tableau, générer un premier ensemble de tableaux qui échangent le premier élément avec chaque élément suivant tour à tour, chaque fois laissant les autres éléments non perturbés. eg: donné 1234, générer 1234, 2134, 3214, 4231.

2. utilisez chaque tableau de la passe précédente comme la graine pour une nouvelle passe, mais au lieu d'échanger le premier élément, changez le deuxième élément avec chaque élément suivant. Aussi, cette fois, n'incluez pas le tableau original dans la sortie.

3. répétez l'étape 2 jusqu'à ce que ce soit fait.

voici le code échantillon:

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

j'en avais besoin aujourd'hui, et bien que les réponses déjà données m'aient indiqué la bonne direction, elles n'étaient pas tout à fait ce que je voulais.

Voici une implémentation utilisant la méthode de Heap. La longueur du tableau doit être au moins 3 et pour des considérations pratiques ne pas être plus grand que 10 ou ainsi, selon ce que vous voulez faire, la patience et la vitesse d'horloge.

avant d'entrer dans votre boucle, initialisez Perm(1 To N) avec la première permutation, Stack(3 To N) avec des zéros*, et Level avec 2 **. À la fin de la boucle , appelez NextPerm , qui retournera false quand nous aurons fini.

* VB le fera pour vous.

** Vous pouvez modifier NextPerm un peu pour faire cela inutile, mais c'est plus clair comme ça.

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

d'Autres méthodes sont décrites par divers auteurs. Knuth décrit deux, l'un donne l'ordre lexical, mais est complexe et lent, l'autre est connu comme la méthode des changements simples. Jie Gao et Dianjun Wang ont également écrit un article intéressant.

en rubis:

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

, Il est assez rapide, mais ça va prendre un peu de temps =). Bien sûr, vous pouvez commencer à "aaaaaaaa" si les cordes courtes ne sont pas intéressantes pour vous.

j'ai peut - être mal interprété la question actuelle cependant-dans un des billets, il semblait que vous aviez juste besoin d'une bibliothèque de cordes bruteforce, mais dans la question principale, il semble que vous ayez besoin de permuter une chaîne particulière.

votre le problème est un peu similaire à celui-ci: http://beust.com/weblog/archives/000491.html (liste de tous les entiers dans laquelle aucun des chiffres se répètent, ce qui a entraîné tout un tas de langues résoudre, avec ocaml mec à l'aide de permutations, et certaines java gars de l'utiliser encore une autre solution).

ce code en python, lorsqu'il est appelé avec allowed_characters défini à [0,1] et 4 caractères max, générerait 2^4 résultats:

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

J'espère que cela vous sera utile. Fonctionne avec n'importe quel caractère ,non seulement des nombres

voici un lien qui décrit comment imprimer les permutations d'une chaîne. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

bien que cela ne réponde pas exactement à votre question, voici une façon de générer chaque permutation des lettres à partir d'un certain nombre de chaînes de la même longueur: par exemple, si vos mots étaient" café"," joomla "et" moodle", vous pouvez vous attendre à la sortie comme" coodle"," joodee"," joffle", etc.

en fait, le nombre de combinaisons est l' (nombre de mots) à la puissance (nombre de lettres par mot). Ainsi, choisissez un nombre aléatoire entre 0 et le nombre de combinaisons - 1, convertissez ce nombre en base (nombre de mots), puis utilisez chaque chiffre de ce nombre comme indicateur pour lequel mot pour prendre la lettre suivante.

par exemple: dans l'exemple ci-dessus. 3 mots, 6 lettres = 729 combinaisons. Choisissez un nombre aléatoire: 465. Convertissez en base 3: 122020. Prenez la première lettre du mot 1, la deuxième du mot 2, la troisième du mot 2, la quatrième du mot 0... et que vous obtenez... "joofle".

si vous voulez toutes les permutations, faites une boucle de 0 à 728. De bien sûr, si vous choisissez juste une valeur aléatoire, une façon beaucoup plus simple moins déroutante serait de boucler sur les lettres. Cette méthode vous permet d'éviter la récursion, si vous voulez toutes les permutations, plus il vous fait ressembler à vous connaissez les mathématiques ^(tm) !

si le nombre de combinaisons est excessif, vous pouvez le décomposer en une série de mots plus petits et les concaténer à la fin.

c # itératif:

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

il y a une implémentation Java itérative dans UncommonsMaths (fonctionne pour une liste d'objets):

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

source

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

Voici mon point de vue sur une version non récursive

la solution pythonique:

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