Generate all permutations of up to `n` letters

Question

I'd like to generate all permutations of letters up to length n

For example, for the argument 2 I'd like obtain a list like

a
aa
..
az
...
z
za
..
zz

---

I tried using a for loop to generate n increasingly larger brace expansions by repeating {a..z} ^1 and appending it to a variable. But this doesn't seem to work.

OUT=""

# loop from 1 to first argument
for ((i=1; i<=$1; i++))
do
    OUT+=$(echo $(printf '{a..z}%.0s' {1..$i}))
done

OUT=$(echo $OUT | sort)

echo $OUT

Tiaratibbetts

Answer 1

Chained brace expansions don't scale well. You're better off with a function like this:

# Usage: perms n [prefix]
perms() {
  if (($1 < 1)); then
    return
  fi

  for pfix in "$2"{a..z}; do
    printf '%s\n' "$pfix"
    perms $(($1 - 1)) "$pfix"
  done
}

$ perms 2
a
aa
ab
ac
...

But if you insist on it, this is how you should do it:

# Usage: perms n
perms() {
  printf -v brace_exp '{a..z}%*s' $(($1 - 1))
  brace_exp=${brace_exp// /'{,{a..z}}'}
  eval "printf '%s\n' $brace_exp"
}

Surprint

Very clean, and being already sorted is a nice bonus! – Tiaratibbetts

Is there also a clever way to generate all permutations of exactly n letters (discarding the shorter ones)? – Tiaratibbetts

@Tiaratibbetts Move printf above return ideone.com/eZb34s – Surprint

Answer 2

This is a case where eval might be your best bet. There isn't a security concern as long as you strictly control the content of brace_string and it allows you to build a list of brace expansions that can do what you want.

#!/bin/bash

make_list() {
  brace_string=""
  for ((i=0 ; i < $1 ; i++)) ; do
    brace_string+="{a..z}"
    eval printf "'%s\n'" "${brace_string}"
  done
}

make_list "$1" | sort

The problem with {1..$i} or with building a list of brace expansions in a variable without eval is that the bash parser evaluates syntax before it expands variables. That means {1..$i} is just treated like a string because $i isn't a single character or integer (it gets replaced by an integer later, but bash can't see into the future). eval works around this by letting you perform all the parsing steps twice, meaning $i can get replaced on the first parsing and then the brace expansion is valid on the second parsing. And, more relevant to the above example, "$brace_string" won't be treated as a brace expansion on the first parsing because the variable hasn't been replaced by the time bash does syntax analysis, but it can be handled on a second parsing through eval.

Induce

Thanks, this works well. Though it seems to buffer all data in memory before it's outputted, e.g. using foo.sh > out.txt. Is it possible to make this "streaming" such that it doesn't buffer all data in memory? – Tiaratibbetts

Answer 3

Try this Shellcheck-clean pure Bash code:

#! /bin/bash -p

n=$1
(( n == 0 )) && exit 0
perms=( {z..a} )
while (( (ilast = ${#perms[*]}-1) >= 0 )); do
    p=${perms[ilast]}
    unset 'perms[ilast]'

    printf '%s\n' "$p"
    (( ${#p} < n )) && perms+=( "$p"{z..a} )
done

• The code uses an array as a stack to implement an iterative depth-first search of a tree of permutations.
• It's been tested with Bash versions 3, 4, and 5.

The code can be made significantly faster (around 4x) by outputting the maximum-length permutations in alphabet-sized groups:

#! /bin/bash -p

n=$1
(( n == 0 )) && exit 0
perms=( {z..a} )
while (( (ilast = ${#perms[*]}-1) >= 0 )); do
    p=${perms[ilast]}
    unset 'perms[ilast]'

    printf '%s\n' "$p"
    if (( ${#p} < (n-1) )); then
        perms+=( "$p"{z..a} )
    elif (( ${#p} == (n-1) )); then
        printf '%s\n' "$p"{a..z}
    fi
done

• On my (unexotic) test VM, this code generated all permutations up to length 4 in 3s, 5 in 1.5m, and 6 in 41m.

Hannah