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

voix
143

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

Toute langue fonctionnerait, mais il devrait être portable.

Créé 02/08/2008 à 07:57
source utilisateur
Dans d'autres langues...                            


35 réponses

voix
67

Il y a plusieurs moyens de le faire. Les méthodes courantes utilisent récursion, memoization ou programmation dynamique. L'idée de base est que vous produisez 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, ajouter cette chaîne concaténée avec chaque caractère dans la chaîne individuellement. (L'indice variable dans le code ci-dessous permet de suivre le début de la dernière et la prochaine itération)

Certains pseudo-code:

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 auriez besoin alors de supprimer toutes les chaînes moins de x longueur, ils seront les premières entrées (x-1) * len (originalString) dans la liste.

Créé 02/08/2008 à 08:48
source utilisateur

voix
35

Il est préférable d'utiliser retours 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;
}
Créé 10/01/2012 à 19:00
source utilisateur

voix
24

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 de% 7B% 7B (ri) de% 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 à partir - -si Je vous comprends bien. Vous devez certainement générer ces au besoin et non bâclée et se dire générer un powerset puis filtrer la longueur des chaînes.

Ce qui suit est certainement pas la meilleure façon de générer ces derniers, mais il est un intéressant côté, cependant pas le moins.

Knuth (volume 4, 2 fascicle, 7.2.1.3) nous dit que (s, t) -combination équivaut à s + 1 choses prises t à la fois avec la répétition - un (s, t) est -combination notation utilisée par Knuth qui est égal à {t \ {choisir s + t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D . On peut comprendre cela en générant d' abord chaque (s, t) -combination sous forme binaire (donc, de longueur (s + t)) et en comptant le nombre de 0 à de la gauche de chaque 1.

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

Créé 05/08/2008 à 05:57
source utilisateur

voix
14

Solution non récursif selon Knuth, par 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)
Créé 09/11/2010 à 14:58
source utilisateur

voix
12

Il y a beaucoup de bonnes réponses ici. Je suggère également une solution très simple récursive 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 produisent pas des permutations uniques.

Créé 08/01/2014 à 12:00
source utilisateur

voix
12

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;
        }
    }
Créé 05/07/2010 à 10:06
source utilisateur

voix
12

Une partie du code Java de travail 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);
    }
}
Créé 04/04/2010 à 19:18
source utilisateur

voix
12

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

Pour chaque sous-ensemble, vous auriez 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 permutant chacun pour obtenir « PBR », « bac », "BCA", etc.

Créé 14/11/2008 à 20:36
source utilisateur

voix
8

Je viens fouetté ce haut rapide 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 pouvez regarder dans API de langage pour des fonctions intégrées de type de permutation, et vous pourriez être en mesure d'écrire du code plus optimisé, mais si les chiffres sont si élevés, je ne suis pas sûr qu'il ya beaucoup de chemin autour d'avoir beaucoup de résultats .

Quoi qu'il en soit, l'idée derrière le code est de commencer avec la chaîne de longueur 0, puis garder une trace de toutes les chaînes de longueur Z où Z est la taille actuelle dans l'itération. Ensuite, passez par chaque chaîne et ajoutez chaque caractère sur chaque chaîne. Enfin, à la fin, supprimer ceux qui étaient au-dessous du seuil de x et retourner le résultat.

Je n'ai pas testé avec entrée potentiellement vide de sens (liste des caractères nuls, les valeurs étranges de x et y, etc.).

Créé 02/08/2008 à 08:56
source utilisateur

voix
7

Ruby réponse 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")
Créé 20/04/2012 à 01:21
source utilisateur

voix
7

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 chèque de l' alphabet pour voir 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

Créé 22/02/2011 à 19:45
source utilisateur

voix
7

... 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;
}
Créé 07/02/2011 à 22:56
source utilisateur

voix
7

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. Pour les majuscules, changer "a"à "A"et "zzzz"à "ZZZZ".

Pour mixte cas, il devient beaucoup plus difficile, et probablement pas faisable avec l'un des opérateurs de Perl builtin comme ça.

Créé 15/02/2009 à 11:02
source utilisateur

voix
7

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);
Créé 20/10/2008 à 01:17
source utilisateur

voix
7

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;
            }
        }
}
Créé 29/09/2008 à 02:34
source utilisateur

voix
7

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 en utilisant plus de fonctionnalités de l'installation de la 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)))))
Créé 16/09/2008 à 06:15
source utilisateur

voix
6

Les impressions récursion Java suivantes 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! (Factorielle n) appels récursifs moins 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()));
   }
}
Créé 19/06/2013 à 05:23
source utilisateur

voix
5

Voici une version non récursif je suis venu avec, en javascript. Il est pas fondée sur un non récurrent de Knuth ci-dessus, même si elle a quelques similitudes dans swapping élément. Je l'ai vérifié l'exactitude des tableaux d'entrée jusqu'à 8 éléments.

Une optimisation rapide serait pré-flighting le outtableau et éviter push().

L'idée de base est le suivant:

  1. Etant donné une matrice unique source, générer un premier nouvel ensemble de tableaux qui échangent le premier élément à chaque élément subséquent à son tour, chaque fois en laissant les autres éléments non perturbé. par exemple: donné 1234, générer 1234, 2134, 3214, 4231.

  2. Utiliser chaque réseau à partir de la passe précédente en tant que germe pour une nouvelle passe, mais au lieu de l'échange du premier élément, le second élément échanger avec chaque élément subséquent. De plus, cette fois-ci, ne comprennent pas le tableau original dans la sortie.

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

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;
}
Créé 03/08/2011 à 08:11
source utilisateur

voix
5
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;
    }
}
Créé 24/10/2010 à 23:01
source utilisateur

voix
4

Je ne sais pas pourquoi vous voulez faire en premier lieu. L'ensemble résultant pour toutes les valeurs modérément élevées de x et y sera énorme, et augmentera de manière exponentielle x et / ou y grossir.

Disons que votre jeu de caractères possibles sont les 26 lettres minuscules de l'alphabet, et vous demandez à votre application pour générer toutes les permutations où la longueur = 5. En supposant que vous ne courez pas de mémoire que vous obtiendrez 11.881.376 (soit 26 à la puissance 5) Les chaînes arrière. Bump cette longueur jusqu'à 6, et vous aurez 308,915,776 dos lacé. Ces chiffres se douloureusement grand, très rapidement.

Voici une solution que je mets ensemble 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);
            }
        }
    }
}
Créé 02/08/2008 à 10:40
source utilisateur

voix
3

Je avais besoin aujourd'hui, et bien que les réponses déjà données m'a orienté dans la bonne direction, ils étaient pas tout à fait ce que je voulais.

Voici une mise en oeuvre en 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 si, en fonction de ce que vous voulez faire, la patience et de la vitesse d'horloge.

Avant d'entrer dans la boucle, initialiser Perm(1 To N)avec la première permutation, Stack(3 To N)avec des zéros * et Levelavec 2**. A la fin de l'appel en boucle NextPerm, qui retournera faux quand nous aurons terminé.

* VB fera pour vous.

** Vous pouvez changer NextPerm un peu pour faire cela inutile, mais il 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, on 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 a également écrit un article intéressant.

Créé 02/10/2011 à 10:13
source utilisateur

voix
2

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

Créé 13/02/2014 à 22:08
source utilisateur

voix
2

Ce code en python, lorsqu'il est appelé avec allowed_charactersjeu à [0,1]et 4 caractères au 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()

Espérons que cela est utile pour vous. Fonctionne avec tous les caractères, chiffres non seulement

Créé 26/05/2011 à 15:22
source utilisateur

voix
2

En ruby:

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

Il est très rapide, mais il va prendre un certain temps =). Bien sûr, vous pouvez commencer à « aaaaaaaa » si les chaînes courtes ne sont pas intéressants pour vous.

Je pourrais avoir mal interprété la question réelle bien - dans l'un des postes, il aurait dit que si vous aviez juste besoin d'une bibliothèque bruteforce de cordes, mais la principale question, il semble que vous devez permuter une chaîne particulière.

Votre problème est un peu similaire à celui - ci: http://beust.com/weblog/archives/000491.html (liste tous les entiers dans lesquels aucun des chiffres se répéter, ce qui a entraîné beaucoup de langues résoudre, avec le guy OCaml à l' aide de permutations, et un type java en utilisant une autre solution).

Créé 15/09/2008 à 18:32
source utilisateur

voix
0

Les permutations de chaînes possibles peuvent être calculées en utilisant la fonction récursive. Ci-dessous l'une des solutions possibles.

public static String insertCharAt(String s, int index, char c) {
        StringBuffer sb = new StringBuffer(s);
        StringBuffer sbb = sb.insert(index, c);
        return sbb.toString();
}

public static ArrayList<String> getPerm(String s, int index) {
        ArrayList<String> perm = new ArrayList<String>();

        if (index == s.length()-1) {
            perm.add(String.valueOf(s.charAt(index)));
            return perm;
        }

        ArrayList<String> p = getPerm(s, index+1);
        char c = s.charAt(index);

        for(String pp : p) {
            for (int idx=0; idx<pp.length()+1; idx++) {
                String ss = insertCharAt(pp, idx, c);
                perm.add(ss);
            }
        }

        return perm;    
}

public static void testGetPerm(String s) {
        ArrayList<String> perm = getPerm(s,0);
        System.out.println(s+" --> total permutation are :: "+perm.size());
        System.out.println(perm.toString());
}
Créé 06/02/2017 à 06:00
source utilisateur

voix
0

code écrit pour le langage Java:

namo.algorithms de paquets;

importation java.util.Scanner;

Permuations public class {

public static int totalPermutationsCount = 0;
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("input string : ");
        String inputString = sc.nextLine();
        System.out.println("given input String ==> "+inputString+ " :: length is = "+inputString.length());
        findPermuationsOfString(-1, inputString);
        System.out.println("**************************************");
        System.out.println("total permutation strings ==> "+totalPermutationsCount);
    }


    public  static void findPermuationsOfString(int fixedIndex, String inputString) {
        int currentIndex = fixedIndex +1;

        for (int i = currentIndex; i < inputString.length(); i++) {
            //swap elements and call the findPermuationsOfString()

            char[] carr = inputString.toCharArray();
            char tmp = carr[currentIndex];
            carr[currentIndex] = carr[i];
            carr[i] = tmp;
            inputString =  new String(carr);

            //System.out.println("chat At : current String ==> "+inputString.charAt(currentIndex));
            if(currentIndex == inputString.length()-1) {
                totalPermutationsCount++;
                System.out.println("permuation string ==> "+inputString);
            } else {
                //System.out.println("in else block>>>>");
                findPermuationsOfString(currentIndex, inputString);
                 char[] rarr = inputString.toCharArray();
                    char rtmp = carr[i];
                    carr[i] = carr[currentIndex];
                    carr[currentIndex] = rtmp;
                    inputString =  new String(carr);
            }
        }
    }

}

Créé 05/06/2016 à 08:42
source utilisateur

voix
0

Eh bien voici une solution élégante, non récurrente, 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;
    }
Créé 27/06/2015 à 08:44
source utilisateur

voix
0

La solution pythonique:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
Créé 13/07/2014 à 08:51
source utilisateur

voix
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 avis sur une version non récurrente

Créé 23/01/2014 à 04:28
source utilisateur

voix
0

Solution récursive avec chauffeur main()méthode.

public class AllPermutationsOfString {
public static void stringPermutations(String newstring, String remaining) {
    if(remaining.length()==0)
        System.out.println(newstring);

    for(int i=0; i<remaining.length(); i++) {
        String newRemaining = remaining.replaceFirst(remaining.charAt(i)+"", "");
        stringPermutations(newstring+remaining.charAt(i), newRemaining);
    }
}

public static void main(String[] args) {
    String string = "abc";
    AllPermutationsOfString.stringPermutations("", string); 
}

}

Créé 19/10/2013 à 02:34
source utilisateur

voix
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
Créé 22/08/2013 à 18:51
source utilisateur

voix
0

Une solution récursive en python. La bonne chose à propos de ce code est qu'il exporte un dictionnaire, avec des touches sous forme de chaînes et toutes les permutations possibles sous forme de valeurs. Toutes les longueurs de cordes possibles sont inclus, donc en effet, vous créez un surensemble.

Si vous avez besoin que les permutations finales, vous pouvez supprimer d'autres clés du dictionnaire.

Dans ce code, le dictionnaire de permutations est globale.

Dans le cas de base, je stocke la valeur que les deux possibilités dans une liste. perms['ab'] = ['ab','ba'].

Pour des longueurs de chaîne supérieures, la fonction se réfère à abaisser la longueur de chaîne et intègre les permutations calculées précédemment.

La fonction fait deux choses:

  • appelle lui-même avec une chaîne plus petite
  • renvoie une liste des permutations d'une chaîne particulière si elle est déjà disponible. En cas de retour à lui-même, ceux-ci seront utilisés pour ajouter au caractère et à créer des permutations plus récentes.

Cher pour la mémoire.

perms = {}
def perm(input_string):
    global perms
    if input_string in perms:
        return perms[input_string] # This will send a list of all permutations
    elif len(input_string) == 2:
        perms[input_string] = [input_string, input_string[-1] + input_string [-2]]
        return perms[input_string]
    else:
        perms[input_string] = []
        for index in range(0, len(input_string)):
            new_string = input_string[0:index] + input_string[index +1:]
            perm(new_string)
            for entries in perms[new_string]:
                perms[input_string].append(input_string[index] + entries)
    return perms[input_string]
Créé 05/07/2013 à 05:15
source utilisateur

voix
0

Il y a une implémentation de Java itérative 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 complet

Créé 07/05/2013 à 02:18
source utilisateur

voix
0

c # itérative:

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;
    }
Créé 26/07/2012 à 16:20
source utilisateur

voix
0

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

En fait, le nombre de combinaisons est le (nombre de mots) à la puissance (nombre de lettres par mot). Ainsi, choisir un nombre aléatoire entre 0 et le nombre de combinaisons - 1, convertir ce nombre à la base (nombre de mots), puis utilisez chaque chiffre de ce numéro comme indicateur pour lequel mot prendre la prochaine lettre.

par exemple: dans l'exemple ci-dessus. 3 mots, 6 lettres = 729 combinaisons. Choisissez un nombre aléatoire: 465. Convertir en base 3: 122020. Prenez la première lettre du mot 1, 2 du mot 2, 3 du mot 2, 4 de mot 0 ... et vous obtenez ... « joofle ».

Si vous voulez toutes les permutations, boucle juste de 0 à 728. Bien sûr, si vous êtes juste de choisir une valeur aléatoire, beaucoup plus simple façon moins déroutant serait de boucler sur les lettres. Cette méthode permet d' éviter récursion, si vous voulez que toutes les permutations, plus il vous fait ressembler vous savez Maths (tm) !

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

Créé 16/09/2008 à 06:33
source utilisateur

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more