Function Repository Resource:

 PermutationMinimize (1.0.0) current version: 1.1.0 »

Source Notebook

Find an ordering of a list that minimizes a cost function

Contributed by: Jon McLoone

ResourceFunction["PermutationMinimize"][f,elems]

finds an ordering of the list elems that minimizes f[ordering], and returns {fmin,ordering}.

Details and Options

The cost function f is applied to complete orderings of elems and must return a real number.
The result {fmin,ordering} satisfies fmin==f[ordering].
The following options can be given:
MethodAutomaticmethod to use
MaxIterationsAutomaticmaximum number of cost function evaluations
RandomSeedingInheritedseeding of the pseudorandom generator
"RandomRestarts"Noneadditional runs starting from random reorderings of the input
"CandidateGeneration"{"Swaps", "SegmentReverse", "ElementMove"}random moves used by heuristic methods to generate candidate orderings
Possible settings for Method include:
"Exhaustive"evaluate every distinct ordering; guaranteed to find a global minimum
"LocalSearch"random-neighbor hill climbing from a random starting ordering
"SimulatedAnnealing"simulated annealing with geometric cooling
With Method→Automatic, "Exhaustive" is used when elems has 8 or fewer elements, MaxIterations is Automatic or at least the number of distinct orderings of elems, and neither "RandomRestarts" nor "CandidateGeneration" is given. Otherwise "SimulatedAnnealing" is used.
With MaxIterations→Automatic, "Exhaustive" evaluates f up to n! times for a list of length n, at most Max[1000,100 n2] times for heuristic methods.
Possible settings for "RandomRestarts" include:
Nonea single run starting from the order given
none run from elems, then n runs from random reorderings of elems; the best result is returned
{n,m}one run from elems, then batches of n random restarts; another batch is run only if the previous one improved the best result, up to m batches
MaxIterations applies to each run separately.
Heuristic methods generate candidate orderings by applying random moves to the current ordering. Moves are chosen randomly from the methods given by "CandidateGeneration" these can be any combination of:
"Swaps"exchange two elements
"NeighborSwaps"exchange two adjacent elements
"SegmentReverse"reverse the order of a contiguous segment
"ElementMove"move one element to a new position
Heuristic methods may return a local minimum.
Method→{"LocalSearch",subopts} supports the following suboptions:
"SearchBreadth"Automaticmaximum number of candidates tried at each step
"SearchDepth"1maximum number of steps in an excursion
"ImprovementPool"1number of improving candidates to collect before taking the best
"MaxExcursions"Infinityconsecutive excursions without a lower cost before stopping
"LocalSearch" proceeds by testing candidate orderings for improvement, constrained by "SearchBreadth" and "ImprovementPool". The best improvement is used and the process restarts. If no improvement is found, an excursion is started into the best candidate found (which may be worse than the current ordering) in an attempt to escape local mimina. The exclusion can recursively continue up to "SearchDepth" before returning to the best ordering so far. The number of such excursions is constrained by "MaxExcursions"
"ImprovementPool" → 1 takes the first improvement found, and "ImprovementPool" → Infinity takes the best improvement among all candidates (constrained by only by "SearchBreadth").
Orderings already visited during the current excursion are not revisited. Such candidates are not evaluated, but count toward MaxIterations.

Examples

Basic Examples (3) 

Find the ordering of a the list {1, 2, 10,31,32} that most closely aligns with {0, 10, 33, 30, 1}:

In[1]:=
ResourceFunction["PermutationMinimize"][
 Total[Abs[# - {0, 10, 33, 30, 1}]] &, {1, 2, 10, 31, 32}]
Out[1]=

Order words so that adjacent words differ by as few letters as possible:

In[2]:=
ResourceFunction["PermutationMinimize"][
 Total[EditDistance @@@ Partition[#, 2, 1]] &, {"cog", "cat", "dot", "cot", "dog"}]
Out[2]=

Align two ontologies:

In[3]:=
ontology1 = {"Home", "Londres", "Basel", "Roma", "Firenze"};
ontology2 = {"Rome", "Florence", "Base", "London", "Basel"};
ResourceFunction["PermutationMinimize"][
 Total[MapThread[EditDistance, {#, ontology1}]] &, ontology2]
Out[12]=

Scope (3) 

The elements can be arbitrary expressions. Order images to best align their dominant colors::

In[13]:=
images = RandomSample[ExampleData /@ ExampleData["ColorTexture"]];
group1 = images[[1 ;; 10]];
group2 = images[[11 ;; 20]];
group1 = Map[# -> First[DominantColors[#, 1]] &, group1];
group2 = Map[# -> First[DominantColors[#, 1]] &, group2];
In[14]:=
result = ResourceFunction["PermutationMinimize"][
   Total[MapThread[
       Function[{img1, img2}, ColorDistance[img1[[2]] , img2[[2]]]], {#, group2}]^2] &, group1];
In[15]:=
Grid[{First /@ group2, First /@ result[[2]]}]
Out[15]=

Repeated elements are allowed. Arrange elements so that no two equal elements are adjacent:

In[16]:=
ResourceFunction["PermutationMinimize"][
 Count[Partition[#, 2, 1], {x_, x_}] &, {a, a, a, b, b, c}]
Out[16]=

Larger problems use a heuristic method automatically:

In[17]:=
ResourceFunction["PermutationMinimize"][Total[Abs[# - Range[20]]] &, RandomSample[Range[20], 20], RandomSeeding -> 1]
Out[17]=

Options (12) 

Method (4) 

By default, "Exhaustive" is used for short lists, which guarantees a global minimum:

In[18]:=
f = Total[(Range[7] - #)^2 Range[7]] &;
ResourceFunction["PermutationMinimize"][f, {5, 2, 7, 1, 6, 3, 4}]
Out[18]=

Heuristic methods can be used on short lists as well:

In[19]:=
ResourceFunction["PermutationMinimize"][f, {5, 2, 7, 1, 6, 3, 4}, Method -> "LocalSearch", RandomSeeding -> 1]
Out[19]=
In[20]:=
ResourceFunction["PermutationMinimize"][f, {5, 2, 7, 1, 6, 3, 4}, Method -> "SimulatedAnnealing", RandomSeeding -> 1]
Out[20]=

With suboptions, "LocalSearch" makes excursions that may temporarily increase the cost, which can escape local minima:

In[21]:=
SeedRandom[3];
pts = RandomReal[1, {30, 2}];
len = Total[EuclideanDistance @@@ Partition[#, 2, 1, 1]] &;
{First@ResourceFunction["PermutationMinimize"][len, pts, Method -> "LocalSearch", MaxIterations -> 100000, RandomSeeding -> 4],
  First@ResourceFunction["PermutationMinimize"][len, pts, Method -> {"LocalSearch", "SearchDepth" -> 5, "SearchBreadth" -> 400}, MaxIterations -> 100000, RandomSeeding -> 4]}
Out[21]=

Use "ImprovementPool" to collect several improving candidates at each step and take the best of them:

In[22]:=
Table[p -> First@ResourceFunction["PermutationMinimize"][len, pts, Method -> {"LocalSearch", "SearchBreadth" -> 100, "ImprovementPool" -> p}, MaxIterations -> 20000, RandomSeeding -> 1], {p, {1, 5, Infinity}}]
Out[22]=

Use "MaxExcursions" to stop once excursions stop improving the result. Count the number of cost function evaluations:

In[23]:=
evals = 0;
ResourceFunction["PermutationMinimize"][(evals++; len[#]) &, pts, Method -> {"LocalSearch", "SearchDepth" -> 3, "MaxExcursions" -> 50}, MaxIterations -> 100000, RandomSeeding -> 1]; evals
Out[23]=

MaxIterations (1) 

MaxIterations constrains the overall effort that the function will make to find the optimum ordering. Increasing MaxIterations generally gives better results for heuristic methods:

In[24]:=
cost = Total[Abs[Differences[#]]] &;
Table[First@
  ResourceFunction["PermutationMinimize"][cost, RandomSample[Range[30]], MaxIterations -> k, RandomSeeding -> 1], {k, {100, 1000, 10000, 100000}}]
Out[24]=

RandomRestarts (2) 

Restarting from random orderings helps heuristic methods avoid local minima:

In[25]:=
SeedRandom[3];
pts = RandomReal[1, {30, 2}];
len = Total[EuclideanDistance @@@ Partition[#, 2, 1, 1]] &;
Table[First@
  ResourceFunction["PermutationMinimize"][len, pts, Method -> "LocalSearch", MaxIterations -> 2000, "RandomRestarts" -> r, RandomSeeding -> 1], {r, {None, 5, 20}}]
Out[25]=

With {n, Infinity}, batches of n restarts are run until a batch fails to improve the result. Count how many runs were made:

In[26]:=
runs/2000
Out[26]=

With {n, m}, at most m batches of n are run, so at most n m restarts:

In[27]:=
runs/2000
Out[27]=

"RandomRestarts"→n is equivalent to "RandomRestarts"→{n,1}.

CandidateGeneration (2) 

"CandidateGeneration" provides a list of methods for generating new permutations from the current permutation. Each candidate is generated by choosing a method randomly from the list. Compare the moves used to generate candidate orderings on a tour problem:

In[28]:=
Table[cg -> First@ResourceFunction["PermutationMinimize"][len, pts, "CandidateGeneration" -> cg, MaxIterations -> 20000, RandomSeeding -> 1], {cg, {{"Swaps"}, {"NeighborSwaps"}, {"SegmentReverse"}, {"ElementMove"}, {"Swaps", "SegmentReverse", "ElementMove"}}}]
Out[28]=

Sorting by minimizing the number of inversions needs only exchanges of adjacent elements:

In[29]:=
inversions = Count[Subsets[#, {2}], {a_, b_} /; a > b] &;
ResourceFunction["PermutationMinimize"][inversions, RandomSample[Range[15]], Method -> "LocalSearch", "CandidateGeneration" -> {"NeighborSwaps"}, MaxIterations -> 5000, RandomSeeding -> 1]
Out[29]=

RandomSeeding (3) 

Heuristic methods generally give different results each time they are run:

In[30]:=
Table[First@
  ResourceFunction["PermutationMinimize"][len, pts, Method -> "LocalSearch", MaxIterations -> 1000], 3]
Out[30]=

By default, the current state of the pseudorandom generator is used, so SeedRandom gives reproducible results:

In[31]:=
Table[SeedRandom[5]; First@ResourceFunction["PermutationMinimize"][len, pts, Method -> "LocalSearch", MaxIterations -> 1000], 3]
Out[31]=

Use RandomSeeding to get reproducible results independently of the session's random state:

In[32]:=
Table[First@
  ResourceFunction["PermutationMinimize"][len, pts, Method -> "LocalSearch", MaxIterations -> 1000, RandomSeeding -> 123], 3]
Out[32]=

Applications (2) 

Find a short closed tour through a set of points:

In[33]:=
SeedRandom[1];
pts = RandomReal[1, {25, 2}];
{len, tour} = ResourceFunction["PermutationMinimize"][
   Total[EuclideanDistance @@@ Partition[#, 2, 1, 1]] &, pts, RandomSeeding -> 1];
len
Out[33]=
In[34]:=
Graphics[{Line[Append[tour, First[tour]]], Red, PointSize[Medium], Point[pts]}]
Out[34]=

Find a seating arrangement around a table that keeps feuding guests apart:

In[35]:=
feuds = {{"Ann", "Bob"}, {"Bob", "Cat"}, {"Cat", "Dan"}, {"Dan", "Eve"}, {"Eve", "Ann"}};
adjacentQ[s_, {a_, b_}] := MemberQ[Partition[s, 2, 1, 1], {a, b} | {b, a}];
ResourceFunction["PermutationMinimize"][
 Count[feuds, p_ /; adjacentQ[#, p]] &, {"Ann", "Bob", "Cat", "Dan", "Eve", "Fay"}]
Out[35]=

Properties and Relations (1) 

Method→"Exhaustive" gives the same minimum as a brute-force search with Permutations:

In[36]:=
g = Total[Abs[Differences[#]]^2] &;
Min[g /@ Permutations[{1, 5, 2, 8, 3, 7}]] == First[ResourceFunction["PermutationMinimize"][g, {1, 5, 2, 8, 3, 7}, Method -> "Exhaustive"]]
Out[36]=

Possible Issues (4) 

Heuristic methods may return a local minimum, especially with few iterations:

In[37]:=
ResourceFunction["PermutationMinimize"][Total[Abs[# - Range[40]]] &, RandomSample[Range[40]], MaxIterations -> 1000, RandomSeeding -> 1]
Out[37]=

The time taken by "Exhaustive" grows factorially with the length of the list:

In[38]:=
Table[{n, First@AbsoluteTiming[
    ResourceFunction["PermutationMinimize"][Total, Range[n], Method -> "Exhaustive"]]}, {n, 5, 8}]
Out[38]=

"RandomRestarts" is ignored when "Exhaustive" is used:

In[39]:=
ResourceFunction["PermutationMinimize"][Total[Range[3] #] &, {3, 1, 2}, Method -> "Exhaustive", "RandomRestarts" -> 5]
Out[39]=

The cost function must return a real number:

In[40]:=
ResourceFunction["PermutationMinimize"][h, {1, 2, 3}]
Out[40]=

Neat Examples (1) 

Sort random colors into a smooth gradient:

In[41]:=
SeedRandom[7];
colors = RandomColor[24];
Row[colors]
Out[42]=
In[43]:=
Row[Last@
  ResourceFunction["PermutationMinimize"][
   Total[ColorDistance @@@ Partition[#, 2, 1]] &, colors, RandomSeeding -> 1]]
Out[43]=

Publisher

Jon McLoone

Version History

  • 1.1.0 – 11 November 2026
  • 1.0.0 – 14 October 2026

Related Resources

Author Notes

Heuristic methods do not guarantee a global minimum. Possible extensions include method suboptions (e.g. annealing schedule), user-supplied neighborhood moves, and incremental cost updates.

License Information