Function Repository Resource:

 PermutationMinimize

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
"MetropolisHastings"Markov chain Monte Carlo search at a fixed temperature
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 minima. The excursion 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 only by "SearchBreadth").
Orderings already visited during the current excursion are not revisited. Such candidates are not evaluated, but count toward MaxIterations.
Method→{"MetropolisHastings",subopts} supports the following suboption:
"Temperature"Automaticfixed temperature of the search
"MetropolisHastings" and "SimulatedAnnealing" use the same basic process. They always accepts a candidate that does not increase the cost, and accepts one that increases the cost by d with probability Exp[-d/t], where t is the temperature. The difference is that In "SimulatedAnnealing", the temperature t decays geometrically so that the algorithms settles into a minumum and in "MetropolisHastings" it remains fixed so that the search keeps exploring . In both cases the best ordering visited is returned.
With "Temperature"→Automatic, t is a tenth of the mean change in cost of random candidates generated from the starting ordering.
Every move used by "CandidateGeneration" is as likely to be proposed as the move that undoes it, so no Hastings correction is needed, and the search samples orderings with probability proportional to Exp[-f[ordering]/t].

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

Examples

Basic Examples (3) 

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

In[1]:=
ResourceFunction[
 "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][
 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", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][
 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", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][
 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", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][
   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", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][
 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", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][Total[Abs[# - Range[20]]] &, RandomSample[Range[20], 20], RandomSeeding -> 1]
Out[17]=

Options (13) 

Method (5) 

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

In[18]:=
f = Total[(Range[7] - #)^2 Range[7]] &;
ResourceFunction[
 "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][f, {5, 2, 7, 1, 6, 3, 4}]
Out[18]=

Heuristic methods can be used on short lists as well:

In[19]:=
ResourceFunction[
 "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][f, {5, 2, 7, 1, 6, 3, 4}, Method -> "LocalSearch", RandomSeeding -> 1]
Out[19]=
In[20]:=
ResourceFunction[
 "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][f, {5, 2, 7, 1, 6, 3, 4}, Method -> "SimulatedAnnealing", RandomSeeding -> 1]
Out[20]=
In[21]:=
ResourceFunction[
 "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][f, {5, 2, 7, 1, 6, 3, 4}, Method -> "MetropolisHastings", RandomSeeding -> 1]
Out[21]=

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

In[22]:=
SeedRandom[3];
pts = RandomReal[1, {30, 2}];
len = Total[EuclideanDistance @@@ Partition[#, 2, 1, 1]] &;
{First@ResourceFunction[
   "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][len, pts, Method -> "LocalSearch", MaxIterations -> 100000, RandomSeeding -> 4],
  First@ResourceFunction[
   "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][len, pts, Method -> {"LocalSearch", "SearchDepth" -> 5, "SearchBreadth" -> 400}, MaxIterations -> 100000, RandomSeeding -> 4]}
Out[22]=

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

In[23]:=
Table[p -> First@ResourceFunction[
    "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][len, pts, Method -> {"LocalSearch", "SearchBreadth" -> 100, "ImprovementPool" -> p}, MaxIterations -> 20000, RandomSeeding -> 1], {p, {1, 5, Infinity}}]
Out[23]=

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

In[24]:=
evals = 0;
ResourceFunction[
 "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][(evals++; len[#]) &, pts, Method -> {"LocalSearch", "SearchDepth" -> 3, "MaxExcursions" -> 50}, MaxIterations -> 100000, RandomSeeding -> 1]; evals
Out[24]=

With "MetropolisHastings", "Temperature" sets how readily worse orderings are accepted (at too low a temperature one can get trapped in a local minimum, and wander without settling at too high a temperature):

In[25]:=
Table[t -> First@ResourceFunction[
    "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][len, pts, Method -> {"MetropolisHastings", "Temperature" -> t}, MaxIterations -> 20000, RandomSeeding -> 1], {t, {0.001, 0.03, 0.3}}]
Out[25]=

MaxIterations (1) 

Increase MaxIterations to get better results (usually) for heuristic methods:

In[26]:=
cost = Total[Abs[Differences[#]]] &;
Table[First@
  ResourceFunction[
   "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][cost, RandomSample[Range[30]], MaxIterations -> k, RandomSeeding -> 1], {k, {100, 1000, 10000, 100000}}]
Out[26]=

RandomRestarts (2) 

Restarting from random orderings helps heuristic methods avoid local minima:

In[27]:=
SeedRandom[3];
pts = RandomReal[1, {30, 2}];
len = Total[EuclideanDistance @@@ Partition[#, 2, 1, 1]] &;
Table[First@
  ResourceFunction[
   "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][len, pts, Method -> "LocalSearch", MaxIterations -> 2000, "RandomRestarts" -> r, RandomSeeding -> 1], {r, {None, 5, 20}}]
Out[27]=

With {n,Infinity}, batches of n restarts are run until a batch fails to improve the result:

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

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

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

CandidateGeneration (2) 

Compare the moves used to generate candidate orderings on a tour problem:

In[30]:=
Table[cg -> First@ResourceFunction[
    "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][len, pts, "CandidateGeneration" -> cg, MaxIterations -> 20000, RandomSeeding -> 1], {cg, {{"Swaps"}, {"NeighborSwaps"}, {"SegmentReverse"}, {"ElementMove"}, {"Swaps", "SegmentReverse", "ElementMove"}}}]
Out[30]=

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

In[31]:=
inversions = Count[Subsets[#, {2}], {a_, b_} /; a > b] &;
ResourceFunction[
 "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][inversions, RandomSample[Range[15]], Method -> "LocalSearch", "CandidateGeneration" -> {"NeighborSwaps"}, MaxIterations -> 5000, RandomSeeding -> 1]
Out[31]=

RandomSeeding (3) 

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

In[32]:=
Table[First@
  ResourceFunction[
   "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][len, pts, Method -> "LocalSearch", MaxIterations -> 1000], 3]
Out[32]=

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

In[33]:=
Table[SeedRandom[5]; First@ResourceFunction[
   "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][len, pts, Method -> "LocalSearch", MaxIterations -> 1000], 3]
Out[33]=

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

In[34]:=
Table[First@
  ResourceFunction[
   "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][len, pts, Method -> "LocalSearch", MaxIterations -> 1000, RandomSeeding -> 123], 3]
Out[34]=

Applications (2) 

Find a short closed tour through a set of points:

In[35]:=
SeedRandom[1];
pts = RandomReal[1, {25, 2}];
{len, tour} = ResourceFunction[
   "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][
   Total[EuclideanDistance @@@ Partition[#, 2, 1, 1]] &, pts, RandomSeeding -> 1];
len
Out[35]=
In[36]:=
Graphics[{Line[Append[tour, First[tour]]], Red, PointSize[Medium], Point[pts]}]
Out[36]=

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

In[37]:=
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", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][
 Count[feuds, p_ /; adjacentQ[#, p]] &, {"Ann", "Bob", "Cat", "Dan", "Eve", "Fay"}]
Out[37]=

Properties and Relations (2) 

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

In[38]:=
g = Total[Abs[Differences[#]]^2] &;
Min[g /@ Permutations[{1, 5, 2, 8, 3, 7}]] == First[ResourceFunction[
   "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][g, {1, 5, 2, 8, 3, 7}, Method -> "Exhaustive"]]
Out[38]=

PermutationMinimize is broadly equivalent to the resource function "MaximizeOverPermutations" with a negated target function to optimize. PermutationMinimize provides different methods for searching but its Method→"Exhaustive" is roughly equivalent to "MaximizeOverPermutations" Method→"Enumerate" and Method→"MetropolisHastings" is roughly equivalent to "MaximizeOverPermutations" Method→"MonteCarlo" PermutationMinimize returns only one solution where "MaximizeOverPermutations" returns all discovered solutions:

In[39]:=
ResourceFunction["MaximizeOverPermutations"][#[[2]] &, 3]
Out[39]=
In[40]:=
ResourceFunction[
 "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][-#[[2]] &, Range[3]]
Out[40]=

Possible Issues (4) 

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

In[41]:=
ResourceFunction[
 "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][Total[Abs[# - Range[40]]] &, RandomSample[Range[40]], MaxIterations -> 1000, RandomSeeding -> 1]
Out[41]=

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

In[42]:=
Table[{n, First@AbsoluteTiming[
    ResourceFunction[
     "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][Total, Range[n], Method -> "Exhaustive"]]}, {n, 5, 8}]
Out[42]=

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

In[43]:=
ResourceFunction[
 "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][Total[Range[3] #] &, {3, 1, 2}, Method -> "Exhaustive", "RandomRestarts" -> 5]
Out[43]=

The cost function must return a real number:

In[44]:=
ResourceFunction[
 "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][h, {1, 2, 3}]
Out[44]=

Neat Examples (1) 

Sort random colors into a smooth gradient:

In[45]:=
SeedRandom[7];
colors = RandomColor[24];
Row[colors]
Out[46]=
In[47]:=
Row[Last@
  ResourceFunction[
   "PermutationMinimize", ResourceSystemBase -> "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"][Total[ColorDistance @@@ Partition[#, 2, 1]] &, colors, RandomSeeding -> 1]]
Out[47]=

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