How to measure the optimality of word or gesture order with respect to the principle of swap distance minimization

Ramon Ferrer-i-Cancho

cs.CLApr 2, 2026

How to measure the optimality of word or gesture order with respect to the principle of swap distance minimization

Authors: Ramon Ferrer-i-Cancho

Organizations: Quantitative, Mathematical and Computational Linguistics Research Group (LQMC), Departament de Ciències de la Computació, Universitat Politècnica de Catalunya, Campus Nord, Edifici Omega, Jordi Girona Salgado 1-3, 08034 Barcelona, Catalonia, Spain

Abstract

The structure of all the permutations of a sequence can be represented as a permutohedron, a graph where vertices are permutations and two vertices are linked if a swap of adjacent elements in the permutation of one of the vertices produces the permutation of the other vertex. It has been hypothesized that word orders in languages minimize the swap distance in the permutohedron: given a source order, word orders that are closer in the permutohedron should be less costly and thus more likely. Here we explain how to measure the degree of optimality of word order variation with respect to swap distance minimization. We illustrate the power of our novel mathematical framework by examining spontaneous gestures produced by speakers from four languages (two SVO languages and two VSO languages, which represent two linguistic families). We show that crosslinguistic gestures are at least $77\%$ optimal. It is unlikely that the multiple times where crosslinguistic gestures hit optimality are due to chance. We establish the theoretical foundations for research on the optimality of word or gesture order with respect to swap distance minimization in communication systems. Finally, we introduce the quadratic assignment problem (QAP) into language research as an umbrella for multiple optimization problems and, accordingly, postulate a general principle of optimal assignment that unifies various linguistic principles including swap distance minimization.

Figures & tables

Figure 1: The permutohedron of order 3. Vertices are labeled with all the possible permutations of SOV.

Figure 2: Hasse diagrams (blue arrows) of four total orders of vertices of the permutohedron. Every Hasse diagram describes an arrangement of probabilities on the permutohedron. Vertices are labeled with numbers from 1 to 6 in clockwise sense starting from the left-most vertex. Near each vertex, we show the probability of the vertex.

\pi_{i}

stands for the

i

-th largest probability. A blue arrow from vertex

i

to vertex

j

indicates that

p_{i}\geq p_{j}

. Black lines indicate edges of the permutohedron (only edges that are not hidden by a blue arrow are visible). (a) A Hasse diagram that minimizes

\left<d\right>

and

\left<d|1\right>

. (b) A symmetric Hasse diagram that also minimizes

\left<d\right>

and

\left<d|1\right>

. (c) A Hasse diagram that minimizes

\left<d|1\right>

but not

\left<d\right>

. (d) A symmetric Hasse diagram that also minimizes

\left<d|1\right>

but not

\left<d\right>

Figure 3: (a) The frequency of the six possible orders of S, O and V produced by speakers of Tagalog in unconventional gesturing experiments under the non-reversible condition [ 14 ] . (b) An optimal assignment of the frequencies in (a).

Figure 4: Probability assigments to vertices of the permutohedron. Black numbers indicate vertex labels while red numbers indicate probabilities. (a) A probability assignment to vertices of the permutohedron without probability ties. (b) A probability assignment to vertices of the permutohedron with probability ties. (c) The directed graph (blue arcs) of the vertex relation induced by the probability assignment in (a). A blue arrow from vertex

i

to vertex

j

indicates that

p_{i}\geq p_{j}

. Black lines indicate edges of the permutohedron (only edges that are not hidden by a blue arrow are visible). (d) The Hasse diagram of the previous directed graph following the same conventions as in (c).

Figure 5: The total preorder of vertices of the permutohedron (blue arrows) induced by the minimization of

\left<d|1\right>

. Vertices are labeled with numbers from

1

6

in a clockwise sense. A blue arrow from vertex

i

to vertex

j

indicates that

p_{i}\geq p_{j}

. Black lines indicate edges of the permutohedron (only edges that are not hidden by a blue arrow are visible). (a) The total preorder as a directed graph. Self-edges resulting from reflexivity are omitted for simplicity. (b) A Hasse diagram of the previous graph. As the directed graph that defines the total preorder has cycles, the transitive reduction may not be unique [ 28 ] , and then we show only one of the Hasse diagrams (Appendix C ).

Figure 6: Arrangements with four non-zero probability orders (vertices with non-zero probability are marked in red). (a) The non-zero probability orders are contiguous, namely they form a path. (b) The non-zero probability orders are not contiguous.

	$T(m)$
$m$	non-reversible	reversible	any
1	0	0	0
2	0	0	0
3	1	1	2
4	2	3	5
5	1	0	1

Table 1: The distribution of

m

, the number of non-zero probability orders in each ensemble (non-reversible, reversible or any).

T(m)

is the number of

m

non-zero probability orders in members of an ensemble.

Figure 7: The average swap distance (

\left<d\right>

) as a function of the random baseline (

\left<d\right>_{r}

) in crosslinguistic gestures. The dashed line is a control line to indicate identity, i.e.

\left<d\right>=\left<d\right>_{r}

. Points below the control line satisfy

\left<d\right><\left<d\right>_{r}

. Color point indicates the language of the participants. Point shape indicates the reversibility condition.

Reversibility	Language	$F$	$m$	$\bar{S}$	$\pi_{o}$	$p_{o}(m)$	$\left<d\right>_{min}$	$\left<d\right>$	$\left<d\right>_{r}$	$\left<d\right>_{max}$	$\Omega$
reversible	English	121	4	0.37	0.033	0.033	0.41	0.47	0.67	1.5	0.78
	Russian	103	3	0.57	0.1	0.1	0.64	0.7	1.02	1.5	0.85
	Irish	82	4	0.54	0.033	0.033	0.62	0.62	0.97	1.5	1
	Tagalog	82	4	0.61	0.033	0.033	0.74	0.74	1.1	1.5	1
non-reversible	English	119	4	0.6	0.033	0.033	0.71	0.74	1.08	1.5	0.91
	Russian	117	3	0.54	0.1	0.1	0.59	0.59	0.97	1.5	1

Table 2: Summary of the statistical information by reversibility condition and participant’s language:

F

(the total frequency),

m

(the number of non-zero probability orders),

\bar{S}

(the dominance index),

\pi_{o}

(the probability that a random permutation is optimal),

p_{o}(m)

(the probability that a random permutation is optimal assuming no probability ties among the

m

non-zero probability orders),

\left<d\right>_{min}

(the minimum value of

\left<d\right>

over all permutations),

\left<d\right>

(the average swap distance),

\left<d\right>_{r}

(the expected value of

\left<d\right>

in a random permutation),

\left<d\right>_{max}

(the maximum value of

\left<d\right>

) and

\Omega

(the optimality of

\left<d\right>

Figure 8: The distribution of gesture orders in each combination of language and reversibility condition. Languages are sorted by dominant order: SVO on the left (English and Russian) and VSO on the right (Irish and Tagalog).

Figure 9: The Hasse diagram of induced from acceptability ratings in Malayalam (blue) on the permutohedron (black). A blue arrow from vertex

i

to vertex

j

indicates that

p_{i}\geq p_{j}

where

p_{i}

is the acceptability rating of vertex

i

. The acceptability rating each order is shown near each vertex.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 10:

\Omega_{min}

, a tight lower bound of

\Omega

, when

m

, the number of non-zero probability orders, is

2

Figure 11: $\Omega_{min}$ ( Eq. A21 ) as a function of $\pi_{1}$ and $\pi_{2}$ . Red circles are used to indicate the corners of the triangle at $(1/3,1/3)$ , $(1/2,1/2)$ and $(1,0)$ . Within the triangle, $\Omega_{min}$ was calculated by scanning exhaustively with a step of $10^{-3}$ for both variables.

Figure 12: The permutohedron of order 3. Vertices are labeled with consecutive numbers in a clockwise sense.

$m$	$p_{o}(m)$	$p_{c}(m)$
1	$1$	$1$
2	$2/5$	$2/5$
3	$1/10$	$3/10$
4	$1/30$	$2/5$
5	$1/60$	$1$
6	$1/60$	$1$

Appendix

Table 3:

p_{o}(m)

, the probability that random arrangement is optimal assuming that there are no probability ties among the

m

non-zero probability orders ( Eq. 16 ), and

p_{c}(m)

, the probability that a random arrangement is contiguous when the number non-zero probability orders is

m

( Eq. A39 ).

Figure 13: Distinct ways of arranging

m

non-zero probability orders on the permutohedron (

m=3

on the left and

m=4

on the right). The orders with non-zero probability are marked in red. (a) A contiguous arrangement where the multiset of swap distances is

\{1,1,2\}

. (b) A contiguous arrangement where the multiset of swap distances is

\{1,1,1,2,2,3\}

. (c) A non-contiguous arrangement where the multiset of swap distances is

\{1,2,3\}

. (d) A non-contiguous arrangement where the multiset of swap distances is

\{1,1,2,2,2,3\}

. (e) A non-contiguous arrangement where the multiset of swap distances is

\{2,2,2\}

. (f) Another non-contiguous arrangement where the multiset of swap distances is

\{1,1,2,2,3,3\}

Combinatorial Optimization

Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.

See all 382 papers

Swap distance minimization shapes the order of subject, object and verb in languages of the world
Apr 29, 2026Jairo Rios-El-Yazidi, Ramon Ferrer-i-CanchoLinguistic Typology
Quantitative, Mathematical and Computational Linguistics Research Group, Department of Computer Science, Universitat Polit`ecnica de Catalunya, 08034 Barcelona, Catalonia (Spain)
Vocabulary shapes cross-lingual variation of word-order learnability in language models
Mar 19, 2026Jonas Mayer Martins, Jaap Jumelet, Viola Priesemann +1Linguistic Typology
University of Göttingen, Germany · University of Groningen, Netherlands · MPI for Dynamics and Self-Organization, Germany
Left-Branching Transformers Excel at Right-Branching Languages: Data Shapes Word Order Preferences in Language Models
Aug 15, 2026Varvara Arzt, Allan Hanbury, Terra BlevinsMultilingual Language Models Decoder-Only Language Models
Faculty of Informatics, TU Wien · Khoury College of Computer Sciences, Northeastern University

Apr 29, 2026J/K move · Enter open · S save

Swap distance minimization shapes the order of subject, object and verb in languages of the world

Jairo Rios-El-Yazidi, Ramon Ferrer-i-Cancho

Quantitative, Mathematical and Computational Linguistics Research Group, Department of Computer Science, Universitat Polit`ecnica de Catalunya, 08034 Barcelona, Catalonia (Spain)

Linguistic Typology

Open paper AskPDF arXiv

Languages of the world vary concerning the order of subject, object and verb. The most frequent dominant orders are SOV and SVO, and researchers have tailored models to this fact. However, there are still languages whose dominant order does not conform to these expectations or even lack a dominant order. Here we show that across linguistic families and macroareas, word order variation within languages is shaped by the principle of swap distance minimization even when the dominant order is not SOV/SVO and even when a dominant order is lacking.

Abstract

Combinatorial Optimization

Explore similar work

Swap distance minimization shapes the order of subject, object and verb in languages of the world

Vocabulary shapes cross-lingual variation of word-order learnability in language models

Left-Branching Transformers Excel at Right-Branching Languages: Data Shapes Word Order Preferences in Language Models