Adjacency of intersected sets

Vote count:

0

Given a known number N of sets of items. Each set containing exactly D - 1 (N >= D) unique (within the set) items. But each item shared between D - 1 sets. Therefore every set have two "neighbouring" sets: both neighbours differs by exactly one element. Also every set have (if D is big enough) two more distant neighbouring sets, that differs by exactly two elements, etc. All sets together forms a closed chain.

E.g. there are ten elements a x b n q p j t r c. D = 4. And sets are (in parentheses are hints for possible ordering of neighbouring sets):

c x j (1)
p j x (2)
x a p (3)
p a n (4)
n q b (6)
a n q (5)
b r t (8)
b q t (7)
j c r (0)
c t r (9)

=> respective chain of items is: r c j x p a n q b t. The example generated as the result of backward substitution. But how to perform the restoration of the neighbourhood algoritmically ?

One way is obvious: simply enumerate all possible pairs of sets and compare sets from each pair whether they are differs exactly by one element or not (also there is possible some small optimizations, but they not matters much).

Another way to solve the problem is to generate (for each set from input) hashes for all possible D - 2-tuples of ordered sets of elements, then find pairs of collisions. There is a knowledge domain called Locality-Sensitive Hashing.

Both approaches seems to me as a full opposites. Hashing is faster, but implies the adjustment (of buckets sizes, choosing the way of hash combining for vector elements etc.) and most of its operations have amortized constant time. So, there involved some probabilistic actions. I can conclude, that for some D and N there is possibility to encounter performance degradation.

I suspect that there is a deterministic (in above sense) way to find all the neighbouring (adjacent) sets.

asked 57 secs ago

Orient

1,025

Adjacency of intersected sets