string - programa - Generar lista de todas las posibles permutaciones de una cadena

permutaciones python

Question

¿Cómo podría generar una lista de todas las permutaciones posibles de una cadena entre los caracteres x e y de longitud, que contiene una lista variable de caracteres?

Cualquier lenguaje funcionaría, pero debería ser portátil.

Answer 1

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 eliminar duplicados al insertar cada alfabeto, verifique si la cadena anterior termina con el mismo alfabeto (¿Por qué? -Ejercicio)

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 las permutaciones sin duplicados

Answer 2

... y aquí está la versión 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 3

Acabo de batir esto rápidamente en 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

Puede buscar en la API de lenguaje para funciones integradas de tipo de permutación, y puede escribir más código optimizado, pero si los números son tan altos, no estoy seguro de que haya muchos resultados que tengan muchos resultados .

De todos modos, la idea detrás del código es comenzar con una cadena de longitud 0, luego hacer un seguimiento de todas las cadenas de longitud Z donde Z es el tamaño actual en la iteración. Luego, recorra cada cadena y agregue cada carácter a cada cadena. Finalmente, al final, elimine cualquiera que esté por debajo del umbral x y devuelva el resultado.

No lo probé con entradas potencialmente sin sentido (lista de caracteres nulos, valores extraños de x e y, etc.).

Answer 4

Algún código Java de trabajo basado en la respuesta 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);
}
}

Answer 5

Aquí hay un enlace que describe cómo imprimir las permutaciones de una cadena. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

Answer 6

Aquí hay una solución recursiva simple de la palabra 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;
}

Vocación:

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

Answer 7

Aquí hay una solución simple en C #.

Genera solo las distintas permutaciones de una cadena dada.

 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

Aquí hay una versión no recursiva que se me ocurrió, en javascript. No se basa en el no recursivo de Knuth anterior, aunque tiene algunas similitudes en el intercambio de elementos. He verificado su corrección para matrices de entrada de hasta 8 elementos.

Una optimización rápida sería antes de volar la matriz de out y evitar push() .

La idea básica es:

1. Dada una matriz de origen única, genere un primer conjunto nuevo de matrices que intercambien el primer elemento con cada elemento subsiguiente, dejando cada vez que los otros elementos no se vean afectados. por ejemplo: dado 1234, generar 1234, 2134, 3214, 4231.

2. Utilice cada matriz de la pasada anterior como semilla para una nueva pasada, pero en lugar de intercambiar el primer elemento, intercambie el segundo elemento con cada elemento posterior. Además, esta vez, no incluya la matriz original en la salida.

3. Repita el paso 2 hasta que termine.

Aquí está el ejemplo del 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;
}

Answer 9

Aunque esto no responde exactamente a su pregunta, aquí hay una manera de generar cada permutación de las letras a partir de una serie de cadenas de la misma longitud: por ejemplo, si sus palabras fueron "café", "joomla" y "moodle", puede espera la salida como "coodle", "joodee", "joffle", etc.

Básicamente, el número de combinaciones es el (número de palabras) al poder de (número de letras por palabra). Por lo tanto, elija un número aleatorio entre 0 y el número de combinaciones - 1, convierta ese número en base (número de palabras), luego use cada dígito de ese número como indicador de la palabra desde la cual debe tomar la próxima letra.

Por ejemplo: en el ejemplo anterior. 3 palabras, 6 letras = 729 combinaciones. Elija un número aleatorio: 465. Convierta a base 3: 122020. Tome la primera letra de la palabra 1, 2ª de la palabra 2, 3ª de la palabra 2, 4ª de la palabra 0 ... y obtendrá ... "joofle".

Si deseara todas las permutaciones, solo haga un bucle de 0 a 728. Por supuesto, si solo está eligiendo un valor aleatorio, una forma mucho más sencilla y menos confusa sería hacer un bucle sobre las letras. Este método te permite evitar la recursión, si quieres todas las permutaciones, además, ¡te hace parecer que sabes Matemáticas ^(tm) !

Si el número de combinaciones es excesivo, puede dividirlo en una serie de palabras más pequeñas y concatenarlas al final.

Answer 10

Bueno, aquí hay una solución elegante, no recursiva, O (n!):

public static StringBuilder[] permutations(String s) {
if (s.length() == 0)
return null;
int length = fact(s.length());
StringBuilder[] sb = new StringBuilder[length];
for (int i = 0; i < length; i++) {
sb[i] = new StringBuilder();
}
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
int times = length / (i + 1);
for (int j = 0; j < times; j++) {
for (int k = 0; k < length / times; k++) {
sb[j * length / times + k].insert(k, ch);
}
}
}
return sb;
}

Answer 11

En Perl, si quieres restringirte al alfabeto en minúsculas, puedes hacer esto:

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

Esto da todas las cadenas posibles entre 1 y 4 caracteres usando caracteres en minúscula. Para mayúsculas, cambie "a" a "A" y "zzzz" a "ZZZZ" .

Para el caso mixto, se vuelve mucho más difícil, y probablemente no sea factible con uno de los operadores integrados de Perl como ese.

Answer 12

En rubi

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

Es bastante rápido, pero va a tomar algún tiempo =). Por supuesto, puede comenzar en "aaaaaaaa" si las cadenas cortas no son interesantes para usted.

Aunque podría haber malinterpretado la pregunta real, en una de las publicaciones sonaba como si solo necesitaras una biblioteca de cadenas de fuerza bruta, pero en la pregunta principal parece que necesitas permutar una cadena en particular.

Su problema es algo similar a este: http://beust.com/weblog/archives/000491.html (enumere todos los números enteros en los que ninguno de los dígitos se repite, lo que dio lugar a que muchos idiomas lo resolvieran, con el ocaml guy usando permutaciones, y algunos java guy usando otra solución).

Answer 13

Es mejor usar 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 14

Esta es una traducción de la versión de Mike''s Ruby, a 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)))))

Y otra versión, ligeramente más corta y con más funciones de instalación de bucle:

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

Este código en python, cuando se allowed_characters con los caracteres allowed_characters establecidos en [0,1] y 4 caracteres como máximo, generará 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 esto te sea de utilidad. Funciona con cualquier personaje, no solo con números.

Answer 16

Hay muchas buenas respuestas aquí. También sugiero una solución recursiva muy simple en C ++.

#include <string>
#include <iostream>
template<typename Consume>
void permutations(std::string s, Consume consume, std::size_t start = 0) {
if (start == s.length()) consume(s);
for (std::size_t i = start; i < s.length(); i++) {
std::swap(s[start], s[i]);
permutations(s, consume, start + 1);
}
}
int main(void) {
std::string s = "abcd";
permutations(s, [](std::string s) {
std::cout << s << std::endl;
});
}

Nota : las cadenas con caracteres repetidos no producirán permutaciones únicas.

Answer 17

Hay varias formas de hacerlo. Los métodos comunes utilizan recursión, memorización o programación dinámica. La idea básica es que produzca una lista de todas las cadenas de longitud 1, luego en cada iteración, para todas las cadenas producidas en la última iteración, agregue esa cadena concatenada con cada carácter de la cadena individualmente. (El índice de variable en el código siguiente realiza un seguimiento del inicio de la última iteración y la siguiente)

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

luego necesitaría eliminar todas las cadenas de menos de x de longitud, serán las primeras (x-1) * len (originalString) entradas en la lista.

Answer 18

La siguiente recursión de Java imprime todas las permutaciones de una cadena dada:

//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 continuación se muestra la versión actualizada del método anterior "permut" que hace n! (n factorial) llamadas menos recursivas en comparación con el método anterior

//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 19

La solución pitónica:

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

Answer 20

Necesitaba esto hoy, y aunque las respuestas ya dadas apuntaban en la dirección correcta, no eran exactamente lo que quería.

Aquí hay una implementación usando el método de Heap. La longitud de la matriz debe ser de al menos 3 y, por razones prácticas, no debe ser superior a 10, dependiendo de lo que desee hacer, la paciencia y la velocidad del reloj.

Antes de ingresar a su ciclo, inicie Perm(1 To N) con la primera permutación, Stack(3 To N) con ceros * y Level con 2 **. Al final del bucle, llame a NextPerm , que devolverá false cuando hayamos terminado.

* VB hará eso por ti.

** Puedes cambiar NextPerm un poco para que esto no sea necesario, pero es más claro así.

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

Otros métodos son descritos por varios autores. Knuth describe dos, uno da un orden léxico, pero es complejo y lento, el otro se conoce como el método de los cambios simples. Jie Gao y Dianjun Wang también escribieron un interesante artículo.

Answer 21

No estoy seguro de por qué querrías hacer esto en primer lugar. El conjunto resultante para cualquier valor moderadamente grande de x e y será enorme, y crecerá exponencialmente a medida que x y / o y se hagan más grandes.

Digamos que su conjunto de posibles caracteres son las 26 letras minúsculas del alfabeto, y le pide a su aplicación que genere todas las permutaciones donde longitud = 5. Suponiendo que no se quede sin memoria, obtendrá 11.881.376 (es decir, 26 a la potencia) de 5) cuerdas atrás. Golpee esa longitud hasta 6, y obtendrá 308,915,776 cuerdas hacia atrás. Estos números se vuelven dolorosamente grandes, muy rápidamente.

Aquí hay una solución que armé en Java. Tendrá que proporcionar dos argumentos de tiempo de ejecución (correspondientes a x e y). Que te diviertas.

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 22

Puede consultar " Enumerar eficientemente los subconjuntos de un conjunto ", que describe un algoritmo para hacer parte de lo que desea: generar rápidamente todos los subconjuntos de N caracteres de la longitud x a y. Contiene una implementación en C.

Para cada subconjunto, aún tendrías que generar todas las permutaciones. Por ejemplo, si quisiera 3 caracteres de "abcde", este algoritmo le daría "abc", "abd", "abe" ... pero tendría que permutar cada uno para obtener "acb", "bac", "bca", etc.

Answer 23

Respuesta de rubí 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")

Answer 24

Solución no recursiva según Knuth, ejemplo de 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 25

Solución recursiva en C ++

int main (int argc, char * const argv[]) {
string s = "sarp";
bool used [4];
permute(0, "", used, s);
}
void permute(int level, string permuted, bool used [], string &original) {
int length = original.length();
if(level == length) { // permutation complete, display
cout << permuted << endl;
} else {
for(int i=0; i<length; i++) { // try to add an unused character
if(!used[i]) {
used[i] = true;
permute(level+1, original[i] + permuted, used, original); // find the permutations starting with this string
used[i] = false;
}
}
}

Answer 26

Usted va a tener un montón de cadenas, eso es seguro ...

/ sum_ {i = x} ^ y {/ frac {r!} {{(ri)}!} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20% 7B% 20% 5Cfrac% 7Br!% 7D% 7B% 7B (ri)% 7D!% 7D% 20% 7D
Donde, x e y es cómo los define y r es el número de caracteres que seleccionamos, si lo estoy entendiendo correctamente. Definitivamente, debe generarlos según sea necesario y no quedarse descuidado y decir, generar un conjunto de poderes y luego filtrar la longitud de las cadenas.

Definitivamente, lo siguiente no es la mejor manera de generarlos, pero, aparte de eso, es un punto interesante.

Knuth (volumen 4, fascículo 2, 7.2.1.3) nos dice que la combinación (s, t) es equivalente a s + 1 cosas tomadas t a la vez con repetición: una combinación (s, t) es una notación utilizada por Saber que es igual a {t / elegir {s + t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D . Podemos resolver esto generando primero cada combinación (s, t) en forma binaria (es decir, de longitud (s + t)) y contando el número de 0 a la izquierda de cada 1.

10001000011101 -> se convierte en la permutación: {0, 3, 4, 4, 4, 1}

Answer 27

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

Aquí está mi versión de una versión no recursiva

Answer 30

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