Take the 2-minute tour ×
TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

I want to use LaTeX to print the permutation of a set {s,u,v,a,t}. The output looks like the following.

suvat
suvta
suavt
suatv
...

There are 120 rows in total that must be generated on the fly.

How to do this with LaTeX?

MWE:

\documentclass{article}
\begin{document}
.
\end{document}
share|improve this question
3  
@Papiro: don't give up with your dream, keep on sleeping! :-) –  Please don't touch May 7 '13 at 13:48
17  
+1 for the MWE! –  mafp May 7 '13 at 14:21
1  
Give me time to decide the accepted answer based on 2 items: (1) portability and (2) readability. –  Please don't touch May 7 '13 at 15:03
1  
@Bugbusters Do you really have to make such remarks about the code under each answer? –  kan May 7 '13 at 15:48
1  
I think the focus on "portability" is misguided. If you mistrust the machines you'll be TeXing this document on, then pre-generate the list of permutations and just \input it! In fact, TeX it in advance, where you control the environment. If you can't, write yourself a little program in some compiled language and carry it around with the document. I mean, I recently was generating numerical solutions to nonlinear ODEs using an external tool; if you were doing that, would you want to do it in TeX? It's possible (with pgf, say), but much harder. –  Ryan Reich May 7 '13 at 20:45

5 Answers 5

up vote 33 down vote accepted

Here's a better version, with lots of comments! Incidentally, the method of generating all permutations is based on the Knuth shuffle.

The latest version of the code avoids nested loops and the separator is a \par token every now and again to avoid building too large boxes (see discussion in comments). I ran it with abcdefghij and it worked, although the resulting document was 13746 pages long.

\documentclass{article}
%\url{http://tex.stackexchange.com/q/112975/86}
\usepackage{expl3}
\usepackage{xparse}

\ExplSyntaxOn

\tl_new:N \l__perm_all_tl
\int_new:N \l__perm_int
\int_new:N \l__perm_len_int

% Print the permutations of #2 with prefix #1
\cs_new_nopar:Npn \generate_perms:nn #1#2
{
  % We need to recursively call this function to build up the
  % final list.  This presents us with a dilemma.  Inside the
  % function we need to do some token list manipulations.  These
  % must not propagate upwards to the calling function.  One way
  % to avoid this is to have the function be within a group, but
  % that has two disadvantages: the simplest way leads to a lot of
  % nested groups, and if we want to store the result rather than
  % simply typeset it then the assignments have to be global.
  % So we choose an alternative way which is to ensure that any
  % temporary variables are used as soon as possible after
  % definition and never span a recursive call to the function.
  % This makes the function mildly inefficient in that we can't
  % store and reuse some calculations.
  %
  % How many terms do we need to permute?
  \int_set:Nn \l__perm_len_int {\tl_count:n {#2}}
  \int_compare:nTF {\l__perm_len_int <= 1}
  {
    % Only one, so nothing to do.
    % Add it to the stream with the separator in front.
    \l__perm_sep: #1#2
  }
  {
    % More than one, so need to do the permutations.
    % The method is based on the Knuth shuffle.
    % We need to generate all of the permutations.  We can do this
    % recursively by the following algorithm.  We cyclically permute
    % the token list.  For each cyclic permutation we freeze the first
    % term and then apply the permutation generation function to the
    % rest of the list.
    %
    % Thus if we start with abc we generate the cyclic permutations.
    % These are abc, bca, cab.
    % Then for each of these, we freeze the first term and apply the
    % function to the rest: so with abc we freeze the a and apply the
    % generation function to bc.  This will (by recursion) generate
    % bc and cb, whence appending the a again yields abc and acb.
    %
    % To avoid nesting loops, each iteration creates a token list of
    % what it would do and that list is then inserted into the stream.
    \tl_clear:N \l__perm_all_tl
    \tl_set:Nn \l_tmpb_tl {#2}
    % We "freeze" the first term, adding it to the current prefix.
    \tl_set:Nn \l_tmpa_tl {#1}
    \tl_put_right:Nx \l_tmpa_tl {\tl_head:N \l_tmpb_tl}
    % Now we add the first call to the recursive function to the
    % token list for this iteration.
    % This consists of a call to the function with arguments
    % the new prefix and the new tail.  We pass in the values so
    % that we can now use our temporary variables again with aplomb.
    \tl_put_right:Nn \l__perm_all_tl {\generate_perms:nn}
    \tl_put_right:Nx \l__perm_all_tl {{\exp_not:V \l_tmpa_tl}}
    \tl_put_right:Nx \l__perm_all_tl {{\tl_tail:N \l_tmpb_tl}}
    % Now we repeat the above but applying a cyclic permutation
    % to the main token list first
    \prg_replicate:nn {\l__perm_len_int - 1}
    {
      % This applies a cyclic permutation to the token list.
      \tl_set:Nx \l_tmpb_tl {\tl_tail:N \l_tmpb_tl {\tl_head:N \l_tmpb_tl}}
      % Then we add the function call to the token list.
      \tl_set:Nn \l_tmpa_tl {#1}
      \tl_put_right:Nx \l_tmpa_tl {\tl_head:N \l_tmpb_tl}
      \tl_put_right:Nn \l__perm_all_tl {\generate_perms:nn}
      \tl_put_right:Nx \l__perm_all_tl {{\exp_not:V \l_tmpa_tl}}
      \tl_put_right:Nx \l__perm_all_tl {{\tl_tail:N \l_tmpb_tl}}
    }
    % The token list now contains all the needed recursive calls
    % which we can now call. 
    \l__perm_all_tl
  }
}

\cs_generate_variant:Nn \generate_perms:nn {VV}

% The optional argument is the separator, the mandatory one is the
% token list to permute.
\DeclareDocumentCommand \permute { O{,~} m }
{
  % Set the separator
  \set_separator:n {#1}
  % Generate the permutation list
  \generate_perms:nn {} {#2}
}

% This sets the separator.  The first separator typesets nothing but
% sets all the subsequent separators.  Normally the separator inserts
% the optional argument from the user but every 120 terms it inserts
% a \par token instead to avoid overload. 
\cs_new_nopar:Npn \set_separator:n #1
{
  \int_zero:N \l__perm_int
  \cs_set:Npn \l__perm_sep:
  {
    \cs_set:Npn \l__perm_sep:
    {
      \int_incr:N \l__perm_int
      \int_compare:nTF {\l__perm_int == 120}
      {
        \par
        \int_zero:N \l__perm_int
      }
      {
        #1
      }
    }
  }
}

\ExplSyntaxOff

\parskip=1em plus 1ex minus .5ex

\begin{document}
\noindent\raggedright\permute{abcdefghi}
\end{document}

Permutations of abcde

share|improve this answer
2  
It is portable but the code looks too cryptic to me. :-) –  Please don't touch May 7 '13 at 15:03
1  
output would look a bit nicer using \noindent and \raggecright locally for the paragraph. –  barbara beeton May 7 '13 at 15:23
2  
@Bugbusters - you are asking too much. LaTeX is not a programming language, no matter how much it may pass for one sometimes. –  Leonardo Herrera May 7 '13 at 18:21
    
@barbarabeeton Quite right. I've updated it accordingly. –  Loop Space May 7 '13 at 19:04
1  
New revision avoids nested loops and adds a few \pars now and again. I've tried abcdefghij and it works. Will now attempt abcdefghijk to see if my laptop survives. –  Loop Space May 7 '13 at 20:15

run with lualatex

\documentclass{article}
\usepackage{luacode}
\begin{luacode*}
local function perm_generate(a, n)
  if n == 0 then
    coroutine.yield(a)
  else
    for i=1,n do          
      a[n], a[i] = a[i], a[n]  -- put i-th element as the last one
      -- generate all permutations of the other elements
      perm_generate(a, n - 1)
      a[n], a[i] = a[i], a[n]  -- restore i-th element
    end
  end
end
function permutation(a)
  local n = #a
  return coroutine.wrap(function () perm_generate(a, n) end)
end
function print_result (a)
  for i,v in ipairs(a) do tex.print(v .. " ") end
  tex.print(" ")
end
\end{luacode*}

\def\printPermutations#1{\directlua{%
  itable = {#1};
  for p in permutation(itable) do print_result(p) end }}

\begin{document}
\printPermutations{"a","b","c","d","e"}
\end{document}

enter image description here

share|improve this answer
    
It is readable but less portable. :-) –  Please don't touch May 7 '13 at 15:04
2  
@Bugbusters In contrast to the python solution it does not rely on external programs. IMO it's more portable, but I agree, it relies on a LuaTeX engine, though. –  Marco May 7 '13 at 16:46

Use the right tool for the job:

\documentclass{article}
\usepackage{python}

\begin{document}
\begin{python}
import itertools
for p in itertools.permutations("suvat"): print ''.join(p)
\end{python}
\end{document}

Run it with pdflatex -shell-escape.

share|improve this answer
    
cannot find latex2.py.out –  Please don't touch May 7 '13 at 15:00
    
@Bugbusters Did you run it with pdflatex -shell-escape latex2.tex? Oh, and of course you need python to be installed. –  mafp May 7 '13 at 15:05
1  
You get this error when you do not enable -shell-escape. Normally, you should get a file latex2.py containing the code, latex2.py.out containing the output, and latex2.py.err containing errors from python. –  mafp May 7 '13 at 15:14
2  
Small note: calling list is not needed: for p in itertools.permutations("suvat"): print ''.join(p) –  Bakuriu May 7 '13 at 15:32
1  
This could also be done with pythontex, if the calculations were ever slow enough that caching would be useful. –  G. Poore May 7 '13 at 17:19

The \permute macro is plain TeX, so it's very portable. Why don't you want it cryptic? It does the job, cryptically!

% New simplified code -- less cryptic than before :-)
\documentclass{article}
\def\recurse#1#2#3#4\endmarker{%
  \dopermute{#1#3}#2#4\endmarker
  \ifx\relax#4\relax\else % add a \par before \else if there are more than 8 items
    \recurse{#1}{#2#3}#4\endmarker
  \fi}
\def\dopermute#1#2#3\endmarker{%
  \ifx\relax#3\relax
    #1#2,
  \else
    \dopermute{#1#2}#3\endmarker
    \recurse{#1}{#2}#3\endmarker
  \fi}
\newcommand*\permute[1]{\dopermute{}#1\endmarker}
\begin{document}
\noindent\raggedright
\permute{12345}
\end{document}

output

Note that \permute is picky and wants to be fed single tokens, so \permute{12{34}} won't work, but \newcommand*\tf{34}\permute{12\tf} will. (Would you really want to permute such a thing?)

share|improve this answer
    
that's nice, but will run into memory problems for 9 and more items. –  Herbert May 7 '13 at 17:58
1  
@Herbert: Ah, right - I only tested up to 8, which already gave me 123 pages. For 9 items it would be more than a thousand pages! –  Hendrik Vogt May 7 '13 at 18:00
    
@Herbert: You get TeX capacity exceeded only because the paragraph becomes too large. If you use \pars, then it nicely works with 11 items, too. –  Hendrik Vogt May 8 '13 at 7:27
    
yes, that's true. Andrew already suggested it. –  Herbert May 8 '13 at 7:31
    
Just found a couple of edge cases: try permuting ab{cd} with yours and with mine; and try permuting ab\relax cd with yours! –  Loop Space May 8 '13 at 13:08

A simple LaTeX code, restricted to 5 characters only:

\documentclass[10pt,a4paper]{article}
\usepackage[english]{babel}
\usepackage{pgffor}
\def\defPerm|#1#2#3#4#5|{\lccode`\1`#1\lccode`\2`#2\lccode`\3`#3\lccode`\4`#4\lccode`\5`#5}
\def\typePerm#1#2#3#4#5{\char\the\lccode`#1\char\the\lccode`#2\char\the\lccode`#3\char\the\lccode`#4\char\the\lccode`#5}%
\def\permuteV#1{{\defPerm|#1|\def\tmp{\foreach\next in {%
12345,12354,12435,12453,12534,12543,13245,13254,13425,13452,13524,13542,
14235,14253,14325,14352,14523,14532,15234,15243,15324,15342,15423,15432,
21345,21354,21435,21453,21534,21543,23145,23154,23415,23451,23514,23541,
24135,24153,24315,24351,24513,24531,25134,25143,25314,25341,25413,25431,
31245,31254,31425,31452,31524,31542,32145,32154,32415,32451,32514,32541,
34125,34152,34215,34251,34512,34521,35124,35142,35214,35241,35412,35421,
41235,41253,41325,41352,41523,41532,42135,42153,42315,42351,42513,42531,
43125,43152,43215,43251,43512,43521,45123,45132,45213,45231,45312,45321,
51234,51243,51324,51342,51423,51432,52134,52143,52314,52341,52413,52431,
53124,53142,53214,53241,53412,53421,54123,54132,54213,54231,54312,54321}
{\expandafter\typePerm\next{} }}\tmp}}%
%
\begin{document}

\noindent\permuteV{suvat}

\noindent\permuteV{LaTeX}

\noindent\texttt{\permuteV{@1234}}

\end{document}

enter image description here

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.