Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 MinSumPermutation

Source Notebook

Find a permutation that minimizes a matrix sum

Contributed by: Wolfram Research

ResourceFunction["MinSumPermutation"][m]

finds a permutation p such that the quantity is minimized for the matrix m .

Details and Options

ResourceFunction["MinSumPermutation"] uses integer linear optimization to find the optimal matrix.

Examples

Basic Examples (3) 

Define a matrix:

In[1]:=
mat = {{41, 40, 40, 40}, {40, 39, 39, 41}, {40, 39, 41, 39}, {40, 41, 39, 39}};

Return the minimizing permutation:

In[2]:=
p = ResourceFunction["MinSumPermutation"][mat]
Out[2]=

The sum:

In[3]:=
Sum[mat[[i, p[[i]]]], {i, Length[p]}]
Out[3]=

Scope (1) 

Use on a larger example:

In[4]:=
ResourceFunction[ "MinSumPermutation"][{{41, 38, 38, 39, 39, 38, 38, 40, 40, 38, 38, 39, 39, 40, 39, 39, 40, 40, 38}, {40, 37, 37, 38, 38, 37, 39, 39, 41, 37, 39, 38, 40, 39, 38, 40, 39, 41, 39}, {40, 37, 37, 38, 38, 39, 37, 41, 39, 39, 37, 40, 38, 39, 40, 38, 41, 39, 39}, {40, 39, 39, 40, 40, 39, 39, 39, 39, 37, 37, 40, 40, 41, 38, 38, 39, 39, 37}, {38, 35, 35, 36, 36, 37, 37, 39, 39, 39, 39, 38, 38, 37, 40, 40, 39, 39, 41}, {39, 36, 36, 37, 37, 36, 38, 38, 40, 38, 40, 37, 39, 38, 39, 41, 38, 40, 40}, {39, 36, 36, 37, 37, 38, 36, 40, 38, 40, 38, 39, 37, 38, 41, 39, 40, 38, 40}, {39, 38, 38, 39, 39, 38, 40, 38, 42, 36, 40, 39, 41, 40, 37, 39, 38, 40, 38}, {39, 38, 38, 39, 39, 40, 38, 42, 38, 40, 36, 41, 39, 40, 39, 37, 40, 38, 38}, {38, 35, 37, 36, 38, 35, 39, 37, 41, 39, 41, 36, 40, 37, 38, 40, 37, 39, 39}, {38, 37, 35, 38, 36, 39, 35, 41, 37, 41, 39, 40, 36, 37, 40, 38, 39, 37, 39}, {39, 40, 40, 41, 41, 40, 40, 38, 40, 36, 38, 39, 39, 40, 37, 37, 38, 38, 36}, {39, 40, 40, 41, 41, 40, 40, 40, 38, 38, 36, 39, 39, 40, 37, 37, 38, 38, 36}, {40, 37, 39, 38, 40, 37, 41, 37, 43, 37, 41, 38, 42, 39, 38, 40, 39, 41, 39}, {38, 39, 39, 40, 40, 39, 41, 37, 41, 35, 39, 38, 40, 39, 36, 38, 37, 39, 37}, {40, 39, 37, 40, 38, 41, 37, 43, 37, 41, 37, 42, 38, 39, 40, 38, 41, 39, 39}, {38, 39, 39, 40, 40, 41, 39, 41, 37, 39, 35, 40, 38, 39, 38, 36, 39, 37, 37}, {38, 41, 41, 40, 40, 39, 39, 37, 39, 35, 37, 38, 38, 39, 36, 36, 37, 37, 35}, {38, 41, 41, 40, 40, 39, 39, 39, 37, 37, 35, 38, 38, 39, 36, 36, 37, 37, 35}}]
Out[4]=

Possible Issues (2) 

For an m×n matrix with m>n, a solution might not exist:

In[5]:=
ResourceFunction[ "MinSumPermutation"][{{6, 7, 3}, {1, 7, 5}, {5, 1, 4}, {5, 4, 4}}]
Out[5]=

If m<n, the result might not necessarily be a permutation:

In[6]:=
ResourceFunction["MinSumPermutation"][ mat = {{1, 7, 7, 3}, {4, 7, 8, 10}, {8, 4, 10, 3}}]
Out[6]=
In[7]:=
Sum[mat[[i, %[[i]]]], {i, Length[%]}]
Out[7]=

Version History

  • 1.0.0 – 15 April 2020

Related Resources

License Information