lista de todas as permutações possíveis de uma seqüência de gerar

votos
143

Como eu iria sobre como gerar uma lista de todas as permutações possíveis de uma corda entre x e y caracteres de comprimento, contendo uma lista de variáveis ​​de caracteres.

Qualquer língua iria funcionar, mas deve ser portátil.

Publicado 02/08/2008 em 07:57
fonte usuário
Em outras línguas...                            


35 respostas

votos
67

Existem várias maneiras de fazer isso. Os métodos mais comuns usar recursão, memoization, ou programação dinâmica. A idéia básica é que você produzir uma lista de todas as cadeias de comprimento 1, em seguida, em cada iteração, para todas as seqüências produzidas na última iteração, adicione essa string concatenado com cada caractere na seqüência individualmente. (O índice variável no código abaixo mantém o controle do início da última e da próxima iteração)

Alguns 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ê precisa então de remover todas as cordas menos de x de comprimento, eles serão os primeiros (x-1) * len (originalString) entradas na lista.

Respondeu 02/08/2008 em 08:48
fonte usuário

votos
35

É melhor usar retrocesso

#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;
}
Respondeu 10/01/2012 em 19:00
fonte usuário

votos
24

Você vai ter um monte de cordas, isso é certo ...

\ sum_ {i = x} ^ Y {\ frac {r!} {{(IR)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20% 7B% 20% 5Cfrac% 7BR% 7D% 7B% 7B (ri)% 7D% 7D% 20% 7D!
Onde, x e y é como você defini-los e r é o número de caracteres que estamos selecionando - -Se eu estou entendendo você corretamente. Você deve definitivamente gerar estes conforme necessário e não ficar desleixado e dizer, gerar um powerset e, em seguida, filtrar o comprimento das cordas.

A seguir definitivamente não é a melhor maneira de gerar estes, mas é um interessante de lado, nada-a-menos.

Knuth (volume 4, fascículo 2, 7.2.1.3) nos diz que (s, t) -combination é equivalente a s + 1 coisas tomado t de cada vez com a repetição - uma (s, t) -combination é notação usada por Knuth que é igual a {t \ escolha {s + t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D . Podemos entender isso, em primeiro lugar gerando cada (s, t) -combination em forma binária (portanto, de comprimento (s + t)) e contagem do número de 0 à esquerda de cada um.

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

Respondeu 05/08/2008 em 05:57
fonte usuário

votos
14

solução recursiva não de acordo com Knuth, Python exemplo:

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)
Respondeu 09/11/2010 em 14:58
fonte usuário

votos
12

Há um monte de 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 : cordas com caracteres repetidos não irá produzir permutações exclusivas.

Respondeu 08/01/2014 em 12:00
fonte usuário

votos
12

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

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

    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;
        }
    }
Respondeu 05/07/2010 em 10:06
fonte usuário

votos
12

Algum código Java trabalhando com base 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);
    }
}
Respondeu 04/04/2010 em 19:18
fonte usuário

votos
12

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

Para cada subconjunto, você ainda tem para gerar todas as permutações. Por exemplo, se você quisesse 3 personagens de "ABCDE", este algoritmo iria dar-lhe "abc", "abd", "abe" ... mas você tem que permutar cada um para obter "acb", "bac", "BCA", etc.

Respondeu 14/11/2008 em 20:36
fonte usuário

votos
8

Eu só chicoteado isto rápida em 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 olhar para API idioma para construído em funções do tipo permutação, e você pode ser capaz de escrever um código mais otimizado, mas se os números são tão alto, eu não tenho certeza que é muito de uma maneira em torno de ter um monte de resultados .

De qualquer forma, a idéia por trás do código é começar com cadeia de comprimento 0, em seguida, manter o controle de todas as strings de comprimento Z, onde Z é o tamanho atual na iteração. Em seguida, passar por cada corda e anexar cada personagem em cada corda. Finalmente, no final, remover qualquer que estavam abaixo do limite de x e devolve o resultado.

Eu não testá-lo com a entrada potencialmente sem sentido (lista de caracteres null, valores estranhos de x e y, etc).

Respondeu 02/08/2008 em 08:56
fonte usuário

votos
7

Rubi resposta 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")
Respondeu 20/04/2012 em 01:21
fonte usuário

votos
7

permute (ABC) -> A.perm (BC) -> A.perm [B.perm (C)] -> A.perm [( * B C), (C, B * )] -> [( * Um aC ), (B a C), (BC a * ), ( * Um CB), (C Uma B), (CB a * )] para remover duplicados ao inserir cada cheque alfabeto para ver se o texto anterior termina com o mesmo alfabeto (porquê?-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 sans duplicatas

Respondeu 22/02/2011 em 19:45
fonte usuário

votos
7

... e aqui é 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;
}
Respondeu 07/02/2011 em 22:56
fonte usuário

votos
7

Em Perl, se você quiser restringir-se ao alfabeto minúsculas, você pode fazer isso:

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

Isto dá todas as cordas possíveis entre 1 e 4 caracteres usando caracteres minúsculos. Para maiúscula, mude "a"para "A"e "zzzz"para "ZZZZ".

Para caso misto torna-se muito mais difícil, e provavelmente não factível com um dos operadores embutidas do Perl como esse.

Respondeu 15/02/2009 em 11:02
fonte usuário

votos
7

Aqui está uma solução recursiva simples 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;
        }

chamar:

string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);
Respondeu 20/10/2008 em 01:17
fonte usuário

votos
7

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;
            }
        }
}
Respondeu 29/09/2008 em 02:34
fonte usuário

votos
7

Esta é uma tradução da versão do rubi de Mike, para Lisp comum:

(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, ligeiramente mais curto e usando mais recursos facilidade 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)))))
Respondeu 16/09/2008 em 06:15
fonte usuário

votos
6

Os seguintes Java recursão imprime todas as permutações de uma determinada string:

//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 é a versão atualizada do método acima "PERMUT" que faz com que n! (Factorial n) chamadas menos recursivos em comparação com o método acima referido

//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()));
   }
}
Respondeu 19/06/2013 em 05:23
fonte usuário

votos
5

Aqui está uma versão não-recursiva eu ​​vim com, em javascript. Não é baseado em um não-recursiva de Knuth acima, embora tenha algumas semelhanças no elemento de troca. Eu tenho verificado sua correção para arrays de entrada de até 8 elementos.

Uma optimização rápida seria pré-flight a outmatriz e evitando push().

A idéia básica é:

  1. Dado um conjunto de fonte única, gerar um primeiro novo conjunto de matrizes que trocar o primeiro elemento com cada elemento subsequente por sua vez, cada vez deixando os outros elementos não perturbado. por exemplo: dado 1234, gerar 1234, 2134, 3214, 4231.

  2. Usar cada matriz a partir da passagem anterior como a semente para uma nova passagem, mas em vez de trocar o primeiro elemento, o segundo elemento de trocar com cada elemento subsequente. Além disso, desta vez, não incluem a matriz original na saída.

  3. Repetir passo 2 até que feito.

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;
}
Respondeu 03/08/2011 em 08:11
fonte usuário

votos
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;
    }
}
Respondeu 24/10/2010 em 23:01
fonte usuário

votos
4

Eu não sei por que você iria querer fazer isso em primeiro lugar. O conjunto resultante de quaisquer moderadamente grandes valores de x e y será enorme, e vai crescer exponencialmente à medida que x e / ou y ficar maior.

Vamos dizer que o seu conjunto de caracteres possíveis são as 26 letras minúsculas do alfabeto, e você perguntar ao seu aplicativo para gerar todas as permutações onde o comprimento = 5. Supondo que você não fique sem memória você vai ter 11.881.376 (ou seja, 26 ao poder de 5) cadeias traseiras. Bump que o comprimento até 6, e você terá 308,915,776 cordas de volta. Estes números ficam dolorosamente grande, muito rapidamente.

Aqui está uma solução que eu juntos em Java. Você precisará fornecer dois argumentos de tempo de execução (correspondente 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);
            }
        }
    }
}
Respondeu 02/08/2008 em 10:40
fonte usuário

votos
3

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

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

Antes de introduzir a loop, inicializar Perm(1 To N)com a primeira permutação, Stack(3 To N)com zeros *, e Levelcom 2**. No final da chamada ciclo NextPerm, que vai retornar falso quando estamos a fazer.

* VB vai fazer isso por você.

** É possível alterar NextPerm um pouco para fazer isso desnecessário, mas é mais clara 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, a outra é conhecida como o método de modificações simples. Jie Gao e Dianjun Wang também escreveu um artigo interessante.

Respondeu 02/10/2011 em 10:13
fonte usuário

votos
2

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

Respondeu 13/02/2014 em 22:08
fonte usuário

votos
2

Este código em python, quando chamado com allowed_charactersconjunto para [0,1]e 4 caracteres no máximo, iria gerar 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 este seja de utilidade para você. Funciona com qualquer personagem, não apenas números

Respondeu 26/05/2011 em 15:22
fonte usuário

votos
2

Em Ruby:

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

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

Eu poderia ter interpretado mal a questão real - embora em uma das mensagens que soou como se você só precisava de uma biblioteca bruteforce de cordas, mas a questão principal parece que você precisa para permutar uma seqüência particular.

Seu problema é um pouco semelhante a esta: http://beust.com/weblog/archives/000491.html (lista todos os inteiros em que nenhum dos dígitos se repetem, o que resultou em um monte de línguas resolvê-lo, com o ocaml cara usando permutações, e um cara java usando ainda uma outra solução).

Respondeu 15/09/2008 em 18:32
fonte usuário

votos
0

Os possíveis permutações de cordas pode ser calculado usando a função recursiva. Abaixo está uma das soluções possíveis.

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());
}
Respondeu 06/02/2017 em 06:00
fonte usuário

votos
0

código escrito para a linguagem java:

namo.algorithms pacote;

importação java.util.Scanner;

Permuations classe pública {

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

}

Respondeu 05/06/2016 em 08:42
fonte usuário

votos
0

Bem, aqui é um elegante, não-recursivo, O (n!) Solução:

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;
    }
Respondeu 27/06/2015 em 08:44
fonte usuário

votos
0

A solução pythônico:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
Respondeu 13/07/2014 em 08:51
fonte usuário

votos
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

Aqui é a minha opinião sobre uma versão não recursiva

Respondeu 23/01/2014 em 04:28
fonte usuário

votos
0

Solução recursiva com condutor main()método.

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

}

Respondeu 19/10/2013 em 02:34
fonte usuário

votos
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
Respondeu 22/08/2013 em 18:51
fonte usuário

votos
0

Uma solução recursiva no pitão. A coisa boa sobre este código é que ele exporta um dicionário, com chaves como cordas e todas as permutações possíveis como valores. Todos os possíveis comprimentos de cordas estão incluídas, assim, em efeito, você está criando um super.

Se você só exigem as permutações finais, você pode excluir outras chaves do dicionário.

Neste código, o dicionário de permutações é global.

No caso base, eu armazenar o valor que ambas as possibilidades em uma lista. perms['ab'] = ['ab','ba'].

Para comprimentos de cadeia mais elevados, a função refere-se a diminuir comprimentos de cadeia e incorpora as permutações previamente calculados.

A função faz duas coisas:

  • chama-se com uma corda menor
  • retorna uma lista de permutações de uma seqüência particular se já disponível. Se voltou a si, estes serão utilizados para anexar ao caráter e criar permutações mais recentes.

Caro para a memória.

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]
Respondeu 05/07/2013 em 05:15
fonte usuário

votos
0

Não é uma implementação Java iterativo em UncommonsMaths (trabalha para uma lista de objetos):

/**
 * 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 completo

Respondeu 07/05/2013 em 02:18
fonte usuário

votos
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;
    }
Respondeu 26/07/2012 em 16:20
fonte usuário

votos
0

Embora isso não responder à sua pergunta exatamente, aqui está uma maneira de gerar todas as permutações das letras a partir de um número de cordas do mesmo comprimento: por exemplo, se suas palavras foram "café", "Joomla" e "moodle", você pode esperar uma saída como "coodle", "joodee", "joffle", etc.

Basicamente, o número de combinações é o (número de palavras) para o poder de (número de letras por palavra). Então, escolha um número aleatório entre 0 e o número de combinações - 1, converter esse número para base (número de palavras), então use cada dígito desse número como o indicador para o qual palavra para dar o próximo carta.

por exemplo: no exemplo acima. 3 palavras, letras 6 = 729 combinações. Escolha um número aleatório: 465. Converter para basear 3: 122020. Tome a primeira letra da palavra 1, 2 da palavra 2, 3 da palavra 2, 4 de palavra 0 ... e você começa ... "joofle".

Se você queria todas as permutações, apenas laço de 0 a 728. Claro que, se você está apenas escolhendo um valor aleatório, um tanto mais simples maneira menos confuso seria para fazer um loop sobre as letras. Este método permite-lhe evitar recursão, se você quiser todas as permutações, além de que faz você olhar como você sabe Matemática (tm) !

Se o número de combinações é excessiva, você pode dividi-lo em uma série de palavras menores e concatenar-los no final.

Respondeu 16/09/2008 em 06:33
fonte usuário

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