permute.tex

% we use heap's algorithm to generate all permutations of a list - i love that algorithm honestly
% to avoid deep expansions for larger lists, i use the non-recursive variant
%
% well, i noticed too late that we only need permutations of size n and honestly it is getting later and
% later.... i tried fingerprinting but it does not work if a constraint appears multiple times...
%
% #1 the name of the list, please define '\chr@@output' to run on the list after each permutation
% this macro receives no arguments, but can read the same list you gave to permute!
% besides, it can use '\chr@list@coll' to get the collected list elements if necessary!
% #2 is the length of the permutations desired
\def\chr@permute#1#2{\begingroup% i fumbled here (historical reasons :D)
   \ifx\chr@@output\chr@undefined
      \chr@error{You have to define \string\chr@@output\space to run on the list after each permutation!}%
   \fi
   \let\chr@list@coll=\@empty
   \def\chr@permute@length{\csname #1length\endcsname}%
   \edef\chr@permute@output@length{#2}%
   \expandafter\chr@permute@generate\expandafter{\chr@permute@length}{#1}%
\endgroup}

% fingerprint the current state of the list with name in #1
% #2 is only executed if the fingerprint does not already exist
\def\chr@permute@fingerprint#1#2{%
   % TODO: make even single values unique! or just change the
   \chr@list@to@string\chr@list@coll{#1}{\chr@permute@output@length}%
   % \expandafter\let\expandafter\chr@permute@fingerprint@cmd\expandafter=\csname chr@permute@\chr@list@coll\endcsname
   %\ifx\chr@permute@fingerprint@cmd\relax
   %   \expandafter\let\csname chr@permute@\chr@list@coll\endcsname=\chr@ns\relax
      #2%
   %\else % we already have this fingerprint
   %   \chr@verbose{    Skip for fingerprint is present.}%
   %\fi
}

\def\chr@permute@init#1{%
   \chr@verbose{Initialize array C.}%
   \def\chr@tmp{0}
   \ifnum#1>1\relax
      \chr@tempcount=\z@
      \chr@step\chr@tempcount % we step early to skip the 0 :3
      \loop
         \chr@app\chr@tmp{,0}%
         \chr@step\chr@tempcount
         \ifnum\the\chr@tempcount<#1\relax
      \repeat
   \fi
   % c allows us to use expandafter more easily and is consistent with the pseudo-code
   \expandafter\chr@list\expandafter{\expandafter C\expandafter}\expandafter{\chr@tmp}
}
% #1: n of iterations, #2: list name
% as a slight modification we call \chr@@output for 'output'
\def\chr@permute@generate#1#2{\begingroup
   \chr@verbose{Generate all permutations of list #2 (length: #1).}%
   \ifnum#1=\z@
      \gdef\chr@return{}%
   \else
      % initialize new array - also known as the ""list""
      \chr@permute@init{#1}%
      \chr@permute@fingerprint{#2}{\chr@@output}%
      % tempcount will be our i
      \chr@tempcount=1\relax
      \let\chr@permute@done\chr@empty
      \loop
         \ifnum\the\chr@tempcount<#1\relax % essentially the head/while condition
            \edef\chr@c@i{\C{\the\chr@tempcount}} % number, we now we can edef C[i]
            \ifnum\chr@c@i<\the\chr@tempcount\relax
               \ifodd\the\chr@tempcount\relax% careful, we have to swap here, as tex presents \ifodd, but the default implementation uses "\ifeven"
                  \chr@list@swap{#2}{\chr@c@i}{\the\chr@tempcount}% swap(A[C[i]], A[i])
               \else
                  \chr@list@swap{#2}{0}{\the\chr@tempcount}% swap(A[0], A[i])
               \fi
               \chr@permute@fingerprint{#2}{\chr@@output}
               % without numexpr this is like... really painful
               \chr@tempcountb=\chr@c@i\relax
               \chr@step\chr@tempcountb
               \chr@list@eset C[\the\chr@tempcount]=\the\chr@tempcountb;% C[i] := C[i] + 1
               \chr@tempcount=1\relax % i := 1
            \else
               \chr@list@set C[\the\chr@tempcount]=0;% C[i] := 0
               \chr@step\chr@tempcount % i++
            \fi
         \else
            % while loop is done!
            \let\chr@permute@done=\chr@ns\relax
         \fi
         \ifx\chr@permute@done\chr@empty
      \repeat
   \fi
   \endgroup
}