Generating permutations using bash

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 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