Есть ли алгоритм, который из N множеств выберет M максимально не пересекающихся?

Question

[Станислав Агарков]

Есть ли алгоритм, который из N множеств выберет M максимально не пересекающихся?

Comments

[Mrrl]

Уточните, пожалуйста, условие. Что означает "максимально не пересекающихся"? Из наборов ({1},{2},{3},{4},{1,2,3,4}) и ({1},{1,2},{1,3},{1,4},{2,3,4}) какой будет более не пересекающимся и почему?

[Станислав Агарков]

Mrrl: Не понял ваш вопрос. Есть три множества: (1,2,3,4), (1,2,5,6) и (1,2,3,7). У первого и второго два общих элемента, у первого и третьего 3 общих элемента, у второго и третьего — 2 общих элемента. Следовательно, наиболее разные множества здесь: либо 1 и 2, либо 2 и 3. Нужен алгоритм, который либо найдет все пары, либо по заданному множеству, найдет самое отличающееся от заданного.

[Mrrl]

Станислав Агарков: Я привёл пример, в котором M=5 (каким было N, неизвестно). Есть два набора-кандидата, множества в каждом из них как-то пересекаются, какие-то элементы принадлежат двум множествам, какие-то трём... некоторые могут не принадлежать никому. Какова мера "пересекаемости"?
И если даже говорить о парах множеств - какая лучше: ({1,2},{1,2,3}) или ({1,2,3,4,5,6,7,8},{6,7,8,9,10,11,12,13})?

[Станислав Агарков]

Mrrl: Видимо определить правильную меру пересекаемости и есть суть вопроса... Может быть составить таблицу, где для каждой пары множеств посчитать, например, число различий и потом выбрать по ней уже. Я сначала не думал, что это важно, но теперь вижу: в моей задаче все множества одинакового размера, поэтому задача упрощается.

[Mrrl]

Станислав Агарков: Так вы ищете только пары? Какого порядка N, размер множества, и число элементов в их объединении?

[Станислав Агарков]

Все в пределах нескольких десятков.

Answer 1

[Axian Ltd.]

Люблю такие вопросы - ответ - есть, как минимум 1. Ответ засчитан? ;-)

Comments

[Станислав Агарков]

Где есть ответ?

[Axian Ltd.]

Вопрос был - если ли алгоритм? Ответ - да, есть. Это же математика, сэр. Отвечая на незаданный вопрос - полный перебор всегда есть, если нет желания изучать математику.

Answer 2

[sivabur]

Есть берешь первый элемент удаляешь его в втором множестве и так далее) в итоге во втором множестве будет все элементы которые не пересекаться с первым.