# restricting “dances of minimal cost” (optimization on braids/permutations?)

Consider applying the permutation (1,3,0,5,2,7,4,6) to the integers (0,1,2,3,4,5,6,7) three times. I call this a "dance of minimal cost" because all unordered pairs in {0..7} meet each other, and the total movement of all the "dancers" is minimal. For a pair to "meet" I simply mean that, at some point during the dance, they occupy adjacent positions.

Say that n=8 in this case. Here is a crude illustration of the dance:

    0 -\ /--- 1 -\ /--- 3 -\ /--- 5
X         X         X
1 -/ \ /- 3 -/ \ /- 5 -/ \ /- 7
X         X         X
2 -\ / \- 0 -\ / \- 1 -\ / \- 3
X         X         X
3 -/ \ /- 5 -/ \ /- 7 -/ \ /- 6
X         X         X
4 -\ / \- 2 -\ / \- 0 -\ / \- 1
X         X         X
5 -/ \ /- 7 -/ \ /- 6 -/ \ /- 4
X         X         X
6 -\ / \- 4 -\ / \- 2 -\ / \- 0
X         X         X
7 -/ \--- 6 -/ \--- 4 -/ \--- 2

-----------------------------------------
t=0       t=1       t=2       t=3


It looks something like a braid. We can define the cost of a dance to be the sum of the distances by which each element is displaced. For the dance above, the cost is 42 (3 permutations x cost of 14 each). The permutation (1,3,0,5,2,7,4,6) has a cost of 14 since it displaces all 8 elements up or down by 2, except for the second and second-last elements which move up and down by a distance of 1.

I should mention that the dance above is not unique, for example there are other dances on {0..7} which also have cost 42 but consist of different permutations, not repeated application of a single permutation as illustrated above. I am reasonably confident that the cost of 42 is minimal for the n=8 case but do not have a solid proof.

The question I have is this: what can be said about dances of minimal (or approximately minimal) cost in the following restricted case: suppose we introduce a radius r, and require not that every pair of dancers meet, but only those initially within distance r of each other. For example, a dance on {0..7} with n=8, r=2 and initial configuration (0,1,2,3,4,5,6,7) does not need {2} and {5} to meet, since these are initially separated by a distance 3, greater than r.

Edit: Can this notion of restriction be cast in the language of forbidden patterns, I wonder?

-