Generate lexicographic permutations

Here is an (inefficient) implementation in plain bash. It also works with repeated characters. It does not require a sort utility provided that the constituent characters of the initial string are already sorted.

$ cat permute

#!/bin/bash

nextperm () {
    local i j rhs

    for ((i = ${#perm} - 1; i > 0; --i)); do
        rhs+=${perm:i:1}
        [[ ${perm:i-1:1} < ${perm:i:1} ]] && break
    done
    ((i <= 0)) && return 1

    for ((j = 0; ; ++j)); do [[ ${rhs:j:1} > ${perm:i-1:1} ]] && break; done

    perm=${perm:0:i-1}${rhs:j:1}${rhs:0:j}${perm:i-1:1}${rhs:j+1}
    echo "$perm"
}

perm=$1
echo "$perm"
while nextperm; do :; done

$ ./permute 123

123
132
213
231
312
321

$ ./permute 1122

1122
1212
1221
2112
2121
2211

$ cat prog.awk
BEGIN {
  nElem = split(set, mySet)
  if (nElem > 0)
    perms(mySet, nElem)
}

function perms(set, nElem, perm, cnt, ind, elem) {
  if (nElem == 0) {
    print perm
    return
  }

  cnt = 0
  for (ind = 1; cnt < nElem; ind++) {
    if (!(ind in set))
      continue

    elem = set[ind]
    delete set[ind]
    perms(set, nElem - 1, perm elem)
    set[ind] = elem
    cnt++
  }
}

$ awk -v set='1 2 3 4' -f prog.awk
1234
1243
1324
1342
1423
...

Given a set whose elements are lexicographically sorted, this will generate lexicographic permutations; otherwise, you will need to pipe its output to sort.