Generando permutaciones usando bash

¿es posible escribir un script bash que pueda leer en cada línea desde un archivo y generar permutaciones (sin repetición) para cada una? Usar awk / perl está bien.

File ---- ab abc Output ------ ab ba abc acb bac bca cab cba 

Pure bash (usando local , más rápido, pero no puede vencer a la otra respuesta usando awk debajo, o Python abajo):

 perm() { local items="$1" local out="$2" local i [[ "$items" == "" ]] && echo "$out" && return for (( i=0; i< ${#items}; i++ )) ; do perm "${items:0:i}${items:i+1}" "$out${items:i:1}" done } while read line ; do perm $line ; done < File 

Pure bash (utilizando subshell, mucho más lento):

 perm() { items="$1" out="$2" [[ "$items" == "" ]] && echo "$out" && return for (( i=0; i< ${#items}; i++ )) ; do ( perm "${items:0:i}${items:i+1}" "$out${items:i:1}" ) done } while read line ; do perm $line ; done < File 

Como asker mencionó que Perl está bien, creo que Python 2.6 + / 3.X también está bien:

 python -c "from itertools import permutations as p ; print('\n'.join([''.join(item) for line in open('File') for item in p(line[:-1])]))" 

Para Python 2.5 + / 3.X:

 #!/usr/bin/python2.5 # http://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python/104436#104436 def all_perms(str): if len(str) < =1: yield str else: for perm in all_perms(str[1:]): for i in range(len(perm)+1): #nb str[0:1] works in both string and list contexts yield perm[:i] + str[0:1] + perm[i:] print('\n'.join([''.join(item) for line in open('File') for item in all_perms(line[:-1])])) 

En mi computadora usando un archivo de prueba más grande:

 First Python code Python 2.6: 0.038s Python 3.1: 0.052s Second Python code Python 2.5/2.6: 0.055s Python 3.1: 0.072s awk: 0.332s Bash (local): 2.058s Bash (subshell): 22+s 

Sé que llego un poco tarde al juego, pero ¿por qué no ampliarme?

Por ejemplo:

 echo {a..z}{0..9} 

Productos:

 a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 c0 c1 c2 c3 c4 c5 c6 c7 c8 c9 d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 g0 g1 g2 g3 g4 g5 g6 g7 g8 g9 h0 h1 h2 h3 h4 h5 h6 h7 h8 h9 i0 i1 i2 i3 i4 i5 i6 i7 i8 i9 j0 j1 j2 j3 j4 j5 j6 j7 j8 j9 k0 k1 k2 k3 k4 k5 k6 k7 k8 k9 l0 l1 l2 l3 l4 l5 l6 l7 l8 l9 m0 m1 m2 m3 m4 m5 m6 m7 m8 m9 n0 n1 n2 n3 n4 n5 n6 n7 n8 n9 o0 o1 o2 o3 o4 o5 o6 o7 o8 o9 p0 p1 p2 p3 p4 p5 p6 p7 p8 p9 q0 q1 q2 q3 q4 q5 q6 q7 q8 q9 r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 s0 s1 s2 s3 s4 s5 s6 s7 s8 s9 t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 u0 u1 u2 u3 u4 u5 u6 u7 u8 u9 v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 w0 w1 w2 w3 w4 w5 w6 w7 w8 w9 x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 y0 y1 y2 y3 y4 y5 y6 y7 y8 y9 z0 z1 z2 z3 z4 z5 z6 z7 z8 z9 

Otro ejemplo útil:

 for X in {a..z}{a..z}{0..9}{0..9}{0..9} do echo $X; done 

Una versión más rápida con awk

 function permute(s, st, i, j, n, tmp) { n = split(s, item,//) if (st > n) { print s; return } for (i=st; i< =n; i++) { if (i != st) { tmp = item[st]; item[st] = item[i]; item[i] = tmp nextstr = item[1] for (j=2; j<=n; j++) nextstr = nextstr delim item[j] }else { nextstr = s } permute(nextstr, st+1) n = split(s, item, //) } } { permute($0,1) } 

uso:

 $ awk -f permute.awk file 

Usando el crunch util, y bash :

 while read a ; do crunch ${#a} ${#a} -p "$a" ; done 2> /dev/null < File 

Salida:

 ab ba abc acb bac bca cab cba 

Tutorial aquí https://pentestlab.blog/2012/07/12/creating-wordlists-with-crunch/

Vea el Perl Cookbook para ejemplos de permutación. Están orientados a palabras / números, pero una simple split() / join() en el ejemplo anterior será suficiente.

Bash lista de palabras / diccionario / generador de permutación:

El siguiente código Bash genera permutación de 3 caracteres sobre 0-9, az, AZ. Te da (10 + 26 + 26) ^ 3 = 238,328 palabras en la salida.

No es muy escalable, ya que puede ver que necesita boost el número de bucle para boost los caracteres en combinación. Sería mucho más rápido escribir tal cosa en el ensamblaje o C usando recurrencia para boost la velocidad. El código de Bash es solo para demostración.

PD : puedes poblar la variable $list con list=$(cat input.txt)

 #!/bin/bash list=`echo {0..9} {a..z} {A..Z}` for c1 in $list do for c2 in $list do for c3 in $list do echo $c1$c2$c3 done done done 

SALIDA DE MUESTRA:

 000 001 002 003 004 005 ... ... ... ZZU ZZV ZZW ZZX ZZY ZZZ [babil@quad[13:27:37][~]> wc -l t.out 238328 t.out 
 $ ruby -ne '$_.chomp.chars.to_a.permutation{|x| puts x.join}' file # ver 1.9.1 

Porque nunca puedes tener enogh críptico Bash-oneliners:

 while read s;do p="$(echo "$s"|sed -e 's/./&,/g' -e 's/,$//')";eval "printf "%s\\\\n" "$(eval 'echo "$(printf "{'"$p"'}%.0s" {0..'"$((${#s}-1))"'})"')"|grep '\(.\)\1*.*\1' -v";echo;done  

Es bastante rápido, al menos en mi máquina aquí:

 $ time while read s;do p="$(echo "$s"|sed -e 's/./&,/g' -e 's/,$//')";eval "printf "%s\\\\n" "$(eval 'echo "$(printf "{'"$p"'}%.0s" {0..'"$((${#s}-1))"'})"')"|grep '\(.\)\1*.*\1' -v";echo;done /dev/null real 0m0.021s user 0m0.000s sys 0m0.004s 

Pero ten en cuenta que éste comerá mucha memoria cuando pases de 8 caracteres ...