16

How do I generate in LaTeX a list of random integers, in a given range, avoiding repetitions? The command \pgfmathrandomitem selects an item from a list, but when inserted in a loop can select twice the same item. Since I am selecting questions from a list in order to prepare an exam, I cannot ask twice the same question.

16

You can remove the item from the list after selecting it, then it won't be picked again:

enter image description here

\documentclass{article}
\usepackage{tikz}

\begin{document}
\makeatletter
\pgfmathsetseed{123321}



\def\prunelist#1{%
\expandafter\edef\csname pgfmath@randomlist@#1\endcsname
        {\the\numexpr\csname pgfmath@randomlist@#1\endcsname-1\relax}
\count@\pgfmath@randomtemp 
\loop
\expandafter\let
\csname pgfmath@randomlist@#1@\the\count@\expandafter\endcsname
\csname pgfmath@randomlist@#1@\the\numexpr\count@+1\relax\endcsname
\ifnum\count@<\csname pgfmath@randomlist@#1\endcsname\relax
\advance\count@\@ne
\repeat}

\pgfmathdeclarerandomlist{mylist}{{one}{two}{three}{four}{five}{six}{seven}}

\pgfmathrandomitem\z{mylist}\z\prunelist{mylist}


\pgfmathrandomitem\z{mylist}\z\prunelist{mylist}

\pgfmathrandomitem\z{mylist}\z\prunelist{mylist}

\pgfmathrandomitem\z{mylist}\z\prunelist{mylist}

\pgfmathrandomitem\z{mylist}\z\prunelist{mylist}

\pgfmathrandomitem\z{mylist}\z\prunelist{mylist}

\pgfmathrandomitem\z{mylist}\z\prunelist{mylist}



\end{document}

to declare an integer list:

\def\declarenumlist#1#2#3{%
\expandafter\edef\csname pgfmath@randomlist@#1\endcsname{#3}%
\count@\@ne
\loop
\expandafter\edef
\csname pgfmath@randomlist@#1@\the\count@\endcsname
  {\the\count@}
\ifnum\count@<#3\relax
\advance\count@\@ne
\repeat}

%\pgfmathdeclarerandomlist{mylist}{{one}{two}{three}{four}{five}{six}{seven}}


\declarenumlist{mylist}{1}{10}% list from 1 to 10 inclusive.
  • Very useful, it works fine. Now maybe a naive question, can I build the "mylist" of consecutive integer numbers in an easy way? – Fedele Lizzi Apr 19 '13 at 18:49
  • @FedeleLizzi added code for 1..10 to the answer – David Carlisle Apr 19 '13 at 19:03
  • @DavidCarlisle That's works very well. I have two questions. 1) if one uses the command \pgfmathrandomitem more times than the elements in List, then the result is just the last element of List. Is there a way to put a control which sends an error messages in the case the list is empty? – user126154 Jan 30 '15 at 16:52
  • @DavidCarlisle my second question is: ok, that's very nice, but I would like to learn to use the tools you used. I searched and I found a huge user guide of pgf which appears to be a graphic tools package. Where can I learn just to use the command useful for "macros" like those used in the present case? Thank you for help! – user126154 Jan 30 '15 at 16:56
  • 1
    @user126154 dont ask questions in old comments:-) \@roman\count@ (it's a primitive count register so you need the lower level form) – David Carlisle Jan 30 '15 at 17:43
6

This code for generating random numbers from 1 to N without repetitions should run faster than the one based on pgfmath. Speed gain can not be felt here because the numbers are extracted one by one, but if one wanted to generate in one-go a full random permutation, for later use, then this code could be extended to do it and the difference with the pgfmath+\prune should show up when dealing with N more than a few hundreds. (untested ;-) ).

Edit: code added to generate in one-go a complete random permutation of the integers from 1..N. Contrarily to \NewRandom which each time "prunes" the list by one, \NewPermutation leaves the list intact in order to allow iterated uses.

Last Edit: added \DeclareList as a companion to \DeclareIntegerList, but now for lists of arbitrary things. Renamed \NewPermutation to \Permutation and rewrote the code which does not re-use anymore pieces of \NewRandom with its accompanying overhead.

\documentclass{article}
\usepackage[vscale=0.9,hscale=0.75]{geometry}

% \DeclareIntegerList {name}{N}
% declares the list of the integers from 1 to N 
% under name "name" for future use of either
% \NewRandom<macro>\FromList {name}, 
% or \Permutation<macro>\OfList{name}

% \DeclareList {name}{{first}{second}...{last}}
% declares similarly a list of things, possibly containing empty lines or
% `\par`. Second argument may be macro. Items must be braced (or single tokens
% but the first one will be expanded if not protected by braces)

% \NewRandom\z \FromList {name}

% makes \z expand to a randomly chosen element in what remains of list
% "name", and removes the chosen element from the list "name"

% \Permutation\R \OfList {name}

% makes \R expand to the token list of the braced elements of list
% "name", in a random order. The list is not modified.

\makeatletter

\newtoks\rndperm@tok
\newcount\rndperm@cnta
\newcount\rndperm@cntb

% auxiliary macros \rndperm@tmpa, \rndperm@tmpb, \rndperm@aux

\newcommand{\DeclareIntegerList}[2]{%
% sets up a the integers from 1 to N as a list for random extraction
    \rndperm@cnta #2\relax
    \rndperm@cntb \rndperm@cnta
    \rndperm@tok {}%
    \loop
    \rndperm@tok 
             \expandafter\expandafter\expandafter{%
             \expandafter\the\expandafter\rndperm@tok
             \csname \the\rndperm@cntb\expandafter\endcsname 
                   \expandafter{\the\rndperm@cntb}}%
    \ifnum\rndperm@cntb>\@ne
       \advance\rndperm@cntb\m@ne
    \repeat
    \expandafter\def\csname rndperm@list@#1\expandafter\endcsname
    \expandafter{\the\rndperm@tok }%
    \expandafter\def\csname rndperm@card@#1\expandafter\endcsname
    \expandafter{\the\rndperm@cnta }%
}%

\newcommand{\NumberOfItems}[1]{\csname rndperm@card@#1\endcsname }

\newcommand{\DeclareList}[2]{%
    \rndperm@cnta \z@
    \rndperm@tok {}%
    \expandafter\rndperm@scanlist \romannumeral-`0#2\rndperm@bye
    \long\expandafter\def\csname rndperm@list@#1\expandafter\endcsname
         \expandafter{\the\rndperm@tok }%
    \expandafter\def\csname rndperm@card@#1\expandafter\endcsname
                \expandafter{\the\rndperm@cnta }%
}%

\long\def\rndperm@bye #1\rndperm@bye {}%
\def\rndperm@endscan #1\rndperm@scanlist {}%

\long\def\rndperm@scanlist #1{%
     \rndperm@bye #1\rndperm@endscan\rndperm@bye
     \advance\rndperm@cnta\@ne
     \long\expandafter\def\expandafter\rndperm@tmpa\expandafter
          {\csname\the\rndperm@cnta\endcsname {#1}}%
     \rndperm@tok\expandafter\expandafter\expandafter
                {\expandafter\rndperm@tmpa\the\rndperm@tok }%
     \rndperm@scanlist
}%


\def\NewRandom #1\FromList #2{%
    \rndperm@cnta \csname rndperm@card@#2\endcsname\relax
    \ifnum\rndperm@cnta=\z@\rndperm@abort #1\fi
    \expandafter\let\expandafter\rndperm@list\csname rndperm@list@#2\endcsname
    \rndperm@cntb\pdfuniformdeviate\rndperm@cnta\relax
    \advance\rndperm@cnta\m@ne
    \ifnum\rndperm@cntb=\rndperm@cnta
            \expandafter\rndperm@firstone
       \else
            \expandafter\rndperm@fartherup
    \fi
    \expandafter\def\csname rndperm@card@#2\expandafter\endcsname 
                \expandafter{\the\rndperm@cnta}%
    \long\expandafter\def\expandafter#1\expandafter{\rndperm@element}%
    \expandafter\let\csname rndperm@list@#2\endcsname\rndperm@list
     \empty
}%

\def\rndperm@abort #1\fi #2\empty{\fi \let#1\empty}

\def\rndperm@firstone {\expandafter\rndperm@firstone@a \rndperm@list!}%

\long\def\rndperm@firstone@a #1#2#3!{%
     \long\def\rndperm@element {#2}%
     \long\def\rndperm@list {#3}}

\def\rndperm@fartherup {%
    \expandafter\def\expandafter\rndperm@tmpa
                \expandafter{\csname\the\numexpr\rndperm@cntb+1\endcsname }%
    \rndperm@tok {\long\def\rndperm@aux ##1##2##3}%
    \expandafter\the\expandafter\rndperm@tok\rndperm@tmpa ##4##5!%
       {\long\expandafter\def
        \expandafter\rndperm@tmpa\expandafter{\rndperm@tmpa {##2}##5}%
        \long\def\rndperm@tmpb {##3}%
        \expandafter\expandafter\expandafter\def
        \expandafter\expandafter\expandafter\rndperm@list
        \expandafter\expandafter\expandafter
                    {\expandafter\rndperm@tmpb\rndperm@tmpa }%
        \long\def\rndperm@element {##4}}%
     \expandafter\rndperm@aux \rndperm@list!%
}%

\def\Permutation #1\OfList #2{%
    \rndperm@cnta \csname rndperm@card@#2\endcsname\relax
    \let\rndperm@perm\empty
    \ifnum\rndperm@cnta>\z@ 
            \expandafter\expandafter\expandafter
            \rndperm@all\csname rndperm@list@#2\endcsname
    \fi
    \let#1\rndperm@perm
}%

\def\rndperm@all {%
    \rndperm@cntb\pdfuniformdeviate\rndperm@cnta\relax
    \advance\rndperm@cnta\m@ne
    \ifnum\rndperm@cntb=\rndperm@cnta
            \expandafter\rndperm@all@firstone
       \else
            \expandafter\rndperm@all@fartherup
    \fi
}%

\long\def\rndperm@all@firstone #1#2{%
    \long\expandafter\def\expandafter\rndperm@perm\expandafter
                               {\rndperm@perm {#2}}%
    \ifnum\rndperm@cnta>\z@ \expandafter\rndperm@all\fi 
}%

\def\rndperm@all@fartherup {%
    \expandafter\def\expandafter\rndperm@tmpa
                \expandafter{\csname\the\numexpr\rndperm@cntb+1\endcsname }%
    \rndperm@tok {\long\def\rndperm@aux ##1##2##3}%
    \expandafter\the\expandafter\rndperm@tok\rndperm@tmpa ##4%
       {\long\expandafter\def\expandafter\rndperm@perm\expandafter
                               {\rndperm@perm {##4}}%
        \long\expandafter\def\expandafter\rndperm@tmpa
                        \expandafter{\rndperm@tmpa {##2}}%
        \long\def\rndperm@tmpb {##3}%
        \expandafter\expandafter\expandafter\rndperm@all
        \expandafter\rndperm@tmpb\rndperm@tmpa 
       }%
     \rndperm@aux 
}%

\makeatother

\begin{document}
\begin{verbatim}
\DeclareIntegerList {mylist}{10}
\count 255 1
\loop
   \NewRandom\z\FromList {mylist}\z 
\ifnum\count 255 < 15 \advance\count 255 by 1 ,
\repeat 
\end{verbatim}

\DeclareIntegerList {mylist}{10}
\count 255 1
\loop
   \NewRandom\z\FromList {mylist}\z 
\ifnum\count 255 < 15 \advance\count 255 by 1 ,
\repeat (macro is set to empty when the list is exhausted)

\begin{verbatim}
\DeclareList {words}{{Unpounced}{epimetheus}{angelhood}{diopside}% (percent optional)
                      {gospeler}{quiff}{eutrophy}}
\count 255 1
{\bfseries\loop
   \NewRandom\z\FromList {words}\z 
\ifnum\count 255 < 7 \advance\count 255 by 1 ,
\repeat } 
\end{verbatim}

\DeclareList {words}{{Unpounced}{epimetheus}{angelhood}{diopside}%
                      {gospeler}{quiff}{eutrophy}}
\count 255 1
{\bfseries\loop
   \NewRandom\z\FromList {words}\z 
\ifnum\count 255 < 7 \advance\count 255 by 1 ,
\repeat }

At this stage \texttt{words} has no more elements, it is emptied.


% \verb|\Permutation\S\OfList {mylist}| sets \texttt{\string\S} to the empty macro
% (meaning of \texttt{\string\S} is \Permutation\S\OfList
% {mylist}\texttt{\meaning\S}).

\begin{verbatim}
\def\x #1{\ifx \relax #1\else \{#1\}\hskip 0pt plus 1pt minus 1pt
                       \expandafter\x \fi }
\DeclareList {words}{{Unpounced}{epimetheus}{angelhood}{diopside}%
                     {gospeler}{quiff}{eutrophy}}
\Permutation\S\OfList {words}\texttt{\string\S\ is \expandafter\x\S\relax}\endgraf
\end{verbatim}

\def\x #1{\ifx \relax #1\else \{#1\}\hskip 0pt plus 1pt minus 1pt
                       \expandafter\x \fi }
\DeclareList {words}{{Unpounced}{epimetheus}{angelhood}{diopside}%
                     {gospeler}{quiff}{eutrophy}}
\noindent
\Permutation\S\OfList {words}\texttt{\string\S\ is \expandafter\x\S\relax}\endgraf
\noindent\Permutation\S\OfList {words}\texttt{\string\S\ is \expandafter\x\S\relax}\endgraf
\noindent\Permutation\S\OfList {words}\texttt{\string\S\ is \expandafter\x\S\relax}\endgraf
\noindent\Permutation\S\OfList {words}\texttt{\string\S\ is \expandafter\x\S\relax}\endgraf

\medskip
We can declare lists of arbitrary contents
\begin{verbatim}
\DeclareList {tokens}{{\if}{{\ifnum}}{\ifdim}{\par}{\end}{\fi}{{\fi\fi}}{\gobbleall}}%
There are \NumberOfItems {tokens} elements in this list.\endgraf
\noindent\Permutation\S\OfList {tokens}\noindent\texttt{\meaning\S}\endgraf
\noindent\Permutation\S\OfList {tokens}\noindent\texttt{\meaning\S}\endgraf
\noindent\Permutation\S\OfList {tokens}\noindent\texttt{\meaning\S}\endgraf
\noindent\Permutation\S\OfList {tokens}\noindent\texttt{\meaning\S}\endgraf
\end{verbatim}

\DeclareList {tokens}{{\if}{{\ifnum}}{\ifdim}{\par}{\end}{\fi}{{\fi\fi}}{\gobbleall}}
There are \NumberOfItems {tokens} elements in this list.\endgraf
\noindent\Permutation\S\OfList {tokens}\texttt{\meaning\S}\endgraf
\noindent\Permutation\S\OfList {tokens}\texttt{\meaning\S}\endgraf
\noindent\Permutation\S\OfList {tokens}\texttt{\meaning\S}\endgraf
\noindent\Permutation\S\OfList {tokens}\texttt{\meaning\S}\endgraf

\begin{verbatim}
\DeclareIntegerList {mylist}{200}
\texttt{mylist} has \NumberOfItems {mylist} elements and a random element is
\NewRandom\z \FromList {mylist}\texttt{\z}. There are now only \NumberOfItems
{mylist} elements left. Here they are in random order:
\Permutation\S\OfList {mylist}%
\texttt{\expandafter\x\S\relax}
\end{verbatim}

\DeclareIntegerList {mylist}{200}
\texttt{mylist} has \NumberOfItems {mylist} elements and a random element is
\NewRandom\z \FromList {mylist}\texttt{\z}. There are now only \NumberOfItems
{mylist} elements left. Here they are in random order:
\Permutation\S\OfList {mylist}%
\texttt{\expandafter\x\S\relax}

\end{document}
\medskip
Extracting 200 times with no repetitions
after \verb|\DeclareIntegerList {mylist}{200}|:

\DeclareIntegerList {mylist}{200}\count 255 1
\begin{verbatim}
\count255 0
\loop
   \NewRandom\z\FromList {mylist}\z
\ifnum\count 255 < 200 \advance\count 255 1 ,
\repeat
\end{verbatim}
\count255 0
\loop
   \NewRandom\z\FromList {mylist}\z
\ifnum\count 255 < 200
\advance\count 255 1
,
\repeat

\medskip
Now with  
\begin{verbatim}
\DeclareIntegerList {mylist}{200}
\Permutation\S\OfList {mylist}
\end{verbatim}
\DeclareIntegerList {mylist}{200}
\Permutation\S\OfList {mylist}

Here are the contents of \texttt{\string\S}:
\def\x #1{\ifx \relax #1\else \{#1\}\hskip 0pt plus 1pt minus 1pt
                       \expandafter\x \fi }
\texttt{\expandafter\x\S\relax}

And \verb|\Permutation| can be used again and again to generate more random
permutations (not necessarily distinct).
% Tools of \verb|xint| such as \verb|\xintApplyUnbraced| or \verb|\xintFor*| can
% help if one wants to do things with the generated list of braced things.
\end{document}

randomIII

  • Did you use fisher-yates algorithm? – kiss my armpit Nov 14 '13 at 22:03
  • 1
    @DonutE.Knot I just had a look at wikipedia to learn what is Fisher-Yates, there is some ressemblance. I focused on efficiency of TeX expansion. We start from \N{N}...\3 {3}\2{2}\1{1}. At any given time when there are M left, the stuff will be \M{K}\M-1{L}\M-2{P}...\2{Y}\1{Z}. Use \pdfuniformdeviate to generate a random k. If k=M, then random is K and just remove the first two things. If k<M, random is what follows \k. Remove the \M and move what is next to after \k. This is all efficient with delimited macros. And then repeat for the next asked for random element. – user4686 Nov 14 '13 at 22:14
  • 1
    with N very big, one would gain some speed if also the {numbers} were single token, like \c1, \c2, ... to distinguish them from the markers \1, \2, ... But one will have to unpack after extraction. I have not thought about it. I am quite certain that the code above is faster than the pgfmath+\prune because all the \edef's are avoided (edit: and the \let all the way to the tail of the list). But this can only reveal itself in macro which would generate the full complete permutation. – user4686 Nov 14 '13 at 22:27
  • 1
    Thanks, the new algorithm seems more efficient and I will use it. However, I hope that the number of students in my classes remains below "a few hundred":) – Fedele Lizzi Nov 15 '13 at 10:23
  • At present numbers are enough, but in the future I might have a list directly with the questions, so if is not much trouble the more general version might turn to be useful. – Fedele Lizzi Nov 15 '13 at 16:41
3

Some time ago we found this code on the internet:

\input random

\newcount\icount
\newcount\i
\newcount\j

% Define a new item.
\def\defitem{%
  \advance\icount by1
  % Define a macro with the name `n' where n is the item's number.
  \expandafter\def \csname \number\icount \endcsname
}
% Printing of items.
\def\printitem#1{\csname \number#1\endcsname}
\let\printbetweenitems\space
% Print all defined items in random order.
\def\getitems{%
  % Unset all flags.
  \i=\icount
  \loop
    \expandafter\let \csname flag\number\i \endcsname a%
    \advance\i by-1
    \ifnum\i > 0 \repeat
  % Print random items, each item once, until every item has been
  % printed.
  \i=\icount
  \loop
    % Get random number \j.
    \setrannum{\j}{1}{\icount}%
    % Print item \j only if its flag is unset.
    \expandafter\ifx \csname flag\number\j \endcsname a%
      \expandafter\let \csname flag\number\j \endcsname b% Set the flag.
      \printitem\j
      \advance\i by-1
      \ifnum\i > 0 \printbetweenitems\fi
    \fi
    \ifnum\i > 0 \repeat
}


\defitem{1}
\defitem{2}
\defitem{3}
\defitem{4}
\defitem{5}
\defitem{6}
\defitem{7}
\defitem{8}
\defitem{9}
\defitem{10}
\defitem{11}

\getitems\par \getitems\par \getitems\par \getitems\par
\getitems\par

\bye

We have adapted it to create a command which chooses randomly m objects in a set of n of them (m <= n).

You can have a look to the esami.sty file at this link https://www.dropbox.com/sh/0t92kehukgafni5/0Mi0qsYLlR

  • 1
    I'd recommend that you either prepare the style file to be uploaded to CTAN and then link there, or paste the style file here in its entirety. As it stands, the link is pronto breaking. – Sean Allred Apr 19 '13 at 15:48

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.