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

Réponses:

70

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

alumb
la source
4
Pourquoi d'abord stocker la liste des éléments, puis l'effacer? (en référence aux lignes 1 et 3 du pseudo-code).
Håvard Geithus
6
Qu'est-ce que y (ligne 4)?
Jaseem
7
@Jaseem De la question: "toutes les permutations possibles d'une chaîne entre les caractères x et y de longueur"
ck_
39

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;
}
Unnykrishnan S
la source
3
Meilleure solution everrrrrrrrr
GrowinMan
25

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

\ sum_ {i = x} ^ y {\ frac {r!} {{(ri)}!}}
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 aparté 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 utilisée par Knuth qui est égal à {t \ choose {s + t}. 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}

nlucaroni
la source
15

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)
rochesportrocker
la source
2
En fait, cela ne fonctionne pas lorsque la chaîne n'est pas triée. Si vous essayez avec "54321"seulement UNE chaîne est montré (lui - même).
tonjo
1
Ce qui nextPermutation()est intéressant, c'est qu'il est sans état - il suffit de l'entrée pour permuter et les index ne sont pas conservés d'une itération à l'autre. Il est capable de le faire en supposant que l'entrée initiale a été triée et en trouvant des index ( k0et l0) elle-même, en fonction de l'endroit où l'ordre est conservé. Le tri d'une entrée comme "54321" -> "12345" permettrait à cet algorithme de trouver toutes les permutations attendues. Mais comme cela fait beaucoup de travail supplémentaire pour retrouver ces index pour chaque permutation qu'il génère, il existe des moyens plus efficaces de le faire de manière non récursive.
spaaarky21
13

Vous pouvez consulter « É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érer 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.

AShelly
la source
13

Un code Java fonctionnel basé sur la ré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);
    }
}
Lazer
la source
En commentaire, notez que pour une chaîne avec des caractères répétés, cela ne produira pas les permutations uniques. Cela pourrait être résolu avec un hachage, mais cela pourrait être un problème avec de longues chaînes.
Glenn
8
Vous voudrez peut-être utiliser des tableaux de caractères au lieu de chaînes pour accélérer cette exécution, car les chaînes sont immuables en java.
Abhijeet Kashnia
13

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;
        }
    }
Prakhar Gupta
la source
12

Il y a beaucoup de bonnes réponses ici. Je propose é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.

gd1
la source
9

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 nombres 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 garder une trace de 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 en dessous du 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.).

Mike Stone
la source
11
Ce code est erroné. Cela générera des permutations invalides, telles que celles avec des caractères répétés. Par exemple, pour la chaîne "abc", il génère ces permutations de taille 3: ["aaa", "aab", "aac", "aba", "abb", "abc", "aca", "acb", "acc", "baa", "bab", "bac", "bba", "bbb", "bbc", "bca", "bcb", "bcc", "caa", "cab", "cac "," cba "," cbb "," cbc "," cca "," ccb "," ccc "]. Ceci est une erreur.
pmc255
8

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)))))
Martin
la source
8

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);
Crackerjack
la source
8

... 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;
}
Peyman
la source
8

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 * )] 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

raj
la source
8

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;
            }
        }
}
Sarp Centel
la source
7

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" en "A"et "zzzz"en "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à.

Chris Lutz
la source
7

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")
Kem Mason
la source
Pour une doublure fantaisie en Ruby: stackoverflow.com/questions/5773961/…
dojosto
6
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;
    }
}
Swapneel Patil
la source
6

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()));
   }
}
Ramy
la source
C'est la solution la plus propre, et je crois l'avoir déjà vue dans le livre "Cracking the Coding Interview"
Tao Zhang
1
@TaoZhang merci pour le complément, je ne l'ai pas copié de n'importe où mais il est possible que quelqu'un ait créé un algo similaire. Quoi qu'il en soit, j'ai mis à jour le code ci-dessus pour les appels moins récursifs
Ramy
5

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 deviendront plus grands.

Disons que votre jeu de caractères possibles est constitué des 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 manquez 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);
            }
        }
    }
}
Brian Willis
la source
Longtemps mais ne les générez-vous pas avec répétition?
Kakira
5

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 la outbaie 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 inchangés. 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, remplacez le deuxième élément par 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;
}
orion elenzil
la source
3

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 à un grand nombre de langues le résolvant, avec le ocaml guy utilisant des permutations, et certains gars java utilisant encore une autre solution).

bOR_
la source
Un problème avec votre proposition est que str.next! n'itérera pas sur tous les caractères imprimables. Votre exemple ne générera que des lettres minuscules - pas de ponctuation ni de majuscules.
Jarsen
3

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, 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 Levelavec 2**. À la fin de l'appel en boucleNextPerm , qui retournera 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.

Lâche anonyme
la source
2

Ce code en python, lorsqu'il est appelé avec allowed_charactersset to [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, pas seulement des nombres

Aminah Nuraini
la source
Ce ne sont pas des permutations mais une sélection de sous-ensembles, c'est-à-dire ABC & 001 = C alors qu'une permutation valide doit avoir les trois caractères.
Schultz9999
euh? désolé je ne comprends pas ce que vous dites. Si vous le corrigez, laissez une version fixe, je vais la communauté wiki la chose
droope
0

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

Si vous vouliez toutes les permutations, faites une boucle de 0 à 728. Bien sûr, si vous ne choisissez qu'une seule valeur aléatoire, une manière beaucoup plus simple et moins déroutante serait de parcourir les lettres. Cette méthode vous permet d'éviter la récursivité, si vous voulez toutes les permutations, et vous donne l'impression de connaître Maths (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.

nickf
la source
0

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;
    }
wliao
la source
0
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
abkds
la source
0
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

Crâne
la source
0

La solution pythonique:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
Abdul Fatir
la source
0

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;
    }
Adilli Adil
la source