4

Before I only used ifthenelse and for loops, but not complicated data structures. I don't know what is the convenient way to write longer codes.

As an example I would like to generate a random permutation of numbers from 0 to 9. This is not a complicated problem, but I do not know how to solve it easily. Are there any package which makes programming comfortable?

  • 7
    Hmmm... comfortable... subjective much? I think you also need to be very specific in terms of the question, which is currently somewhat vague, and show how you would solve this "[non-] complicated problem". – Werner Jan 23 '15 at 8:09
  • pgffor, etoolbox etc. A lot of packages exist actually for 'programming'. – user31729 Jan 23 '15 at 8:38
  • 2
    Pythontex and sagetex let you program in Python. – DJP Jan 23 '15 at 17:03
  • please, can you mention more? (pgffor, etoolbox, luacode, ... – user3058699 Jan 26 '15 at 20:54
13

With LuaTeX you can use the script language Lua:

\documentclass{article}
\usepackage{luacode}
\begin{luacode}
function permute(n)
  local tab = {}
  for i = 1, n do tab[i] = i end
  for i = 1, n do
    local j = math.random(i, n)
    tab[i], tab[j] = tab[j], tab[i]
  end
  for i = 1, n do
    tex.print("\\shortstack{"..i.."\\\\"..tostring(tab[i]).."} ")
  end
end
\end{luacode}

\begin{document}

\directlua{permute(20)}

\end{document}

enter image description here

  • LuaTeX is not a simple package, as I see. I need a package, not an engine, which has to be installed. – user3058699 Jan 26 '15 at 21:02
  • I need something like LuaTeX in which I do not need to use backslash before each command, and it is very general (with functions, structures, recursions, etc.) but I would like to use only a package, is it possible? – user3058699 Jan 26 '15 at 21:07
12

Here's an implementation of the Knuth shuffle algorithm with expl3.

\documentclass{article}
\usepackage{amsmath,xparse}
\input{random}

\ExplSyntaxOn

\cs_new_eq:NN \knuthshuffle_get_random:Nnn \setrannum

\tl_new:N \l_knuthshuffle_tempa_tl
\tl_new:N \l_knuthshuffle_tempb_tl
\int_new:N \l_knuthshuffle_random_int
\prop_new:N \l_knuthshuffle_newperm_prop
\prop_new:N \g_knuthshuffle_identity_prop % the identity
\seq_new:N \l_knuthshuffle_permutation_seq

\int_step_inline:nnnn { 1 } { 1 } { 100 }
 {
  \prop_gput:Nnn \g_knuthshuffle_identity_prop { #1 } { #1 }
 }


\NewDocumentCommand{\generatepermutation}{m}
 {
  \knuthshuffle_generate:n { #1 }
 }

\NewDocumentCommand{\printpermutation}{}
 {
  \left(
  \int_step_inline:nnnn { 1 } { 1 } { \seq_count:N \l_knuthshuffle_permutation_seq }
   {
    \begin{array}{c}
    ##1 \\ \seq_item:Nn \l_knuthshuffle_permutation_seq { ##1 }
    \end{array}
   }
  \right)
 }

\cs_new_protected:Nn \knuthshuffle_generate:n
 {
  \prop_set_eq:NN \l_knuthshuffle_newperm_prop \g_knuthshuffle_identity_prop
  \int_step_inline:nnnn { #1 } { -1 } { 2 }
   {
    \knuthshuffle_get_random:Nnn \l_knuthshuffle_random_int { 1 } { ##1 }
    \prop_get:NnN \l_knuthshuffle_newperm_prop { ##1 } \l_knuthshuffle_tempa_tl 
    \prop_get:NVN \l_knuthshuffle_newperm_prop \l_knuthshuffle_random_int \l_knuthshuffle_tempb_tl 
    \prop_put:NnV \l_knuthshuffle_newperm_prop { ##1 } \l_knuthshuffle_tempb_tl
    \prop_put:NVV \l_knuthshuffle_newperm_prop \l_knuthshuffle_random_int \l_knuthshuffle_tempa_tl
   }
  \seq_clear:N \l_knuthshuffle_permutation_seq
  \int_step_inline:nnnn { 1 } { 1 } { #1 }
   {
    \seq_put_right:Nx \l_knuthshuffle_permutation_seq
     {
      \prop_item:Nn \l_knuthshuffle_newperm_prop { ##1 }
     }
   }
  %\seq_show:N \l_knuthshuffle_permutation_seq % for debugging
 }
\ExplSyntaxOff


\begin{document}

\generatepermutation{20}

\[
\printpermutation
\]

\end{document}

The permutation is stored in a sequence, then it's up to you what to do with it. I added a \printpermutation macro just to show how to print the most recently generated permutation.

enter image description here

The tools I use are

  1. A fixed property list representing the identity permutation on the numbers from 1 to 1000

  2. A loop from the last place downward; at step k, a random number r between 1 and k is generated thanks to random.tex by D. Arsenau (let's hope it's integrated soon in expl3); the element at place k is swapped with the element at place r;

  3. Another loop loads a sequence with the so determined elements, for further processing.

The identity is defined up to 100, which should be a sufficient bound and keeps processing time down.


There is a faster way (which wastes more memory, though), using a \csname trick. The previous solution was in the spirit of showing the available tools with a toy problem, rather than looking for an efficient implementation.

\documentclass{article}
\usepackage{amsmath,xparse}
\input{random}

\ExplSyntaxOn

\cs_new_eq:NN \knuthshuffle_get_random:Nnn \setrannum

\tl_new:N \l_knuthshuffle_tempa_tl
\tl_new:N \l_knuthshuffle_tempb_tl
\int_new:N \l_knuthshuffle_random_int
\seq_new:N \l_knuthshuffle_permutation_seq

\NewDocumentCommand{\generatepermutation}{m}
 {
  \knuthshuffle_generate:n { #1 }
 }

\NewDocumentCommand{\printpermutation}{}
 {
  \left(
  \int_step_inline:nnnn { 1 } { 1 } { \seq_count:N \l_knuthshuffle_permutation_seq }
   {
    \begin{array}{c}
    ##1 \\ \seq_item:Nn \l_knuthshuffle_permutation_seq { ##1 }
    \end{array}
   }
  \right)
 }

\cs_new_protected:Nn \knuthshuffle_generate:n
 {
  \int_step_inline:nnnn { 1 } { 1 } { #1 }
   {
    \tl_clear_new:c { l_knuthshuffle_##1_element_tl }
    \tl_set:cn { l_knuthshuffle_##1_element_tl } { ##1 }
   }
  \prop_set_eq:NN \l_knuthshuffle_newperm_prop \g_knuthshuffle_identity_prop
  \int_step_inline:nnnn { #1 } { -1 } { 2 }
   {
    \knuthshuffle_get_random:Nnn \l_knuthshuffle_random_int { 1 } { ##1 }
    \tl_set_eq:Nc \l_knuthshuffle_tempa_tl
     { l_knuthshuffle_##1_element_tl }
    \tl_set_eq:Nc \l_knuthshuffle_tempb_tl
     { l_knuthshuffle_ \int_to_arabic:n \l_knuthshuffle_random_int _element_tl }
    \tl_set_eq:cN { l_knuthshuffle_##1_element_tl }
     \l_knuthshuffle_tempb_tl
    \tl_set_eq:cN { l_knuthshuffle_ \int_to_arabic:n \l_knuthshuffle_random_int _element_tl }
     \l_knuthshuffle_tempa_tl
   }
  \seq_clear:N \l_knuthshuffle_permutation_seq
  \int_step_inline:nnnn { 1 } { 1 } { #1 }
   {
    \seq_put_right:Nv \l_knuthshuffle_permutation_seq { l_knuthshuffle_##1_element_tl }
   }
%  \seq_show:N \l_knuthshuffle_permutation_seq % for debugging
 }
\ExplSyntaxOff

\begin{document}
\generatepermutation{20}

\[
\printpermutation
\]

\end{document}

The values are stored in an associative array using an array of token list variables, which makes addressing fast, at the expense of memory usage.

enter image description here


The same in Plain TeX:

\input random
\newcount\myrandom
\newcount\tempcount

\def\generatepermutation#1{%
  \def\lastlength{#1}%
  \tempcount=0
  \loop\ifnum\tempcount<#1\relax
    \advance\tempcount 1
    \expandafter\edef\csname shuffle\the\tempcount element\endcsname{\the\tempcount}%
  \repeat
  \loop\ifnum\tempcount>1
    \setrannum\myrandom{1}{\tempcount}
    \edef\tempa{\csname shuffle\the\tempcount element\endcsname}%
    \edef\tempb{\csname shuffle\the\myrandom element\endcsname}%
    \expandafter\edef\csname shuffle\the\tempcount element\endcsname{\tempb}%
    \expandafter\edef\csname shuffle\the\myrandom element\endcsname{\tempa}%
    \advance\tempcount -1
  \repeat
}

\long\def\gobble#1{}

\def\printpermutation{%
  \left(
  \def\tempa{\gobble}%
  \def\tempb{\gobble}%
  \tempcount=0
  \loop\ifnum\tempcount<\lastlength
    \advance\tempcount 1
    \edef\tempa{\tempa & \the\tempcount}%
    \edef\tempb{\tempb & \csname shuffle\the\tempcount element\endcsname}%
  \repeat
  \vcenter{\tabskip=3pt\halign{&\hfil##\hfil\cr\tempa\cr\tempb\cr}}
  \right)
}

\generatepermutation{20}

$$
\printpermutation
$$

\bye
  • 2
    Damn! I really need to get up to speed with expl3! – jub0bs Jan 23 '15 at 12:45
  • @Jubobs It's slow, of course; generating 100 random permutations on 100 numbers requires, on my machine, about 40 seconds. – egreg Jan 23 '15 at 12:54
  • @Jubobs If I decrease the size of the “identity property list” to 100, processing is much faster. – egreg Jan 23 '15 at 13:06
  • @egreg Probably a case where a 'classical' TeX array might help (still an open question in my mind about the 'back end' for property lists). – Joseph Wright Jan 23 '15 at 13:32
  • 1
    @Manuel \tl_set:NV has its uses if the variable is not a token list; it could be an integer variable, for instance, or a clist. – egreg Jan 23 '15 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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