Generare un elenco di tutte le possibili permutazioni di una stringa

Come posso fare per generare un elenco di tutte le possibili permutazioni di una stringa tra x e y caratteri, contenente un elenco variabile di caratteri.

Qualsiasi lingua avrebbe funzionato, ma dovrebbe essere portatile.

 

34 Replies
  1. 70

    Ci sono diversi modi per fare questo. Metodi comuni di utilizzare la ricorsione, memoization, o di programmazione dinamica. L’idea di base è che si produce un elenco di tutte le stringhe di lunghezza 1, quindi in ogni iterazione, per tutte le stringhe prodotte nell’ultima iterazione, aggiungere la stringa concatenata con ogni carattere della stringa singolarmente. (l’indice della variabile nel codice riportato di seguito tiene traccia di inizio dell’ultima e la prossima iterazione)

    Alcuni pseudocodice:

    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)
    

    sarebbe quindi necessario rimuovere tutte le stringhe meno di x di lunghezza, che sarà il primo (x-1) * len(originalString) voci dell’elenco.

    • Perché primo negozio elenco di elementi, e quindi cancellarlo? (in riferimento alla linea 1 e 3, in pseudocodice).
    • Che cosa è y (linea 4) ?
    • Dalla domanda: “tutte le possibili permutazioni di una stringa tra x e y caratteri in lunghezza”
  2. 39

    È meglio utilizzare backtracking

    #include <stdio.h>
    #include <string.h>
    
    void swap(char *a, char *b) {
        char temp;
        temp = *a;
        *a = *b;
        *b = temp;
    }
    
    void print(char *a, int i, int n) {
        int j;
        if(i == n) {
            printf("%s\n", a);
        } else {
            for(j = i; j <= n; j++) {
                swap(a + i, a + j);
                print(a, i + 1, n);
                swap(a + i, a + j);
            }
        }
    }
    
    int main(void) {
        char a[100];
        gets(a);
        print(a, 0, strlen(a) - 1);
        return 0;
    }
    • Soluzione migliore everrrrrrrrr
    • È molto leggibile e facile da afferrare solo su un aspetto.
  3. 25

    Si sta per ottenere un sacco di stringhe, questo è sicuro…

    Generare un elenco di tutte le possibili permutazioni di una stringa

    Dove x e y è come si definiscono loro, e r è il numero di caratteri stiamo selezionando dalla-se io sono la comprensione è corretta. Sicuramente, si dovrebbe generare questi necessari e non ottenere sciatta e dire, generare un powerset e poi filtrare la lunghezza delle stringhe.

    Seguenti sicuramente non è il modo migliore per generare questi, ma è un interessante a parte, nessuno-la-meno.

    Knuth (volume 4, fascicolo 2, 7.2.1.3) ci dice che (s,t)-combinazione è equivalente a s+1 cose prese t alla volta e con ripetizione, un (s,t)-combinazione di notazione usata da Knuth che è uguale a Generare un elenco di tutte le possibili permutazioni di una stringa. Siamo in grado di capire questo fuori prima generazione di ogni (s,t)-combinazione in forma binaria (così, di lunghezza (s+t)) e contando il numero di 0 a sinistra di ogni 1.

    10001000011101 –> diventa la permutazione: {0, 3, 4, 4, 4, 1}

  4. 15

    Non soluzione ricorsiva secondo Knuth, Python esempio:

    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)
    
    • In realtà, questo significa non quando stringa non è ordinato. Se si tenta con "54321" solo UNA string è mostrato (di per sé).
    • La cosa interessante è che nextPermutation() è stateless – ci vuole solo l’ingresso al permutate e gli indici non sono mantenuti da iterazione per iterazione. È in grado di farlo dal presupposto che l’input iniziale è stato risolto e la ricerca di indici (k0 e l0) di per sé, in base a dove l’ordine è mantenuto. Ordinamento di un ingresso come “54321” -> “12345” consentirebbe di questo algoritmo per trovare tutte le attese permutazioni. Ma dal momento che si fa una buona quantità di lavoro extra per ri-trovare tali indici per ogni permutazione si genera, sono i modi più efficaci per farlo in modo non ricorsivo.
  5. 13

    Si potrebbe guardare “In modo efficiente l’Enumerazione dei Sottoinsiemi di un Insieme“, che descrive un algoritmo per fare la parte di quello che vuoi – generare rapidamente tutti i sottoinsiemi di N caratteri di lunghezza x a y. Esso contiene un’implementazione in C.

    Per ogni sottoinsieme, avresti ancora generare tutte le permutazioni. Per esempio, se si voleva 3 personaggi da “abcde”, questo algoritmo dare “abc”,”abd”, “abe”…
    ma dovresti permute ciascuna di esse per ottenere “acb”, “bac”, “bca”, etc.

  6. 13

    Di lavoro codice Java basato su Sarp risposta:

    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);
        }
    }
    
    • Come commento, nota che per una stringa con caratteri ripetuti questo non produrrà l’unico permutazioni. Questo potrebbe essere risolto con un hash, ma che potrebbe essere un problema con le stringhe.
    • Si potrebbe desiderare di utilizzare char array invece di stringhe per fare questo correre più veloce dato che le stringhe sono immutabili in java.
  7. 13

    Qui è una soluzione semplice in C#.

    Genera solo distinti permutazioni di una data stringa.

        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;
            }
        }
    
  8. 12

    Ci sono un sacco di buone risposte qui. Suggerisco anche una semplice soluzione ricorsiva in 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;
        });
    }
    

    Nota: stringhe di caratteri ripetuti non produrrà unico permutazioni.

    • Questa soluzione è ottima e merita più attenzione.
  9. 9

    Ho appena montata questa rapida in 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
    

    Si potrebbe guardare in lingua API per la costruzione di permutazione tipo di funzioni, e si potrebbe essere in grado di scrivere codice più ottimizzato, ma se i numeri sono alti, non sono sicuro che c’è molto di un modo di avere un sacco di risultati.

    Comunque, l’idea dietro il codice inizia con la stringa di lunghezza 0, quindi tenere traccia di tutte le stringhe di lunghezza Z, dove Z è la dimensione corrente nella iterazione. Quindi, passare attraverso ogni stringa e aggiungere ogni personaggio su ogni stringa. Infine, al termine, rimuovere quelli che erano sotto la x di soglia e restituire il risultato.

    Io non l’ho provato con potenzialmente senso di input (null elenco dei personaggi, strani valori di x e y, ecc).

    • Questo codice è ERRATO. Si genererà voci di permutazioni, come quelle con caratteri ripetuti. Per esempio, per la stringa “abc”, la generazione di queste permutazioni di dimensione 3: [“aaa”, “aab”, “aac”, “aba”, “abb”, “abc”, “aca”, “acb”, “acc”, “baa”, “bab”, “bac”, “bba”, “bbb”, “bbc”, “bca”, “bcb”, “ccn”, “caa”, “cab”, “cac”, “cba”, “cbb”, “cbc”, “cca”, “ccb”, “ccc”]. Questo non è corretto.
  10. 8

    Questa è una traduzione di Mike versione di Ruby, in 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)))))
    

    E in un’altra versione, leggermente più corta ed utilizzando più loop struttura dispone di:

    (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)))))
    
  11. 8

    Qui è una semplice parola C# soluzione ricorsiva:

    Metodo:

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

    Chiamata:

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

    … e qui è la versione 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;
    }
    
  13. 8

    permute (ABC) -> A. perm(BC) -> A. perm[B. perm(C)] -> A. perm[(*BC), (CB*)] -> [(*UNBC), (BUNC), (BCUN*), (*UNCB), (CUNB), (CBUN*)]
    Per rimuovere i duplicati durante l’inserimento di ogni alfabeto controllare per vedere se la stringa precedente finisce con lo stesso alfabeto (perché? -esercizio)

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

    Stampe di tutte le permutazioni sans duplicati

  14. 8

    Soluzione ricorsiva in 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;
                }
            }
    }
    
    • Centel: questo lavoro di codice in C++? <string>
  15. 7

    In Perl, se si desidera limitare voi per le lettere minuscole dell’alfabeto, si può fare questo:

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

    Questo dà tutte le possibili stringhe tra 1 e 4 personaggi con caratteri minuscoli. Per le lettere maiuscole, cambiare "a" per "A" e "zzzz" per "ZZZZ".

    Misto-caso diventa molto più difficile, e probabilmente non è fattibile con uno di Perl incorporato operatori di simile.

  16. 7

    Ruby risposta che funziona:

    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")
    
  17. 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;
        }
    }
    
  18. 6

    Seguenti Java ricorsione stampe di tutte le permutazioni di una data stringa:

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

    Che segue è la versione aggiornata di sopra “permut” metodo che rende n! (n fattoriale) meno chiamate ricorsive rispetto al metodo di cui sopra

    //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()));
       }
    }
    
    • Questa è la soluzione più pulita, e credo di aver visto prima nel libro “Cracking la Codifica Intervista”
    • grazie per il complemento, l’ho fatto, di non copiare da qualsiasi luogo, tuttavia, è possibile che qualcuno abbia creato simile algo. Comunque ho aggiornato il codice di cui sopra per meno di chiamate ricorsive
  19. 5

    Non so perché si vuole fare questo, in primo luogo. Set risultante per qualsiasi moderatamente grandi valori di x e y sarà enorme, e che continuerà a crescere in modo esponenziale con x e/o y ottenere più grande.

    Permette di dire che il set di caratteri possibili è il 26 lettere minuscole dell’alfabeto, e si chiede l’applicazione per generare tutte le permutazioni cui lunghezza = 5. Supponendo che tu non a corto di memoria si otterrà 11,881,376 (cioè 26 alla potenza di 5) stringhe. Bump che la lunghezza fino a 6 persone, e si otterrà 308,915,776 stringhe. Questi i numeri di ottenere dolorosamente grande, molto rapidamente.

    Ecco la soluzione che ho messo insieme in Java. Avrete bisogno di fornire due runtime argomenti (corrispondente a x e y). Divertirsi.

    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);
                }
            }
        }
    }
    
    • Lungo tempo, ma non è la generazione di loro con ripetizione?
  20. 5

    Qui si tratta di un non-versione ricorsiva mi è venuta, in javascript.
    Non è basata su un Knuth non ricorsiva quella di cui sopra, anche se ha alcune somiglianze in elemento di scambio.
    Ho verificato la correttezza dei dati di input array di 8 elementi.

    Una rapida ottimizzazione sarebbe pre-flight, il out array ed evitando push().

    L’idea di base è:

    1. Una singola matrice di origine, generare un primo set di array di swap il primo elemento con ogni elemento successivo a sua volta, ogni volta lasciando gli altri elementi imperturbabile.
      ad esempio: dato 1234, generare 1234, 2134, 3214, 4231.

    2. Utilizzare ogni matrice del passo precedente, come il seme per una nuova pass,
      ma invece di scambiare il primo elemento, sostituire il secondo elemento con ogni elemento successivo. Inoltre, questa volta, non sono la matrice originale in uscita.

    3. Ripetere il passaggio 2 fino a quando fatto.

    Ecco il codice di esempio:

    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;
    }
    
  21. 3

    In ruby:

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

    È abbastanza veloce, ma sta andando a prendere un po di tempo =). Naturalmente, si può iniziare a “aaaaaaaa” se le stringhe non sono interessanti per voi.

    Potrei aver male interpretato la domanda vera e propria, anche se – in uno dei post che sembrava come se avete solo bisogno di un bruteforce biblioteca di stringhe, ma la domanda principale che suona come avete bisogno di permutate una particolare stringa.

    Il tuo problema è un po ‘ simile a questo: http://beust.com/weblog/archives/000491.html (elenco di tutti i numeri interi in cui nessuna delle cifre che si ripetono, che ha portato in un sacco di lingue, a risolverlo con il ocaml ragazzo con permutazioni, e alcune java ragazzo con ancora un’altra soluzione).

    • Un problema con la vostra proposta è che str.avanti! non scorrere tutti i caratteri stampabili. Il tuo esempio sarà solo generare le lettere minuscole – no segni di punteggiatura e maiuscole.
  22. 3

    Ho bisogno di questo, oggi, e anche se le risposte già dato mi ha indicato la direzione giusta, non era proprio quello che volevo.

    Ecco un’implementazione tramite Heap del metodo. La lunghezza dell’array deve essere almeno 3 e per considerazioni pratiche non essere più grande di 10 o giù di lì, a seconda di cosa si vuole fare, la pazienza e la velocità di clock.

    Prima dell’immissione del ciclo, si deve inizializzare Perm(1 To N) con la prima permutazione, Stack(3 To N) con zeri*, e Level con 2**. Alla fine del ciclo di chiamata NextPerm, che restituisce false quando abbiamo finito.

    * VB farà per voi.

    ** È possibile cambiare NextPerm un po ‘ per fare questo inutile, ma è chiaro come questo.

    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

    Altri metodi sono descritti da vari autori. Knuth descrive due, uno dà ordine lessicale, ma è lento e complesso, l’altro è noto come il metodo di pianura modifiche. Jie Gao e Dianjun Wang ha anche scritto un articolo interessante.

  23. 2

    Questo codice in python, se chiamato con allowed_characters set di [0,1] e 4 caratteri max, genererebbe 2^4 risultati:

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

    Spero che questo sia utile a voi. Funziona con qualsiasi personaggio, non solo numeri

    • Questo non è permutazioni ma sottoinsieme di selezione, ovvero ABC & 001 = C, mentre una valida permutazione deve avere tutti e tre i caratteri.
    • uh? scusa non capisco cosa dici. Se è risolvere il problema di lasciare una versione fissa, io wiki la cosa
  24. 0

    Anche se questo non risponde alla tua domanda esattamente, ecco un modo per generare ogni permutazione delle lettere da una serie di stringhe della stessa lunghezza: ad esempio, se le tue parole sono state “caffè”, “joomla” e “moodle”, ci si può aspettare di output come “coodle”, “joodee”, “joffle”, etc.

    Fondamentalmente, il numero di combinazioni è (numero di parole) il potere di (numero di lettere di ogni parola). Quindi, scegliere un numero casuale tra 0 e il numero di combinazioni – 1, convertire il numero di base (numero di parole), quindi utilizzare tutte le cifre di quel numero come indicatore per il quale parola per prendere la prossima lettera.

    ad esempio: nell’esempio di cui sopra. 3 parole di 6 lettere = 729 combinazioni. Scegliere un numero casuale: 465. La conversione di base 3: 122020. Prendere la prima lettera da word 1, 2 ° da word 2, 3 da word 2, 4 da word 0… e ottenere… “joofle”.

    Se si voleva tutte le permutazioni, solo il ciclo for da 0 a 728. Naturalmente, se hai solo la scelta di un valore casuale, molto semplice meno confusione avrebbe loop sopra le lettere. Questo metodo consente di evitare la ricorsione, dovrebbe si desidera che tutte le permutazioni, e in più ti fa apparire come si sa la Matematica(tm)!

    Se il numero di combinazioni è eccessivo, si possono rompere in una serie di piccole parole e concatenare alla fine.

  25. 0

    c# iterativo:

    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;
        }
    
  26. 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
    
  27. 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
    

    Qui è il mio prendere su un non versione ricorsiva

  28. 0

    Il divinatori soluzione:

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

    Beh, qui è un elegante, non ricorsiva, O(n!) soluzione:

    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;
        }
    
  30. 0

    Soluzione ricorsiva con driver main() metodo.

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

    }

  31. 0

    Una soluzione ricorsiva in python. La cosa buona di questo codice è che le esportazioni di un dizionario, con le chiavi come stringhe e tutte le permutazioni possibili valori. Tutte le possibili lunghezze di stringa sono inclusi, quindi, in effetti, la creazione di un superset.

    Se avete bisogno solo del finale di permutazioni, è possibile eliminare le altre chiavi del dizionario.

    In questo codice, il dizionario di permutazioni è globale.

    Al caso base, memorizzare il valore di entrambe le possibilità in un elenco. perms['ab'] = ['ab','ba'].

    Per una maggiore lunghezza di stringa, la funzione si riferisce ad abbassare le lunghezze di stringa e incorpora precedentemente calcolato permutazioni.

    La funzione fa due cose:

    • chiama se stessa con una piccola stringa di
    • restituisce un elenco di tutte le permutazioni di una particolare stringa, se già disponibili. Se restituito a se stesso, questi saranno utilizzati per aggiungere il carattere e creare nuovi permutazioni.

    Costoso per la memoria.

    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]
    
  32. 0

    codice scritto per il linguaggio java :

    pacchetto namo.algoritmi;

    import java.util.Scanner;

    public class Permuations {

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

    }

  33. 0

    Le possibili permutazioni di stringhe può essere calcolata utilizzando funzione ricorsiva. Qui di seguito è una delle possibili soluzione.

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

Lascia un commento