0
$\begingroup$

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 ?

$\endgroup$
0
$\begingroup$

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^+$.
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Beinje Jul 30 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.