Zbiory, z których każde dwa posiadają jeden element wspólny

[SzalPal]

Witam, mam do rozwiązania problem programistyczny. Chodzi o to, żeby wygenerować wszystkie \(\displaystyle{ n}\)-elementowe zbiory, z pośród których każde dwa posiadają dokładnie jeden element wspólny. Zakładając, że mamy do dyspozycji \(\displaystyle{ m}\) elementów. Na razie nie rozpatruję tego, w jaki sposób powinna być dobrana liczba \(\displaystyle{ n}\) na podstawie \(\displaystyle{ m}\). Jeśli to uprości sprawę, można przyjąć, że dobrana jest w taki sposób, żeby każdy element wystąpił taką samą liczbę razy, ale docelowo nie będzie to spełnione raczej.
Moja pierwsza myśl była na zasadzie wybierania ze zbioru M (zawierającego wszystkie elementy) podzbiory posiadające konkretny element i pozostałe \(\displaystyle{ n-1}\) elementów kolejno ze zbioru M, aż do wyczerpania tychże, a następnie usunięciu wspólnego elementu ze zbioru M i powtórzeniu procedury. Ale w tym przypadku pojawia się problem w kolejnych iteracjach sprawdzania, czy dane podzbiory nie mają więcej niż jednego elementu wspólnego z podzbiorami z poprzednich iteracji.
Próbowałem też z \(\displaystyle{ n}\) generatorami pseudolosowymi o odpowiednio dobranych parametrach i ziarnie, ale niestety nie udało mi się znaleźć tego "odpowiedniego" sposobu.
Czy moglibyście naprowadzić mnie na jakieś twierdzenie lub algorytm, które byłoby pomocne w rozwiązaniu tego problemu?

[SidCom]

Mnie pierwsze co przyszło na myśl to TW. Helly (1913) z geometrii...Jeżeli każde dwa zbiory z rodziny posiadają element wspólny to cała rodzina zbiorów ma ten element wspólny...

[SzalPal]

Dając przykład:
\(\displaystyle{ \left\{ {1, 2, 3, 4}\right\}
\left\{ {1, 5, 6, 7}\right\}
\left\{ {1, 8, 9, 10}\right\}
\left\{ {2, 6, 9, 11}\right\}}\)

Każde dwa z tych zbiorów mają dokładnie jeden element wspólny. Przecięcie wszystkich jest zbiorem pustym. Zdaje się, że tw. Helly'ego mówi o tym, że niepuste musi być przecięcie co najmniej trzech każdych zbiorów.

[a4karo]

To twierdzenie mówi o zbiorach wypukłych

[SidCom]

To było pierwsze skojarzenie... Helly mówi o zbiorach ciągłych nie dyskretnych

[pyzol]

O ile dobrze zrozumiałem, to mam dość prosty algorytm:
\(\displaystyle{ \left\{ 1,2\right\} \\
\left\{ 1,3\right\} \\
\left\{ 2,3\right\}}\)
Dorzucamy teraz następny zbiór musi on mieć elementy wspólne z tamtymi, tamte więc musimy rozbudować:
\(\displaystyle{ \left\{ 1,2,4\right\} \\
\left\{ 1,3,5\right\} \\
\left\{ 2,3,6\right\}\\
\left\{ 4,5,6\right\}}\)
I tak dalej. Jakbyśmy chcieli uzyskać inną rodzinę zbiorów, to wystarczyłoby zrobić permutację zbioru: \(\displaystyle{ \left\{1,2,3,...,m \right\}}\). Problem w tym, że musi być odpowiednia liczba elementów, by taką rodzinę zbudować.

[a4karo]

To było pierwsze skojarzenie... Helly mówi o zbiorach ciągłych nie dyskretnych

Co to jest zbiór ciągły?

[SzalPal]

Przedstawiam takie bardziej naukowe (i chyba najwłaściwsze) rozwiązanie problemu:

Ogólnie sprowadza się to do wyznaczenia największej kliki w zgeneralizowanym \(\displaystyle{ KG_{n,k,1}}\). To jest takim, w którym wierzchołki są \(\displaystyle{ n}\)-elementowymi podzbiorami zbioru \(\displaystyle{ M}\) (czyli zbioru zawierającego wszystkie elementy), a krawędzie łączą te wierzchołki, które posiadają dokładnie jeden element wspólny. No dobra, nie jest to prawdziwy \(\displaystyle{ KG_{n,k,1}}\), bo odrzucamy krawędzi łączące wierzchołki zbiorów rozłącznych. Więc rozpatrujemy podgraf tego grafu

Jaka jest korzyść ze skorzystania z takiego sposobu? W przypadku "siłowym" można wybrać jeden element, zbudować na jego podstawie \(\displaystyle{ n}\)-elementowe podzbiory, następnie wybrać kolejny i znów budować podzbiory, ale trzeba wtedy sprawdzać warunek jedno elementowego przecięcia z każdym z podzbiorów wcześniejszej iteracji.
Natomiast algorytm znajdowania największej kliki jest już zaimplementowany w różnych bibliotekach. I jako tako zoptymalizowany, chociaż i tak wymagający obliczeniowo.