# Easier way to make permutation diagrams?

I prefer using figures created inside TeX, but I only know very labor-intensive methods. The following creates a permutation diagram for (6,3,2,4,1,5) with some colors and additional symbols.

I'm considering a project that would call for lots of these sorts of figures. Would it work to write a macro to create things like this? Any other advice for making this less painful?

$\begin{matrix}[cc|cccccc|c] & & & & & & {\color{blue}\downarrow} & {\color{blue}\downarrow} & S \\ \hline & 6 & {\color{red}\newmoon} & & & & & & {\color{red}\leftarrow} \\ {\color{blue}*} &5 & & & & & & {\color{blue}\newmoon} & \\ & 4 & & & & {\color{red}\newmoon} & & & {\color{red}\leftarrow} \\ & 3 & & {\color{red}\newmoon} & & & & & {\color{red}\leftarrow} \\ & 2 & & & \fullmoon & & & & \\ {\color{blue}*} & 1 & & & & & {\color{blue}\newmoon} & & \\ \hline & & 1 & 2 & 3 & 4 & 5 & 6 & \\ & & {\color{red}*} & {\color{red}*} & & {\color{red}*} & & & \end{matrix}$


-
The permutation diagram for (6,3,2,4,1,5) consists of the points (1,6), (2,3), (3,2), (4,4), (5,1), and (6,5). For purposes of this question, everything else is decoration (but decoration that I want to include). –  Brian Hopkins Apr 21 '13 at 0:29
And what are the rules of this decoration? (When blue/red/white, star/arrow?) –  Przemysław Scherwentke Apr 21 '13 at 0:45
Two players, red and blue, alternate selecting dots. Red moves down the right column, blue moves right to left across the top row (S is for "strategic"). The last move after the state shown will color the white dot blue, put an arrow above it on top, and an asterisk next to the 2 on the left. This illustrates an algorithm for dividing indivisible items between two players when both know the other's preferences. Blue's ranking of the six items is 1, 2, 3, 4, 5, 6, red's is 6, 3, 2, 4, 1, 5, thus the permutation diagram. More at "Taking Turns," College Math. J. 41(4) 2010 pp298-297. –  Brian Hopkins Apr 21 '13 at 1:10
Wow, thanks very much for all of the helpful answers. Although I can only accept one, I learned from all of them. –  Brian Hopkins Apr 21 '13 at 20:57

I was tempted to use a matrix of nodes but my solution borrows from Jake's awesome code in Chinese checkers board using TikZ which effectively sets up a matrix of nodes manually.

This solution needs the tikz and the xstring packages.

# The syntax

You use the code below as, for example

\drawpermutate{blue/{1/1,3/2}/left,red/{3/4,2/3}/right}


\drawpermutate{green/{1/1,3/5,4/2}/left,orange/{3/4,2/3}/right}


You'll notice that each part of the argument has three parts to it:

• colour: this should be self explanatory
• {list of coordinates}: note that this needs to be grouped in its own {}, and each ordered pair (x,y) needs to be written as x/y
• left or right: this can either be left or right depending on how you want the legend to be displayed. Actually, it can either be left or anything else- if it is not left, it'll go on the right (and underneath).

# The code

Here's a complete MWE that you can play with; the code is fairly detailed in its comments- it basically uses a few loops to set up the nodes, and then do the appropriate thing at each node (circle, arrow, or *).

% arara: pdflatex
% !arara: indent: {overwrite: true}
\documentclass{standalone}

\usepackage{tikz}
\usepackage{xstring}

\newcommand{\drawpermutate}[1]{%
\begin{tikzpicture}
% setup the nodes
\foreach [evaluate=\i as \x using int(\i-1)]\i in {0,1,...,8}
{
\foreach [evaluate=\j as \y using int(\j-1)] \j in {0,1,...,8}
{
%      \node at (\i,\j)[name=perm-\x-\y,label=\x-\y]{};
\node at (\i,\j)[name=perm-\x-\y,]{};
}
}

% draw numbers 1 to 6 in both x and y direction
\foreach \i in {1,...,6}
{
\node at (perm-\i-0.center){\i};
\node at (perm-0-\i.center){\i};
}
\node at (perm-7-7.center){$S$};

% vertical lines
\draw ([xshift=-5mm]perm-1--1.south west)--([xshift=-5mm]perm-1-7.north west);
\draw ([xshift=-5mm]perm-7--1.south west)--([xshift=-5mm]perm-7-7.north west);
% horizontal lines
\draw ([yshift=5mm]perm--1-0.south west)--([yshift=5mm]perm-7-0.south east);
\draw ([yshift=5mm]perm--1-6.south west)--([yshift=5mm]perm-7-6.south east);

% draw user input
\foreach \mystyle/\coords/\leftorright in {#1}
{
\foreach \x/\y in \coords
{
\node[circle,fill=\mystyle,draw=\mystyle] at (perm-\x-\y){};
\IfStrEq{\leftorright}{left}{%
\node[\mystyle] at (perm--1-\y){*};
\node[\mystyle] at (perm-\x-7){$\downarrow$};
}
{% otherwise put it on the right
\node[\mystyle] at (perm-7-\y){$\leftarrow$};
\node[\mystyle] at (perm-\x--1){*};
}
}

}

\end{tikzpicture}
}

\begin{document}

%\drawpermutate{blue/{1/1,3/5,4/2}/left,red/{3/4,2/3}/right}

\drawpermutate{green/{1/1,3/5,4/2}/left,orange/{3/4,2/3}/right}

\end{document}

-
Nice solution too! The possibility to choose where the decorations will go seems also to be a good decision. –  Gonzalo Medina Apr 21 '13 at 2:56

TikZ is not mandatory:-)

\documentclass{article}
\usepackage{color}
\makeatletter

\def\pdiag#1{{%
\setlength\unitlength{15pt}%
\begin{picture}(10,10)(-2,-2)%
\put(0,-2){\line(0,1){10}}%
\put(7,-2){\line(0,1){10}}%
\put(-2,-0){\line(1,0){10}}%
\put(-2,7){\line(1,0){10}}%
\put(7.2,7){S}%
\count@\z@
\@for\yc:=#1\do{%
\expandafter\ycdef\yc
\put(-1,\count@){\the\count@}%
\put(\count@,-1){\the\count@}%
\put(\count@,\y){\if r\c\color{red}\else\if b\c\color{blue}\fi\fi
\circle*{.3}}%
\if r\c
\put(\count@,-2){\color{red}$\ast$}%
\put(7,\y){\color{red}$\leftarrow$}%
\fi
\if b\c
\put(-2,\y){\color{blue}$\ast$}%
\put(\count@,7.1){\color{blue}$\downarrow$}%
\fi
}%
\end{picture}}}

\def\ycdef#1#2{\def\y{#1}\def\c{#2}}
\begin{document}

\pdiag{6r,3r,2x,4r,1b,5b}

\end{document}

-

With the Asymptote module permdiag.asy typesetting of this nice little permutation game can be completely automated. Processing of the following file permdiag-test.asy

import permdiag;
permDiag pd=permDiag(new int[]{6,3,2,4,1,5});

for(int i=1;i<=pd.n;++i){
shipout("diag"+format("%02d",i),pd.board(i));
}


with asy -f pdf permdiag-test.asy results in 6 files diag01.pdf..diag06.pdf, which were combined together with

\documentclass[a4paper]{article}
\usepackage{graphicx}
\begin{document}
\noindent%
\includegraphics[scale=1]{diag02.pdf}\\[10mm]
\noindent%
\includegraphics[scale=1]{diag05.pdf}
\end{document}


And this is the main permdiag.asy, which handles the permDiag class:

struct permDiag{
int n;
int[] perm;
int[] dotState;
int[][] tperm;

picture boardPic;
guide dotShape;
pen[] dotFill;

void drawNumbers(){
for(int i=0;i<n;++i){
label(boardPic,string(i+1),(i,-1));
label(boardPic,string(n-i),(-1,n-1-i));
}
}

void drawArrows(){
for(int i=0;i<n;++i){
if(dotState[i]>0){
if(dotState[i]==1){
label(boardPic,"$\leftarrow$",(n+0.5,tperm[i][0]-1));
}else{
label(boardPic,"$\downarrow$",(tperm[i][2]-1,n+0.5));
}
}
}
}

void drawStars(){
for(int i=0;i<n;++i){
if(dotState[i]>0){
if(dotState[i]==2){
label(boardPic,"*",(-2,tperm[i][0]-1));
}else{
label(boardPic,"*",(tperm[i][3]-1,-2));
}
}
}
}

void drawLines(){
draw(boardPic,(-2.5,-0.5)--(n+1.5,-0.5));
draw(boardPic,(-2.5,n-0.5)--(n+1.5,n-0.5));
draw(boardPic,(-0.5,-2.5)--(-0.5,n+1.5));
draw(boardPic,(n-0.5,-2.5)--(n-0.5,n+1.5));
}

void play(int hstep){
erase(boardPic);
int tmp;
int redblu=0;
for(int i=0;i<n;++i){
tperm[i][0]=perm[i];
tperm[i][4]=i+1;
}
dotState=array(n,0);
for(int i=0;i<hstep;++i){
for(int j=n-1;j>i;--j){
if(tperm[j][redblu]>tperm[j-1][redblu]){
tmp=tperm[j][redblu];
tperm[j][redblu]=tperm[j-1][redblu];
tperm[j-1][redblu]=tmp;
tmp=tperm[j][1-redblu];
tperm[j][1-redblu]=tperm[j-1][1-redblu];
tperm[j-1][1-redblu]=tmp;
}
}
dotState[i]=1+redblu;
redblu=1-redblu;
}
}

picture board(int move){
assert(move>=0 && move<=n);
//  move number, 0 = initial state,
//   odd - after red move
//  even - after blu move
play(move);
for(int i=0;i<n;++i){
filldraw(boardPic,shift(tperm[i][5]-1,tperm[i][0]-1)*dotShape,dotFill[dotState[i]]);
}
drawNumbers();
drawArrows();
drawStars();
drawLines();
label(boardPic,"$\mathcal{S}$",(n+0.5,n+0.5));
return boardPic;
}

void operator init(int[] perm){
assert(perm.length>0);
this.n=perm.length;
this.perm=copy(perm);
this.dotState=array(n,0);
this.dotShape=scale(0.382)*unitcircle;
this.dotFill=new pen[]{lightyellow,red,blue};
this.tperm=new int[n][6];
boardPic.size(20*n);
}
}

//// Example:
//
//  import permdiag;
//  permDiag pd=permDiag(new int[]{6,3,2,4,1,5});
//
//  for(int i=0;i<=pd.n;++i){
//    shipout("diag"+format("%02d",i),pd.board(i));
//  }
//


Edit: Fixed picture scaling for different values of n. Example permdiag-test2.asy:

import permdiag;
permDiag pda=permDiag(new int[]{3,1,2,4});
permDiag pdb=permDiag(new int[]{9,19,17,1,8,13,18,11,10,4,5,7,2,3,15,16,12,6,20,14});
int i;
i=3;
shipout("diag-"+format("n%d-",pda.n)+format("%02d",i),pda.board(i));
i=12;
shipout("diag-"+format("n%d-",pdb.n)+format("%02d",i),pdb.board(i));


processed with asy -f pdf permdiag-test2.asy results in two pictures, diag-n4-03.pdf and diag-n20-12.pdf:

-
This is above & beyond and very impressive. –  Brian Hopkins Apr 22 '13 at 2:18

Here's a macro for you, also based on TikZ:

\documentclass{article}

\usepackage{tikz,etoolbox}

\def\bluename{blue}
\def\redname{red}

%
\newcommand*\permdiagram[1]{%
% Loop for the first time over #1, printing the circles in
% the desired style.
\begin{tikzpicture}[x=1.5em,y=1.5em]
\foreach[count=\i from 1] \val/\hue in {#1} {
\ifdefequal{\val}{\hue}{
}{
}
}
% Now we know how many there are.  Loop again, printing the
% arrows and stars at the edges.
\let\count=\i
\foreach[count=\i from 1] \val/\hue in {#1} {
\ifdefequal{\val}{\hue}{}{
% Blue above and below, red at the left and right
\ifdefequal{\hue}{\bluename}{
\node at (\i,\count+1) {$\color{\bluename}\downarrow$};
\node at (-0.5,\val)     {$\color{\bluename}*$};
}{
\node at (\count+1,\val) {$\color{\redname}\leftarrow$};
\node at (\i,-0.5)         {$\color{\redname}*$};
}
}
}
% Finally, print the frame: the axis values, the lines, and "S"
\node at (\count+1,\count+1) {$S$};
\foreach \i in {1,...,\count} {
\node at (0,\i) {$\i$};
\node at (\i,0) {$\i$};
}
\draw[thick]
(-1,0.5) -- (\count+1.5,0.5)
(0.5,-1) -- (0.5,\count+1.5)
(-1,\count+0.5) -- (\count+1.5,\count+0.5)
(\count+0.5,-1) -- (\count+0.5,\count+1.5);
\end{tikzpicture}
}
\begin{document}

\permdiagram{6/red,3/red,2,4/red,1/blue,5/blue}

\end{document}


The macro \permdiagram takes one mandatory argument, which is a comma-separated list giving the values (in order) of your permutation, each of which is optionally separated by a slash from its color (which must be either blue or red, but these are configurable by changing \bluename or \redname). If there's no slash, an empty circle is drawn; otherwise, a solid circle of that color is drawn. You can configure the radii via \circlerad, and you can set the scale of the whole picture by editing the x=1.5em,y=1.5em option to {tikzpicture}.

I chose not to do this as a matrix because it is way too sparse, as I'm sure you noticed when asking the question. Instead, I just place the circles directly at the required coordinates, after which I know how many there are and I can draw the stuff on the boundary.

-
Ah, this is nice! My answer seems useless now. –  Gonzalo Medina Apr 21 '13 at 1:22

If you are asking if it possible to write something like

\permdiag(6,3,2,4,1,5)


and obtain a similar picture, the answer is YES. However, the addidtional rules are needed. In particular, I thought that red circles mean numbers moved up, blue -- moved down, white -- unchanged, but it is not true, because 3 not 4 is white. If these rules are easy in terms of comparing numbers, making such a macro is an exercise.

For example (this is only a sketch, without graphics and with some simple rules)

\documentclass[a4paper,11pt,leqno]{article}

\begin{document}

\newcount\pei
\newcount\peii
\newcount\peiii

\def\perm(#1,#2,#3){\pei#1 \peii#2 \peiii#3
\ifcase\pei\or100\or010\or001\fi\endgraf
\ifcase\peii\or200\or020\or002\fi\endgraf
\ifcase\peiii\or300\or030\or003\fi\endgraf
}

\perm(1,2,3)

\perm(3,1,2)
\end{document}


-
@Werner Thank you for editing a picture. How could I achieve such a cut? –  Przemysław Scherwentke Apr 21 '13 at 1:18
I recompiled the MWE, zoomed in on the important part, copy-and-pasted it using the regular "Insert image" interface (copy-and-paste have been made available since February 2013). See also How do you crop an attached PDF? –  Werner Apr 21 '13 at 1:29