Genera un elenco di tutte le possibili permutazioni di una stringa

Question

Come potrei generare un elenco di tutte le possibili permutazioni di una stringa tra i caratteri xey di lunghezza, contenente un elenco variabile di caratteri.

Qualsiasi linguaggio funzionerebbe, ma dovrebbe essere portabile.

Answer 1

Esistono diversi modi per farlo.I metodi comuni utilizzano la ricorsione, la memorizzazione o la programmazione dinamica.L'idea di base è produrre un elenco di tutte le stringhe di lunghezza 1, quindi in ciascuna iterazione, per tutte le stringhe prodotte nell'ultima iterazione, aggiungere quella stringa concatenata individualmente con ciascun carattere nella stringa.(l'indice variabile nel codice seguente tiene traccia dell'inizio dell'ultima e della successiva iterazione)

Alcuni pseudocodici:

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)

dovresti quindi rimuovere tutte le stringhe di lunghezza inferiore a x, saranno le prime (x-1) * len(originalString) voci nell'elenco.

Answer 2

È meglio usare il 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;
}

Answer 3

Avrai un sacco di corde, questo è sicuro...

\sum_{i=x}^y{\frac{r!}{{(r-i)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20%7B%20%5Cfrac%7Br!%7D%7B%7B(r-i)%7D!%7D%20%7D
Dove xey è il modo in cui li definisci e r è il numero di caratteri da cui selezioniamo, se ho capito bene.Dovresti assolutamente generarli secondo necessità e non essere sciatto e dire, generare un powerset e quindi filtrare la lunghezza delle stringhe.

Quello che segue non è sicuramente il modo migliore per generarli, ma è comunque un aspetto interessante.

Knuth (volume 4, fascicolo 2, 7.2.1.3) ci dice che la combinazione (s,t) è equivalente a s+1 cose prese t alla volta con ripetizione -- una combinazione (s,t) è la notazione usata da Knuth è uguale a {t \scegli {s+t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D.Possiamo capirlo generando prima ciascuna combinazione (s,t) in forma binaria (quindi, di lunghezza (s+t)) e contando il numero di 0 a sinistra di ciascun 1.

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

Answer 4

Soluzione non ricorsiva secondo Knuth, esempio 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)

Answer 5

Potresti guardare "Enumerazione efficiente dei sottoinsiemi di un insieme", che descrive un algoritmo per fare parte di ciò che desideri: generare rapidamente tutti i sottoinsiemi di N caratteri dalla lunghezza x a y.Contiene un'implementazione in C.

Per ogni sottoinsieme, dovresti comunque generare tutte le permutazioni.Ad esempio, se volessi 3 caratteri da "abcde", questo algoritmo ti darà "abc", "abd", "abe"...ma dovresti permutarli tutti per ottenere "acb", "bac", "bca", ecc.

Answer 6

Alcuni codici Java funzionanti basati su La risposta di 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);
    }
}

Answer 7

Ecco una soluzione semplice in C#.

Genera solo le permutazioni distinte di una determinata 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;
        }
    }

Answer 8

Ci sono molte buone risposte qui.Suggerisco anche una soluzione ricorsiva molto semplice 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:le stringhe con caratteri ripetuti non produrranno permutazioni univoche.

Answer 9

L'ho appena preparato velocemente 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

Potresti esaminare l'API del linguaggio per funzioni di tipo permutazione integrate e potresti essere in grado di scrivere codice più ottimizzato, ma se i numeri sono così alti, non sono sicuro che ci sia molto modo per ottenere molti risultati .

Ad ogni modo, l'idea alla base del codice è iniziare con una stringa di lunghezza 0, quindi tenere traccia di tutte le stringhe di lunghezza Z dove Z è la dimensione corrente nell'iterazione.Quindi, esamina ciascuna stringa e aggiungi ciascun carattere su ciascuna stringa.Alla fine, rimuovi tutti quelli che erano al di sotto della soglia x e restituisci il risultato.

Non l'ho testato con input potenzialmente privi di significato (elenco di caratteri nulli, valori strani di xey, ecc.).

Answer 10

Questa è una traduzione della versione Ruby di Mike, 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 un'altra versione, leggermente più corta e che utilizza più funzionalità di loop:

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

Answer 11

Ecco una semplice soluzione ricorsiva in C# con parole:

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

Chiamando:

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

Answer 12

In Perl, se vuoi limitarti all'alfabeto minuscolo, puoi farlo:

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

Ciò fornisce tutte le possibili stringhe comprese tra 1 e 4 caratteri utilizzando caratteri minuscoli.Per le maiuscole, cambia "a" A "A" E "zzzz" A "ZZZZ".

Per il caso misto diventa molto più difficile e probabilmente non fattibile con uno degli operatori integrati di Perl come quello.

Answer 13

...ed ecco 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;
}

Answer 14

permuta (ABC) -> A.perm(BC) -> A.perm[B.perm(C)] -> A.perm[(*BC), (CB*)] -> [(*UNa.C.), (BUNC), (a.CUN*), (*UNC.B.), (CUNB), (CBUN*)] Per rimuovere i duplicati quando si inserisce ogni alfabeto, verificare se la stringa precedente termina 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;
}

Stampa tutte le permutazioni senza duplicati

Answer 15

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

Answer 16

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

Answer 17

La seguente ricorsione Java stampa tutte le permutazioni di una determinata 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);
    }
}

Di seguito è riportata la versione aggiornata del metodo "permut" di cui sopra che rende n!(n fattoriale) chiamate meno ricorsive rispetto al metodo precedente

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

Answer 18

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

Answer 19

Ecco una versione non ricorsiva che ho creato, in javascript.Non è basato su quello non ricorsivo di Knuth sopra, sebbene abbia alcune somiglianze nello scambio di elementi.Ho verificato la sua correttezza per array di input fino a 8 elementi.

Una rapida ottimizzazione sarebbe il pre-flight del file out schieramento ed evitando push().

L'idea di base è:

1. Dato un singolo array di origine, generare un primo nuovo set di array che scambiano a turno il primo elemento con ogni elemento successivo, lasciando ogni volta imperturbabili gli altri elementi.per esempio:dato 1234, genera 1234, 2134, 3214, 4231.

2. Usa ogni array dal passaggio precedente come seme per un nuovo passaggio, ma invece di scambiare il primo elemento, scambiare il secondo elemento con ciascun elemento successivo.Inoltre, questa volta, non includere l'array originale nell'output.

3. Ripetere il passaggio 2 fino al termine.

Ecco l'esempio di codice:

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

Answer 20

Non sono sicuro del motivo per cui vorresti farlo in primo luogo.L'insieme risultante per qualsiasi valore moderatamente grande di x e y sarà enorme e crescerà esponenzialmente man mano che x e/o y diventano più grandi.

Supponiamo che il tuo insieme di caratteri possibili sia costituito dalle 26 lettere minuscole dell'alfabeto e chiedi alla tua applicazione di generare tutte le permutazioni in cui lunghezza = 5.Supponendo che non esaurisci la memoria, otterrai 11.881.376 (ovvero26 alla potenza di 5) corde indietro.Aumenta la lunghezza fino a 6 e otterrai indietro 308.915.776 stringhe.Questi numeri diventano dolorosamente grandi, molto rapidamente.

Ecco una soluzione che ho messo insieme in Java.Dovrai fornire due argomenti di runtime (corrispondenti a xey).Divertiti.

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

Answer 21

Ne avevo bisogno oggi e, sebbene le risposte già fornite mi indicassero la giusta direzione, non erano esattamente ciò che volevo.

Ecco un'implementazione che utilizza il metodo Heap.La lunghezza dell'array deve essere almeno 3 e per considerazioni pratiche non essere maggiore di 10 circa, a seconda di cosa si vuole fare, pazienza e velocità di clock.

Prima di entrare nel ciclo, inizializza 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 restituirà false una volta terminato.

*VB lo farà per te.

** Puoi modificare leggermente NextPerm per renderlo non necessario, ma è più chiaro in questo modo.

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 ne descrive due, uno dà l'ordine lessicale, ma è complesso e lento, l'altro è noto come metodo dei cambiamenti semplici.Anche Jie Gao e Dianjun Wang hanno scritto un articolo interessante.

Answer 22

Nel rubino:

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

È abbastanza veloce, ma ci vorrà del tempo =).Naturalmente puoi iniziare da "aaaaaaaa" se le stringhe brevi non ti interessano.

Potrei però aver interpretato male la domanda vera e propria: in uno dei post sembrava che avessi solo bisogno di una libreria di stringhe a forza bruta, ma nella domanda principale sembra che tu debba permutare una particolare stringa.

Il tuo problema è in qualche modo simile a questo: http://beust.com/weblog/archives/000491.html (elenca tutti i numeri interi in cui nessuna cifra si ripete, il che ha portato molti linguaggi a risolverlo, con il ragazzo ocaml che usa permutazioni e qualche ragazzo Java che usa ancora un'altra soluzione).

Answer 23

Questo codice in Python, quando chiamato con allowed_characters impostato [0,1] e un massimo di 4 caratteri, 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 ti sia utile.Funziona con qualsiasi carattere, non solo con i numeri

Answer 24

Ecco un collegamento che descrive come stampare le permutazioni di una stringa.http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

Answer 25

Sebbene questo non risponda esattamente alla tua domanda, ecco un modo per generare ogni permutazione delle lettere da un numero di stringhe della stessa lunghezza:ad esempio, se le tue parole fossero "coffee", "joomla" e "moodle", puoi aspettarti risultati come "coodle", "joodee", "joffle", ecc.

Fondamentalmente, il numero di combinazioni è (numero di parole) elevato a (numero di lettere per parola).Quindi, scegli un numero casuale compreso tra 0 e il numero di combinazioni - 1, converti quel numero in base (numero di parole), quindi usa ciascuna cifra di quel numero come indicatore di quale parola prendere la lettera successiva.

per esempio:nell'esempio sopra.3 parole, 6 lettere = 729 combinazioni.Scegli un numero casuale:465.Convertire in base 3:122020.Prendi la prima lettera dalla parola 1, la seconda dalla parola 2, la terza dalla parola 2, la quarta dalla parola 0...e ottieni..."joofle".

Se desideri tutte le permutazioni, esegui semplicemente il ciclo da 0 a 728.Naturalmente, se scegli solo un valore casuale, molto più semplice un modo meno confuso sarebbe quello di ripetere le lettere.Questo metodo ti consente di evitare la ricorsione, se desideri tutte le permutazioni, inoltre ti fa sembrare che tu conosca la matematica^(tm)!

Se il numero di combinazioni è eccessivo, puoi suddividerlo in una serie di parole più piccole e concatenarle alla fine.

Answer 26

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

Answer 27

Esiste un'implementazione Java iterativa in NoncomuniMatematica (funziona per un elenco di oggetti):

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

Fonte completa

Answer 28

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

Answer 29

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

Ecco la mia opinione su una versione non ricorsiva

Answer 30

La soluzione pitonica:

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