views:

202

answers:

6

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

File
----
ab
abc


Output
------
ab
ba
abc
acb
bac
bca
cab
cba
+1  A: 

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

Brian Agnew
A: 
$ ruby -ne '$_.chomp.chars.to_a.permutation{|x| puts x.join}' file # ver 1.9.1
gives an error - undefined method `chars'
matt_tm
+2  A: 

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
livibetter
Instead of `cat File | while` do `done < File`.
Dennis Williamson
nice bash, but too slow if length gets bigger
ghostdog74
Also, you can do math in array slicing without `$(())` and you can omit the dollar signs: `( perm "${items:0:i}${items:i+1}" "$out${items:i:1} )"
Dennis Williamson
@Dennis, thanks for the tips, answer edited.
livibetter
on my computer, awk is always the fastest.
ghostdog74
@user131527, what was the Python version you using? If it's 2.5, then that result is incorrect. My original python code doesn't work for 2.5 and 3.1, and it runs slower than awk, but it's incorrect. I have updated the code and they all are much faster than awk.
livibetter
Awesome - didnt think it was possible!
matt_tm
A: 

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
ghostdog74
THanks user131 - i'll be testing it out and seeing how it compares as well...
matt_tm
+1  A: 

There is a simple C program called crunch that does this permutation with very useful options.

jyzuz
+1  A: 

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
Babil