Gere uma lista de todas as permutações possíveis de uma string

Como eu geraria uma lista de todas as permutações possíveis de uma string com caracteres x e y de comprimento, contendo uma lista variável de caracteres.

Qualquer idioma funcionaria, mas deveria ser portátil.

Existem várias maneiras de fazer isso. Métodos comuns usam recursão, memorização ou programação dinâmica. A idéia básica é que você produza uma lista de todas as cadeias de comprimento 1 e, em cada iteração, para todas as cadeias produzidas na última iteração, adicione essa cadeia concatenada com cada caractere na cadeia individualmente. (o índice da variável no código abaixo controla o início da última e da próxima iteração)

Algum pseudocódigo:

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)

você precisará remover todas as strings com menos de x de comprimento, elas serão as primeiras (x-1) * len (originalString) da lista.

É melhor usar o retorno

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

Você vai ter muitas cordas, com certeza ...

Onde x e y são como você os define e r é o número de caracteres que estamos selecionando - se estou entendendo corretamente. Você definitivamente deve gerá-las conforme necessário e não ficar desleixado e dizer, gerar um conjunto de energia e depois filtrar o comprimento das seqüências.

Definitivamente, a seguir não é a melhor maneira de gerá-las, mas é um aparte interessante, no entanto.

Knuth (volume 4, fascículo 2, 7.2.1.3) nos diz que a combinação (s, t) é equivalente a s + 1 coisas tomadas t por vez com repetição - uma combinação (s, t) é a notação usada por Knuth que é igual a . Podemos descobrir isso gerando primeiro cada combinação (s, t) em forma binária (portanto, de comprimento (s + t)) e contando o número de 0 à esquerda de cada 1.

10001000011101 -> torna-se a permutação: {0, 3, 4, 4, 4, 1}

Solução não recursiva de acordo com Knuth, exemplo em 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)

Você pode consultar " Enumerando eficientemente os subconjuntos de um conjunto ", que descreve um algoritmo para fazer parte do que você deseja - gere rapidamente todos os subconjuntos de caracteres N do comprimento x até y. Ele contém uma implementação em C.

Para cada subconjunto, você ainda precisará gerar todas as permutações. Por exemplo, se você quiser três caracteres de "abcde", esse algoritmo fornecerá "abc", "abd", "abe" ... mas você precisará permutar cada um para obter "acb", "bac", "bca" etc.

Alguns códigos Java funcionais baseados na resposta 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);
    }
}

Aqui está uma solução simples em C #.

Ele gera apenas as permutações distintas de uma determinada string.

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

Há muitas boas respostas aqui. Sugiro também uma solução recursiva muito simples em 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 : strings com caracteres repetidos não produzirão permutações exclusivas.

Acabei de preparar isso rapidamente no 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

Você pode procurar na API da linguagem funções do tipo permutação incorporadas e conseguir escrever um código mais otimizado, mas se os números forem altos demais, não tenho certeza de que haja muitos meios de obter muitos resultados .

De qualquer forma, a idéia por trás do código é iniciada com a sequência de comprimento 0 e, em seguida, acompanhe todas as sequências de comprimento Z, em que Z é o tamanho atual da iteração. Em seguida, passe por cada sequência e acrescente cada caractere a cada sequência. Finalmente, no final, remova qualquer um que estivesse abaixo do limite x e retorne o resultado.

Não testei com entrada potencialmente sem sentido (lista de caracteres nulos, valores estranhos de x e y, etc.).

Esta é uma tradução da versão Ruby de Mike, para o 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 outra versão, um pouco mais curta e com mais recursos de 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)))))

Aqui está uma solução recursiva simples da palavra C #:

Método:

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

A ligar:

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

... e aqui está a versão 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;
}

permuto (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 * )] Para remover duplicatas ao inserir cada alfabeto, verifique se a sequência anterior termina com o mesmo alfabeto (por que? -exercício)

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 todas as permutações sem duplicatas

Solução recursiva em 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;
            }
        }
}

No Perl, se você quiser se restringir ao alfabeto em minúsculas, faça o seguinte:

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

Isso fornece todas as seqüências possíveis entre 1 e 4 caracteres usando caracteres minúsculos. Para maiúsculas, altere "a"para "A"e "zzzz"para "ZZZZ".

Para casos mistos, fica muito mais difícil e provavelmente não é possível com um dos operadores internos do Perl assim.

Resposta em Ruby que funciona:

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

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

A seguinte recursão Java imprime todas as permutações de uma determinada sequência:

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

A seguir está a versão atualizada do método "permut" acima, que torna n! (n fatorial) chamadas menos recursivas em comparação com o método acima

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

Não sei por que você desejaria fazer isso em primeiro lugar. O conjunto resultante para quaisquer valores moderadamente grandes de x e y será enorme e aumentará exponencialmente à medida que x e / ou y ficarem maiores.

Digamos que seu conjunto de caracteres possíveis seja as 26 letras minúsculas do alfabeto, e você solicita que seu aplicativo gere todas as permutações em que length = 5. Supondo que você não fique sem memória, obterá 11.881.376 (ou seja, 26 ao poder de 5) cordas de volta. Aumente esse comprimento até 6 e você receberá 308.915.776 strings de volta. Esses números aumentam dolorosamente, muito rapidamente.

Aqui está uma solução que montei em Java. Você precisará fornecer dois argumentos de tempo de execução (correspondentes a x e y). Diverta-se.

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

Aqui está uma versão não recursiva que eu criei, em javascript. Não é baseado no não recursivo de Knuth acima, embora tenha algumas semelhanças na troca de elementos. Eu verifiquei sua correção para matrizes de entrada de até 8 elementos.

Uma otimização rápida seria pré-veicular a outmatriz e evitar push().

A ideia básica é:

1. Dada uma única matriz de origem, gere um primeiro novo conjunto de matrizes que troquem o primeiro elemento com cada elemento subsequente, deixando sempre os outros elementos imperturbáveis. por exemplo: dado 1234, gere 1234, 2134, 3214, 4231.

2. Use cada matriz da passagem anterior como a semente de uma nova passagem, mas em vez de trocar o primeiro elemento, troque o segundo elemento por cada elemento subsequente. Além disso, desta vez, não inclua a matriz original na saída.

3. Repita a etapa 2 até concluir.

Aqui está o exemplo de código:

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

Em rubi:

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

É bem rápido, mas vai demorar algum tempo =). Claro, você pode começar em "aaaaaaaa" se as seqüências curtas não forem interessantes para você.

Talvez eu tenha interpretado mal a pergunta real - em uma das postagens, parecia que você só precisava de uma biblioteca de strings da força bruta, mas na pergunta principal parece que você precisa permutar uma determinada string.

Seu problema é um pouco semelhante a este: http://beust.com/weblog/archives/000491.html (liste todos os números inteiros nos quais nenhum dos dígitos se repete, o que resultou em vários idiomas resolvendo-o, com o cara do ocaml usando permutações e cara do java usando outra solução).

Eu precisava disso hoje e, embora as respostas já dadas me apontassem na direção certa, elas não eram exatamente o que eu queria.

Aqui está uma implementação usando o método Heap. O comprimento da matriz deve ser pelo menos 3 e, por considerações práticas, não deve ser maior que 10 ou mais, dependendo do que você deseja fazer, paciência e velocidade do relógio.

Antes de inserir seu loop, inicialize Perm(1 To N)com a primeira permutação, Stack(3 To N)com zeros * e Levelcom 2**. No final da chamada de loop NextPerm, que retornará falso quando terminarmos.

* VB fará isso por você.

** Você pode alterar um pouco o NextPerm para tornar isso desnecessário, mas fica mais claro assim.

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

Outros métodos são descritos por vários autores. Knuth descreve dois, um dá ordem lexical, mas é complexo e lento, o outro é conhecido como o método de mudanças simples. Jie Gao e Dianjun Wang também escreveram um artigo interessante.

Esse código em python, quando chamado com allowed_charactersdefinido como [0,1]e no máximo 4 caracteres, geraria 2 ^ 4 resultados:

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

Espero que isso seja útil para você. Funciona com qualquer caractere, não apenas números

Aqui está um link que descreve como imprimir permutações de uma string. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

Embora isso não responda exatamente à sua pergunta, aqui está uma maneira de gerar todas as permutações de letras de várias seqüências do mesmo comprimento: por exemplo, se suas palavras forem "café", "joomla" e "moodle", você pode esperar resultados como "coodle", "joodee", "joffle" etc.

Basicamente, o número de combinações é o (número de palavras) à potência de (número de letras por palavra). Portanto, escolha um número aleatório entre 0 e o número de combinações - 1, converta esse número em base (número de palavras) e use cada dígito desse número como indicador para qual palavra extrair a próxima letra.

por exemplo: no exemplo acima. 3 palavras, 6 letras = 729 combinações. Escolha um número aleatório: 465. Converta para a base 3: 122020. Pegue a primeira letra da palavra 1, 2ª da palavra 2, 3ª da palavra 2, 4ª da palavra 0 ... e você obterá "joofle".

Se você quiser todas as permutações, faça um loop de 0 a 728. Claro, se você estiver escolhendo apenas um valor aleatório, uma maneira muito mais simples e menos confusa seria fazer um loop sobre as letras. Este método permite evitar recursões, caso você queira todas as permutações, além de fazer com que pareça que você conhece Maths ^(tm) !

Se o número de combinações for excessivo, você poderá dividi-lo em uma série de palavras menores e concatená-las no final.

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

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

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

Aqui está a minha opinião sobre uma versão não recursiva

A solução pitônica:

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

Bem, aqui está uma solução O (n!) Elegante e não recursiva:

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