siliconpi siliconpi - 6 months ago 11
Bash Question

Generating permutations using bash

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

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