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

# Usage: enum-folio-perms -v elems="XxYyZz..."
#
# Enumerates all physically valid permutations of a given list of folios.
# Assumes "elems" is set to a string of letters that will be used to
# identify the folios.  Also assumes that folios 1,3,5,...
# are attached to folios 2,4,6,...
  
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); }
  if ((nf % 2) != 0) { error("elems must be even"); }
  
  split("", p); np = 0;
  split("", h); nh = 0;
  
  recurse();
}

function recurse(   i)
{
  # "f[0..nf-1]" are the folios of still unused bifolios,
  #   in consecutive pairs.
  # "p[0..np-1]" is the partial permutation built so far.
  # "h[0..nh-1]" are the unused folios whose partners have been used,
  #   from first to last.
  
  # printf "+ np = %d nf = %d nh = %d\n", np, nf, nh > "/dev/stderr"
  
  if (nf+nh == 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 folio in turn: 
      for (i=0; i<nf; i+=2)
        { # Place the even-numbered folio:
          p[np] = f[i]; np++; 
          h[nh] = f[i+1]; nh++;
          # Remove it from the free folio list
          nf--; f[i+1] = f[nf];
          nf--; f[i] = f[nf];
          recurse();
          # Now swap it with the corresponding odd-numbered folio:
          np--; nh--; 
          f[nf] = p[np]; p[np] = h[nh]; h[nh] = f[nf];
          np++; nh++;
          recurse();
          # Now return those two folios to the free bifolio bag:
          f[nf] = f[i]; nf++;
          f[nf] = f[i+1]; nf++;
          nh--; f[i] = h[nh]; 
          np--; f[i+1] = 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;
}