# Minimize same placed elements in a list of permutations (Heap)

I'm trying to optimize the permutations generated from a set of n elements.

Here is the pitch: I have a set of 6 elements $$\{1,2,3,4,5,6\}$$ and I want to create 10 permutations. I could use Heap algorithm to keep 10 among 6! possible combinations.

But I'd like to add specific constraint : I want to select the 10 permutations that minimize the number of elements at the same index. (avoid having 10 permutations with the 3 at the same index for example)

For instance, I simply create the first 6 permutations by rotating my initial set from 1 to 6 to the right to obtain the following combinations: $$\{1,2,3,4,5,6\}$$, $$\{2,3,4,5,6,1\}$$, $$\{3,4,5,6,1,2\}$$, $$\{4,5,6,1,2,3\}$$, $$\{5,6,1,2,3,4\}$$, $$\{6,1,2,3,4,5\}$$

Now, I would like to generate additional combinations following my constraint, do you have any clue or advice ?

My initial guess, based on some cursory knowledge about Permutohedrons:

Given your set $$S = {1,2,3,...}$$, generate all permutations $$P(S)$$ and define a multigraph $$G(V,E)$$ where $$V = P(S)$$ (each permutation is a vertex) and the edge-set $$E$$ consists of pairs of permutations that share an element at a common location (e.g. $$123456$$ and $$123465$$ are connected by $$4$$ edges).

Your problem is then picking a subset of $$V' \subset V$$ s.t. the subgraph induced by $$V'$$ has as few edges as possible.

Considerations:

• You can use a weighted graph instead of a multigraph. Replace $$n$$ edges with 1 edge with weight $$n$$. The optimization objective would then be total edge weight of the induced subgraph.
• Based on the many symmetries, I would guess that it should be possible to achieve a very good (maybe even optimal) solution with a greedy algorithm.

Possible greedy algorithm:

• Construct graph, initialize $$V' = \emptyset$$
• Until $$|V'| = n$$:
• For each $$v \in V \setminus V'$$: $$v^+ :=$$ total weight of edges between $$v$$ and $$w\in V'$$
• If $$v^+ = 0$$, add $$v$$ to $$V'$$. Else, add vertex with lowest $$v^+$$.
• Thank you for this elegant solution ! I implemented it and it works like a charm. I can probably optimize the creation of the weighted graph and the computation of the subset but I like it ! Also thanks for the reference to permutohedrons, quite interesting. – Beinje Jul 30 '19 at 15:41