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

Translate

Comment pourrais-je générer une liste de toutes les permutations possibles d'une chaîne entre les caractères x et y de longueur, contenant une liste variable de caractères.

N'importe quelle langue fonctionnerait, mais elle devrait être portable.

This question and all comments follow the "Attribution Required."

Toutes les réponses

Translate

Il y a plusieurs moyens de le faire. Les méthodes courantes utilisent la récursivité, la mémorisation ou la programmation dynamique. L'idée de base est de produire une liste de toutes les chaînes de longueur 1, puis à chaque itération, pour toutes les chaînes produites dans la dernière itération, ajoutez cette chaîne concaténée avec chaque caractère de la chaîne individuellement. (l'index variable dans le code ci-dessous garde une trace du début de la dernière et de la prochaine itération)

Quelques pseudocodes:

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)

vous devrez alors supprimer toutes les chaînes de moins de x de longueur, ce seront les premières entrées (x-1) * len (originalString) de la liste.

La source
Translate

Il vaut mieux utiliser le retour en arrière

#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;
}
La source
Translate

Vous allez avoir beaucoup de cordes, c'est sûr ...

\ sum_ {i = x} ^ y {\ frac {r!} {{(ri)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20% 7B% 20% 5Cfrac% 7Br!% 7D% 7B% 7B (ri)% 7D!% 7D% 20% 7D
Où, x et y sont 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 devez absolument les générer au besoin et ne pas être bâclé et dire, générer un ensemble de pouvoirs, puis filtrer la longueur des chaînes.

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

Knuth (volume 4, fascicule 2, 7.2.1.3) nous dit que la combinaison (s, t) équivaut à s + 1 choses prises t à la fois avec répétition - une combinaison (s, t) est la notation Knuth qui est égal à{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 combinaison (s, t) 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}

La source
Maggie Lee
Translate

Solution non récursive selon Knuth, exemple 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)
La source
Carey Lee
Translate

Vous pourriez regarder "Énumération efficace des sous-ensembles d'un ensemble", qui décrit un algorithme pour faire une partie de ce que vous voulez - générez rapidement tous les sous-ensembles de N caractères de longueur x à y. Il contient une implémentation en C.

Pour chaque sous-ensemble, vous devrez toujours 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 devrez permuter chacun pour obtenir "acb", "bac", "bca", etc.

La source
Translate

Du code Java fonctionnel basé surRéponse de 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);
    }
}
La source
Gilbert Lee
Translate

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;
        }
    }
La source
Maggie Lee
Translate

Il y a beaucoup de bonnes réponses ici. Je suggère également 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;
    });
}

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

La source
Aurora Lee
Translate

Je viens de fouetter cela rapidement dans 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 vous pencher sur l'API de langage pour les fonctions de type permutation intégrées, et vous pourrez peut-être écrire du code plus optimisé, mais si les chiffres sont si élevés, je ne suis pas sûr qu'il existe un moyen de contourner beaucoup de résultats .

Quoi qu'il en soit, l'idée derrière le code est de commencer par une chaîne de longueur 0, puis de suivre toutes les chaînes de longueur Z où Z est la taille actuelle dans l'itération. Ensuite, parcourez chaque chaîne et ajoutez chaque caractère à chaque chaîne. Enfin, à la fin, supprimez tous ceux qui étaient inférieurs au seuil x et renvoyez le résultat.

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

La source
Stacey Lee
Translate

Ceci est 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 fonctionnalités 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)))))
La source
Heloise Lee
Translate

Voici une solution récursive C # avec un mot simple:

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);
La source
Vera Lee
Translate

En Perl, si vous souhaitez 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. Pour les majuscules, changez"a"à"A"et"zzzz"à"ZZZZ".

Pour les cas mixtes, cela devient beaucoup plus difficile, et probablement impossible avec l'un des opérateurs intégrés de Perl comme celui-là.

La source
Cash Lee
Translate

... et voici la version 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;
}
La source
Bradley Lee
Translate

permute (ABC) -> A.perm (BC) -> A.perm [B.perm (C)] -> A.perm [(*BC), (CB*)] -> [(*ABC), (BAC), (BCA*), (*ACB), (CAB), (CBA*)] Pour supprimer les doublons lors de l'insertion de chaque alphabet, vérifiez si la chaîne précédente se termine par le même alphabet (pourquoi? -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

La source
Justin Lee
Translate

Réponse 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")
La source
Wordsworth Lee
Translate

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 source
Dempsey Lee
Translate

La récursivité 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);
    }
}

Voici la version mise à jour de la méthode "permut" ci-dessus qui fait 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()));
   }
}
La source
Translate
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;
    }
}
La source
Victoria Lee
Translate

Voici une version non récursive que j'ai imaginée, en javascript. Il n'est pas basé sur celui non récursif de Knuth ci-dessus, bien qu'il présente certaines 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 consisterait à pré-voler leouttableau et éviterpush().

L'idée de base est:

  1. Étant donné un tableau source unique, générez un premier nouvel ensemble de tableaux qui permutent le premier élément avec chaque élément suivant à tour de rôle, en laissant à chaque fois les autres éléments imperturbables. par exemple: donné 1234, génère 1234, 2134, 3214, 4231.

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

  3. Répétez l'étape 2 jusqu'à ce que vous ayez terminé.

Voici l'exemple de code:

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;
}
La source
Translate

Je ne sais pas pourquoi vous voudriez faire cela en premier lieu. L'ensemble résultant pour toutes les valeurs modérément grandes de x et y sera énorme et augmentera de façon exponentielle à mesure que x et / ou y grossiront.

Supposons que votre jeu de caractères possibles soit les 26 lettres minuscules de l'alphabet, et que vous demandiez à 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 au pouvoir de 5) cordes en arrière. Augmentez cette longueur jusqu'à 6, et vous obtiendrez 308 915 776 cordes. Ces chiffres deviennent extrêmement élevés, 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). S'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);
            }
        }
    }
}
La source
Sylvia Lee
Translate

J'en avais besoin aujourd'hui, et bien que les réponses déjà données m'ont pointé dans 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 d'au moins 3 et pour des raisons pratiques, pas plus de 10 ou plus, en fonction de ce que vous voulez faire, de la patience et de la vitesse d'horloge.

Avant d'entrer dans votre boucle, initialisezPerm(1 To N)avec la première permutation,Stack(3 To N)avec des zéros *, etLevelavec2**. À la fin de l'appel en boucleNextPerm, qui renverra false lorsque nous aurons terminé.

* VB le fera pour vous.

** Vous pouvez modifier un peu NextPerm pour rendre 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 en décrit deux, l'un donne un 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.

La source
Sara Lee
Translate

En rubis:

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

C'est assez rapide, mais ça va prendre du temps =). Bien sûr, vous pouvez commencer par "aaaaaaaa" si les chaînes courtes ne vous intéressent pas.

J'aurais peut-être mal interprété la question réelle - dans l'un des articles, cela semblait comme si vous aviez juste besoin d'une bibliothèque de chaînes bruteforce, mais dans la question principale, il semble que vous deviez permuter une chaîne particulière.

Votre problème est un peu similaire à celui-ci:http://beust.com/weblog/archives/000491.html(listez tous les nombres entiers dans lesquels aucun des chiffres ne se répète, ce qui a abouti à une résolution de ce problème par de nombreux langages, avec le type ocaml utilisant des permutations, et un type Java utilisant encore une autre solution).

La source
Translate

Ce code en python, lorsqu'il est appelé avecallowed_charactersmis à[0,1]et 4 caractères maximum, 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, pas seulement des nombres

La source
Translate

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

La source
Baron Lee
Translate

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 même longueur: par exemple, si vos mots étaient «café», «joomla» et «moodle», vous pouvez attendez-vous à une sortie comme "coodle", "joodee", "joffle", etc.

Fondamentalement, le nombre de combinaisons est le (nombre de mots) à la puissance de (nombre de lettres par mot). Alors, 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 du mot à partir duquel 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 vous obtenez ... "joofle".

If you wanted all the permutations, just loop from 0 to 728. Of course, if you're just choosing one random value, a much simpler Une manière moins déroutante serait de faire une boucle sur les lettres. Cette méthode vous permet d'éviter la récursivité, si vous voulez toutes les permutations, en plus elle vous donne l'impression de connaître les mathématiques(tm)!

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

La source
Rosemary Lee
Translate

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;
    }
La source
Ina Lee
Translate
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
La source
Eric Lee
Translate
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 source
Bing Lee
Translate

La solution pythonique:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
La source
Alan Lee
Translate

Eh bien, voici une solution élégante, non récursive, 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;
    }
La source