Generating permutations using bash

问题:

is it possible to write a bash script that can read in each line from a file and generate permutations (without repetition) for each? Using awk / perl is fine.

File
----
ab
abc


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

回答1:

Pure bash (using local, faster, but can't beat the other answer using awk below, or the Python below):

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 (using subshell, much slower):

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

Since asker mentioned Perl is fine, I think Python 2.6+/3.X is fine, too:

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

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

On my computer using a bigger test file:

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

回答2:

I know I am a little late to the game but why not brace expansion?

For example:

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

Outputs:

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

Another useful example:

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

回答3:

A faster version using 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) }

usage:

$ awk -f permute.awk file

回答4:

Using the crunch util, and 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 here https://pentestlab.blog/2012/07/12/creating-wordlists-with-crunch/

回答5:

See the Perl Cookbook for permutation examples. They're word/number oriented but a simple split()/join() on your above example will suffice.

回答6:

Bash word-list/dictionary/permutation generator:

The following Bash code generates 3 character permutation over 0-9, a-z, A-Z. It gives you (10+26+26)^3 = 238,328 words in output.

It's not very scalable as you can see you need to increase the number of for loop to increase characters in combination. It would be much faster to write such thing in assembly or C using recursion to increase speed. The Bash code is only for demonstration.

P.S. You can populate $list variable with 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 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

回答7:

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

回答8:

Because you can never have enogh cryptic 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

It's pretty fast - at least on my machine here:

$ 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

But be aware that this one will eat a lot of memory when you go beyond 8 characters...