An idea is to use a tree of set instead of a tree of indexes. One can develop it arbitrarily to a valid tree of indexes at end. An advantage is that you obtain all the valid trees with this process.
Let's consider the set of sets $A$ as a list $A[i]$.
The initial tree $G(V, E)$ of set contains only one vertex which is the first set $root = s_0$. And you keep a set $D$ of all indexes you already encoutered.
Then, we loop on other sets to add their information to the set tree. We consider the vertices of the tree starting from the root and adding new vertices when necessary.
let s define a function compare($s$, $v$) with $s$ a set and $v$, the set associated to a vertex of $G$.
if $s == v$ then return true
$c = s \cap v$
if $c == v$ then
- for $v_s$ in sons(v) if compare(s-c, $v_s$) then return true
- if $s-c \cap D$ is not empty then return false
- create a new son to $v$, $v_s$ associated to set $s-c$ and return True
in $G$, develop vertex $v$ to $v_1$ and $v_2$ associated respectively to sets $c$ and $v-c$, return compare($s$, $v_1$)
Thus, the main loop is:
- $root = A[0]$
- $D = A[0]$
- for $s$ in $A[1:]$
- if compare(s, root) then $D = D \cup s$
- else return false
- return true
When reaching the $i^{th}$ set, $G$ contains at most $i-1$ vertices, and you will recursively call the compare function up to $i-1$ times. Thus for $N$ sets covering $L$ different indexes (thus the set operations are $O(L)$), this algorithm solves the problem in $O(L N^2)$
An exemple:
$A = [\{1, 3, 5\}, \{1, 2, 3, 4\}, \{ 1, 2, 3, 6\}, \{1, 2, 3, 5, 7\}]$
the initial tree $T$ has one vertex associated to the set $A[0] = \{1, 3, 5\}$
{1, 3, 5}
then you treat $A[1] = \{1, 2, 3, 4\}$, the root vertex has to be developed in
{1, 3} - {5}
to finally add a $\{2, 4\}$ son vertex to the root:
{1, 3} - {5}
|
{2, 4}
then comes $A[2] = \{ 1, 2, 3, 6\}$, after root, it remains $s = \{2, 6\}$. On $\{5\}$ child, there is no possibility as 2 is already in $D$. But on $\{2, 4\}$ child, it works after developing it.
{1, 3} - {5}
|
{2} - {4}
|
{6}
Finally comes $A[3] = \{1, 2, 3, 5, 7\}$, that will not work as 2 and 5 are both in $D$ and in different branches of $T$.
