#! /usr/bin/gawk -f
# Last edited on 1999-07-22 14:12:40 by stolfi

# Usage: enum-perms -v elems="XxYyZz..."
#
# Enumerates all valid permutations of a given list of letters "elems".

BEGIN {
  abort = -1;
  if (elems == "") { error("must define \"elems\""); }
  s = elems;
  split("", f); nf = length(s);
  for (i=0; i<nf; i++) { f[i] = substr(s,i+1,1); }
  
  split("", p); np = 0;
  
  recurse();
}

function recurse(   i)
{
  # "f[0..nf-1]" are the still unused elements.
  # "p[0..np-1]" is the partial permutation built so far.
  
  # printf "+ np = %d nf = %d\n", np, nf > "/dev/stderr"
  
  if (nf == 0) { print_perm(); return; }
  if (nh > 0) 
    { # Fold in the last hanging folio:
      nh--; p[np] = h[nh]; np++;
      recurse();
      np--; h[nh] = p[np]; nh++;
    }
  if (nf > 0)
    { # Place each unused element in turn: 
      for (i=0; i<nf; i++)
        { # Place the element:
          p[np] = f[i]; np++; 
          # Remove it from the free folio list
          nf--; f[i] = f[nf];
          recurse();
          # Now return the element to the free element bag:
          f[nf] = f[i]; nf++;
          np--; f[i] = p[np];
        }
    }
}

function print_perm(  j)
{
  for(j=0; j<np; j++){ printf "%s", p[j]; }
  printf "\n"; 
}

function error(msg)
{ 
  printf "line %d: %s\n", NR, msg > "/dev/stderr";
  abort = 1;
  exit 1;
}