# Sort 2D arrays so that cost of reaching new position as described at each iteration is minimized

Problem is as following:

We are 8 trumpet players in an orchestra.

There are for example 4 parts so there are always two players on the same part.

Now, there are not always the same two players playing the same part meaning the combination of players that play the same part change from piece to piece.

What is the cheapest way in terms of distance and/or the least amount of switches resulting that the players playing the same parts can sit next to each other on every piece?

Trumpet Players: a,b,c,d,e,f,g,h

Parts: 1,2,3,4

Seats are arranged like that:

1st piece
| a1 | b1 | c2 | d2 |

| e3 | f3 | g4 | h4 |

Next piece the players might play the following parts:
| a2 | b1 | c3 | d1 |

| e3 | f4 | g2 | h4 |

and the next one againt different distribution of the parts:
| a4 | b3 | c1 | d3 |

| e2 | f4 | g2 | h1 |


how do we seat the players so that the least amount has to be traveled in order to reach the desired positions for the players playing the same parts to sit next to each other in the next piece?

additional notes: i dont care where the pairs are starting and if a1 sits left of b1 or the other way around.

• "We are 8 trumpet players in an orchestra" Do you imply you could have, say, 20 or even 100 of players? I am just checking if exhaustive search could work. – Apass.Jack Feb 1 at 6:15
• In this case it would probably never exceed 12 or so. But if the algorithm was scaleable like that it would be great. – jteichert Feb 1 at 8:04
• how would I solve this with exhaustive search? Build a decision tree? – jteichert Feb 3 at 11:21
• how many pieces are there? If there are more than 5, an exhaustive search for even for 8 trumpet players is unlikely to finish before the next performance as there are about $2*7!*(8!)^5\approx 1.0*10^{27}$ situations. – Apass.Jack Feb 4 at 13:26
• How do you want to measure the distance between the seating for one piece and the seating for the next piece? You mention "the number of switches"; are you assuming that a pair of players can switch seats, and you want to know the number of switches needed, and to get from one seating to another you'll restrict things to some sequence of switches? (continued) – D.W. Feb 21 at 23:15