Friday, September 26, 2008

Generating permutation covers: part I

We investigate ways of efficiently generating minimal permutation covers for a set S of N elements. As we have already proved, such covers have size C(N,floor(N/2)). The following intermediate results reduce the problem to simpler terms.

Theorem. Assume that N is even and greater than zero. Let a be an an arbitrary element of S and Σ a minimal permutation cover of S − {a}. The set Σ' defined as

Σ' = {, σa : σ in Σ}

is a minimal permutation cover of S.

Proof. Σ' is a permutation cover: let X be a subset of S; if a is not in X, X is covered by some permutation σ of Σ and a fortiori by σa in Σ'; if a belongs to X, some σ in Σ covers X − {a} and then in Σ' covers X. Σ' is minimal as |Σ'| = 2|Σ| = 2 C(N − 1, floor((N − 1)/2)) = 2 C(N − 1, N/2 − 1) = C(N,N/2) = C(N,floor(N/2)), where the equalities depend on basic properties of binomial coefficients and the fact that N is even.

This result reduces the problem to N odd. The Hasse diagram of the powerset of S when N is odd looks like this (the particular case depicted is N = 5):

We name the layers of the diagram S0,...,SN. Si consists of the subsets of S with cardinality i. We have |Si| = C(N,i). A permutation covers exactly one element of each Si. Similarly, a tuple τ of n non-repeating elements covers exactly one element of each of S0,...,Sn. So, a minimal tuple cover of S0,...,Sn can be proved to have as many elements as the largest layer covered. The next result shows how to extend a minimal tuple cover of S0,...,S(N − 1)/2 , which has cardinality C(N,(N − 1)/2) = C(N,floor(N/2)) and spreads over the bottom half of the powerset of S, to a minimal permutation cover of S.

Theorem. Assume that N is odd and set M = (N − 1)/2. Let Τ be a minimal set of M-tuples of non-repeating elements covering S0 U ... U SM, and d : SMSM a bijection with Xd(X) = Ø for all X in SM. The set Σ defined as

Σ = { τ·a·reverse(τ') : τ,τ' belong to Τ, range(τ') = d(range(τ)), a = S − range(τ) − range(τ')}

is a minimal permutation cover of S.

Proof. We see first that to each τ in Τ there corresponds exactly one permutation στ of the form τ·a·reverse(τ') described above: since Τ is minimal each element of SM is covered by one and only one element of Τ; so, for each τ there is exactly one τ' covering d(range(τ)). We prove now that Σ covers S: let X be a subset of S; if |X| ≤ M, X is covered by some τ in Τ and hence also by the associated στ; if |X| > M, the set Y = SX has |Y| ≤ M and is thus covered by some τ' in Τ; as we have seen, τ' univocally determines a permutation σ = τ·a·reverse(τ'), and σ obviously covers X, as all the elements of Y are packed at the tail of the permutation. Finally, Σ is minimal, since |Σ|= |Τ| and we saw before that |Τ| = C(N,floor(N/2)).

The mapping τστ just defined can be described in a more algorithmic fashion as follows:

  1. Find the τ' in Τ covering d(range(τ)).
  2. Let a be the only element of S not present in τ nor τ'.
  3. στ := τ·a·reverse(τ').

Note that the last theorem extends easily to N even: in this case, the permutations have the form τ·reverse(τ'), i.e. there is no middle element a. However, it is more efficient to reduce the case N even to N − 1 using the first theorem of this entry.

Now we are left with the tasks of designing an algorithm to generate a tuple set Τ covering S0 U ... U SM and finding a suitable bijection d : SMSM.

1 comment :

  1. Can you develop something on Range Voting using for instance Spain's elections as an example?
    http://www.technologyreview.com/article/21172/

    ReplyDelete