Tạo hoán vị bằng cách sử dụng bash

Question

là có thể viết một tập lệnh bash có thể đọc trong mỗi dòng từ một tệp và tạo các hoán vị (không lặp lại) cho mỗi tệp không? Sử dụng awk/perl là tốt.

File 
---- 
ab 
abc 


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

Answer 1

bash tinh khiết (sử dụng local, nhanh hơn, nhưng không thể đánh bại câu trả lời khác sử dụng awk dưới đây, hoặc Python dưới đây):

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 

bash tinh khiết (sử dụng subshell, chậm hơn nhiều):

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 

Kể từ khi Người hỏi đã nêu Perl là tốt, tôi nghĩ rằng Python 2.6 +/3.x là tốt, quá:

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

Đối với 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])])) 

Trên máy tính của tôi sử dụng một tập tin thử nghiệm lớn hơn:

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

Xem Perl Cookbook để biết ví dụ hoán vị. Chúng được định hướng từ/số nhưng đơn giản là split()/join() trên ví dụ trên của bạn sẽ đủ.

Answer 3

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

Answer 4

Một phiên bản nhanh hơn sử dụng 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) } 

sử dụng:

$ awk -f permute.awk file 

Answer 5

Sử dụng crunch util và bash:

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

Output:

ab 
ba 
abc 
acb 
bac 
bca 
cab 
cba 

Tutorial đây https://pentestlab.blog/2012/07/12/creating-wordlists-with-crunch/

Answer 6

Bash từ-list/từ điển/hoán vị phát điện:

Các sau Bash mã tạo ra 3 ký tự hoán vị ation trên 0-9, a-z, A-Z. Nó cung cấp cho bạn (10 + 26 + 26)^3 = 238,328 từ trong đầu ra.

Nó không phải là rất khả năng mở rộng như bạn có thể thấy bạn cần phải tăng số lượng for vòng lặp để tăng ký tự kết hợp. Sẽ nhanh hơn nhiều khi viết những thứ như vậy trong assembly hoặc C bằng cách sử dụng đệ quy để tăng tốc độ. Mã Bash chỉ để trình diễn.

P.S. Bạn có thể cư $list biến với 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 

MẪU OUTPUT:

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

Bởi vì bạn không bao giờ có thể có enogh khó hiểu 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 

Nó khá nhanh - ít nhất trên máy của tôi ở đây:

$ 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 

Nhưng lưu ý rằng điều này sẽ ăn rất nhiều bộ nhớ khi bạn đi xa hơn 8 ký tự ...

Answer 8

Tôi biết tôi là một chút muộn để các trò chơi nhưng tại sao không cú đúp mở rộng?

Ví dụ:

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

Đầu ra:

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 

Một ví dụ hữu ích:

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