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?