Generando permutaciones usando bash

Question

¿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 

Answer 1

fiesta pura (usando local, más rápido, pero no puede vencer a la otra respuesta usando awk a continuación, o el pitón más adelante):

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 

fiesta pura (usando subnivel, 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 

Desde mencionó autor de la pregunta Perl está bien, creo que Python 2.6 +/3.X está bien, también:

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

de mi equipo con 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 

Answer 2

Consulte el Perl Cookbook para ejemplos de permutación. Son palabra/número orientado, pero un simple split()/join() en su ejemplo anterior será suficiente.

Answer 3

$ ruby -ne '$_.chomp.chars.to_a.permutation{|x| puts x.join}' file # ver 1.9.1 

Answer 4

Una versión más rápida mediante el uso de 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) } 

:

$ awk -f permute.awk file 

Answer 5

Utilizando el util crunch 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/

Answer 6

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

El El siguiente código Bash genera permut de 3 caracteres ación sobre 0-9, a-z, A-Z. Te da (10 + 26 + 26)^3 = 238,328 palabras en la salida.

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

P.S. Puede rellenar $list variable SALIDA 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 

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 

Answer 7

Debido a que usted nunca puede tener suficientes mesas crípticos 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 <f 

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 <f >/dev/null 

real 0m0.021s 
user 0m0.000s 
sys 0m0.004s 

Pero tenga en cuenta que éste va a comer una gran cantidad de memoria cuando se va más allá de 8 caracteres ...

Answer 8

Yo sé que soy un poco tarde para el juego, pero ¿por qué no la expansión de llaves?

Por ejemplo:

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

Salidas:

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