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
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
See the Perl Cookbook for permutation examples. They're word/number oriented but a simple split()
/join()
on your above example will suffice.
$ ruby -ne '$_.chomp.chars.to_a.permutation{|x| puts x.join}' file # ver 1.9.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
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
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