Suppose then that we have a minimal tuple cover T of S_{0} U ... U S_{m}, i.e. a minimal set of mtuples of different elements jointly covering all subsets of S with cardinality ≤ m, and we want to extend T to a minimal set T' of (m + 1)tuples jointly covering S_{0} U ... U S_{m} U S_{m}_{ + 1}. We state without proof the following
Lemma. If m ≤ N/2, a miminal tuple cover of S_{0} U ... U S_{m} has cardinality C(N,m).
So, T = C(N,m) and we want to extend T to a set T' by assigning to each tuple τ of T one or more tuples of the form τa, a in S − range(τ), in such a way that all subsets of S_{m}_{ + 1} are covered and the final number of elements of the cover T' is C(N,m + 1).
When extending a tuple τ of T we will disregard the order of its elements, so basically we are identifying τ with range(τ); this reduction still yields C(N,m) different elements, since every element of S_{m} must be covered by some tuple of T. So the extension mapping T → T' relates elements of S_{m} to elements of S_{m}_{ + 1}, and in fact can be regarded as a subset of the graph induced by inclusion between elements of these two sets.
It is easy to see that each element of S_{m} is the source of (N − m) arrows, whereas m + 1 arrows arrive at each element of S_{m}_{ + 1}. Our job is then to select C(N,m + 1) arrows from the diagram above so that all the elements from the source and the destination set are met by at least one arrow. This selection process has to maintain some balance so that no source or destination element is left unattended: for instance, if we select for each element of S_{m}_{ + 1} an arbitrary arrow arriving at it there is the possibility that some elements of S_{m} are not visited by any of the selected arrows. The following is a balanced selection criterion: given a fixed injection f : S_{m} → S_{m}_{ + 1} and function g : S_{m}_{ + 1} → S_{m}, both compatible with the inclusion relationship between S_{m} and S_{m}_{ + 1} (that is, X is a subset of f(X) and Y a superset of g(Y)), we select an arrow X → Y iff
Y = f(X) or (X = g(Y) and Y is not in f(S_{m})).
It is obvious that this criterion does not leave any X or Y unvisited. The number of selected arrows coincides with the number of elements in S_{m}_{ + 1}, which is C(N,m + 1) as required. In the following we suppose, without loss of generality, that S is the set {0,...,N − 1}. Constructively defining an inclusion compatible injection from S_{m} to S_{m}_{ + 1} is not a trivial task, but fortunately for us a paper from Pudlák, Turzík and Poljak provides the definition of such an injection f along with an algorithm χ : S_{m}_{ + 1} → {true,false} that checks whether a given Y belongs to f(S_{m}). We adopt the following definition for g:
g(Y) := Y − max(Y),
which leads to this algorithm for generating Τ' from Τ:
extend(N,Τ)
Τ' ← Ø
for every τ in Τ
····X ← range(τ)
····a ← f(X) − X {the one element added to X by f}
····Τ' ← Τ' U {τ·a}
····for i = max(X) + 1 to N − 1
········Y ← X U {i}
········if not χ(Y) then
············Τ' ← Τ' U {τ·i}
········end if
····end for
end for
Note that the double loop over (X,i) is designed in such a way that it only visits the X → Y arrows where X = g(Y), which is maximally efficient and saves us the need to explicity compute g. The complete Τ_{0} = Ø → Τ_{1} → ··· → Τ_{M} process can be inlined to avoid generating the intermediate Τ_{i} covers.
tuplecover(m,N,τ,Τ) {initial call: tuplecover(0,N,Ø,Τ) with Τ empty}
if m = (N − 1)/2 then
····Τ ← Τ U {τ}
else
····X ← range(τ)
····a ← f(X) − X
····tuplecover(m + 1,N,τ·a,Τ)
····for i = max(X) + 1 to N − 1
········Y ← X U {i}
········if not χ(Y) then
············cover(m + 1,N,τ·i,Τ)
········end if
····end for
end if
In order to leverage the tuple cover algorithm to construct a minimal permutation cover, the only missing piece is finding a bijection d : S_{M} → S_{M} such that X ∩ d(X) = Ø for all X in S_{M}, as we already saw. The aforementioned paper from Pudlák et al. provides also such a function (which, in fact, is used for the construction of f). Having all the necessary components, the following is the full algorithm for constructing a minimal permutation cover on S = {0,...,N − 1}.
cover(N)
if N is even then
····N' ← N − 1
else
····N' ← N
end if
Σ ← Ø
Τ ← Ø
tuplecover(0,N',Ø,Τ)
for every τ in Τ
····find τ' in Τ with range(τ') = d(range(τ))
····a ← S − range(τ) − range(τ')
····σ ← τ·a·reverse(τ')
····if N is even then
········Σ ← Σ U {N'·σ}
········Σ ← Σ U {σ·N'}
···· else
········Σ ← Σ U {σ}
····end if
end for
A C++ implementation of the algorithm is available (Boost used). The following are the different covers generated for S = 1,...,8.
S  permutation cover

1  (a) 
2  (ab), (ba) 
3  (acb), (bac), (cba) 
4  (acbd),(dacb),(bacd),(dbac),(cbad),(dcba) 
5  (acedb),(baedc),(bdaec),(bedca),(cbaed),(cdbae),(cebad),(daceb),(decab),(eadbc) 
6  (acedbf),(facedb),(baedcf),(fbaedc),(bdaecf),(fbdaec),(bedcaf),(fbedca),(cbaedf),(fcbaed), (cdbaef),(fcdbae),(cebadf),(fcebad),(dacebf),(fdaceb),(decabf),(fdecab),(eadbcf),(feadbc) 
7  (acegfdb),(baegfdc),(bdagfec),(bdfagec),(bdgfeca),(bedagfc),(befdcag), (begdcaf),(bfaegdc),(bfgecad),(bgafced),(cbagfed),(cdbagfe),(cdfbage), (cdgbafe),(cebagfd),(cefbagd),(cegbafd),(cfbaged),(cfgeadb),(cgbfdae), (dacgfeb),(decbagf),(defcagb),(degcafb),(dfacgeb),(dfgceab),(dgafbec), (eadcgfb),(efadbgc),(efgdabc),(egadbfc),(facegdb),(fgaebdc),(gacfdeb) 
8  (acegfdbh),(hacegfdb),(baegfdch),(hbaegfdc),(bdagfech),(hbdagfec),(bdfagech), (hbdfagec),(bdgfecah),(hbdgfeca),(bedagfch),(hbedagfc),(befdcagh),(hbefdcag), (begdcafh),(hbegdcaf),(bfaegdch),(hbfaegdc),(bfgecadh),(hbfgecad),(bgafcedh), (hbgafced),(cbagfedh),(hcbagfed),(cdbagfeh),(hcdbagfe),(cdfbageh),(hcdfbage), (cdgbafeh),(hcdgbafe),(cebagfdh),(hcebagfd),(cefbagdh),(hcefbagd),(cegbafdh), (hcegbafd),(cfbagedh),(hcfbaged),(cfgeadbh),(hcfgeadb),(cgbfdaeh),(hcgbfdae), (dacgfebh),(hdacgfeb),(decbagfh),(hdecbagf),(defcagbh),(hdefcagb),(degcafbh), (hdegcafb),(dfacgebh),(hdfacgeb),(dfgceabh),(hdfgceab),(dgafbech),(hdgafbec), (eadcgfbh),(headcgfb),(efadbgch),(hefadbgc),(efgdabch),(hefgdabc),(egadbfch), (hegadbfc),(facegdbh),(hfacegdb),(fgaebdch),(hfgaebdc),(gacfdebh),(hgacfdeb) 
In a later entry we will see a practical application of permutation covers in the context of database querying.
No comments :
Post a Comment