Генерация пересекающихся подмножеств

#алгоритм #множества

Был вчера в гостях, где моему малому показали игру Доббль. В ней имеется набор карточек
с резными пиктограммами, го главное - на любых двух карточках всегда имеется одна и
только одна общая пиктограмма.

С математической точки зрения это означает - имеется множество из N элементов; нужно
построить как можно большее количество подмножеств из M < N элементов, обладающих тем
свойством, что каждые два подмножества имеют один и только один общий элемент.

Как решить эту задачу? Каким алгоритмом сгенерировать эти подмножества? Пусть хоть
для каких-то нетривиальных вариантов - для 3 и 2, как вы понимаете, решение тривиальное
:), как и решение с единственным для всех общим элементом.

Буду признателен как за готовое решение, так и за любые идеи. 
    

Ответы

Ответ 1

Ответ 1-ый - не верный, потому как недооценил всей прелести поставленной проблемы

Я предполагаю, что можно не вдаваться в дебри пересечений множеств, а просто выделив
два подмножества, что уже не так сложно, "примешать" к ним одно и тоже значение, которое
в них не входит. (одна из любых идей)

Ответ 2-ой - к сожалению не мой, неудержался, подсмотрел на просторах инета. 

\#define PRINT(x) printf("%2d  ", (x)+1)

main() {
int i, j, k, r = 0, n = 7;

// first card
printf ("Card %2d:  ", ++r);
for (i = 0; i <= n; i++) {
    PRINT (i);
}
printf ("\n");

// n following cards
for (j = 0; j < n; j++) {
    printf ("Card %2d:  ", ++r);
    PRINT (0);
    for (k = 0; k < n; k++) {
        PRINT (n+1 + n*j + k);
    }
    printf ("\n");
}

// n*n following cards
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        printf ("Card %2d:  ", ++r);
        PRINT (i+1);
        for (k = 0; k < n; k++) {
            PRINT (n+1 + n*k + (i*k+j)%n); // Good for n = prime number
        }
        printf ("\n");
    }
  }
}


А здесь можно посмотреть решение в действии


Ответ 2

имеется множество из N элементов; нужно построить как можно большее количество подмножеств
из M < N элементов, обладающих тем свойством, что каждые два подмножества имеют один
и только один общий элемент.


Давайте думать. Что имеем? У нас есть N элементов. В каждой группе должно быть M
элементов. 

Создадим первую группу. Допустим, в неё включены элементы с номерами от 1 до M. 

Создадим вторую группу. Она должна иметь с первой только 1 общий элемент. Пусть это
будет элемент 1. Тогда вторая группа содержит элемент 1 и элементы от M+1 до 2*M-1.

Создадим третью группу. Она должна иметь с каждой из ранее созданных только по 1
общему элементу. Ну вариант, когда это опять элемент 1, отметём как тривиальный (но
не как невозможный!!!). Тогда это будут элементы 2 (пересекаемся с группой 1) и M+1
(пересекаемся с группой 2), а остальные - это элементы с номерами от 2*M до 3*M-3.

Надеюсь, методика понятна? ну а дальше - самостоятельно... пока не выскочите за N,
или пока не кончатся варианты.

PS. Чую запах совершенных чисел...


Ответ 3

Резервируем первый элемент из N.
Разбиваем оставшиеся элементы в группы по M-1 элементов.
Добавляем в каждую из групп зарезервированный элемент.


Ответ 4

Случайно увидел в голове перед сном такой вариант для случая N=M(M-1)/2. Причём число
подмножеств M, а их размер M-1.

Пронумеруем элементы исходного множества числами от 1 до N, а генерируемые множества
обозначим A1, A2, ..., AM.

Берём элемент 1 и кладём его в множества A1 и A2. Берём элемент 2 и кладём его в
множества A1 и A3, затем элемент 3 в A1 и A4 и так далее до A1 и AM. Затем как бы возвращаемся
к началу и кладём очередной элемент (с номером M) в множества A2 и A3, затем (элемент
M+1) в A2 и A4 и т. д. Пример для N=6 и M=4:

123
145
426
563


Пример для N=10 и M=5 (вместо 10 написал 0):

1234
1567
5289
6830
7904


Доказательство придумывать, к сожалению, некогда.