Generowanie permutacji przy użyciu basha

Question

czy można napisać skrypt bash, który może odczytać w każdej linii z pliku i wygenerować permutacje (bez powtórzeń) dla każdego z nich? Używanie awk/perl jest w porządku.

File 
---- 
ab 
abc 


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

Answer 1

Czysta bash (używając local, szybciej, ale nie można pokonać inną odpowiedź za pomocą awk poniżej lub poniżej Python):

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 

Czysta bash (używając powłoki w tle, dużo wolniej):

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 

Od Pytający wspomniano Perl jest w porządku, myślę, że Python 2.6 +/3.X jest w porządku, zbyt:

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

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

na moim komputerze przy użyciu większy plik testowy:

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

Zobacz przykłady permutacji na stronie Perl Cookbook. Są zorientowane na słowo/liczbę, ale wystarczy prosty split()/ w powyższym przykładzie.

Answer 3

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

Answer 4

szybsza wersja używając 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) } 

użytkowania:

$ awk -f permute.awk file 

Answer 5

Używanie crunch util i bash:

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

wyjściowa:

ab 
ba 
abc 
acb 
bac 
bca 
cab 
cba 

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

Answer 6

Bash słowo lista/słownik/permutacji generator:

następujący kod Bash generuje 3-znakową permut nad 0-9, a-z, A-Z. Daje ci (10 + 26 + 26)^3 = 238 328 słów na wyjściu.

Nie jest zbyt skalowalny, ponieważ widać, że trzeba zwiększyć liczbę pętli for, aby zwiększyć liczbę znaków w połączeniu. O wiele szybciej byłoby napisać coś takiego w zespole lub przy użyciu rekurencji, aby zwiększyć prędkość. Kod Bash służy wyłącznie do demonstracji.

P.S. można zapełnić $list zmienną 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 

SAMPLE wyjściowa:

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

Ponieważ nigdy nie można mieć enogh tajemnicze 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 

Jest to dość szybko - przynajmniej na mojej maszynie tutaj:

$ 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 

Ale należy pamiętać, że ten będzie jeść dużo pamięci, jeśli wykracza poza 8 znaków ...

Answer 8

Wiem, że jestem trochę późno do gry, ale dlaczego nie nawiasów?

Na przykład:

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

Wyjścia:

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 

Inną użyteczną przykład:

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