Разделение N элементов на подмножества k-размера

Question

Если у меня есть N разных чисел, они должны быть разделены на подмножества k-размеров, так что каждое подмножество будет иметь как минимум один общий элемент. Пожалуйста, помогите мне с алгоритмом. вывод должен быть какой-то вещи, как этот , если у меня есть элементы от 1 до 5 и k = 3 то вывод должен быть:

- S0 = {0, 1, 2} 
- S1 = {1, 3, 5} 
- S2 = {2, 4, 5} 
- S3 = {0, 3, 4} 
- S4 = {1, 4, 6} 
- S5 = {0, 5, 6} 
- S6 = {2, 3, 6} 

Answer 1

1) Обратите внимание, что если k = 1 и |S| > 1 то это невозможно (т.е. k = 1 и S = {1,2})

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

По вашему примеру k = 3 и S = {0,1,2,3,4,5,6} мы могли бы сделать:

• S0 = {0,1,2} (первый номер + рядом 2)
• S1 = {0,3,4} (первый номер + следующий 2 после 1,2)
• S2 = {0,5,6} (в данном случае нам повезло, так как мы смогли заполнить S2, иначе он должен быть только для 0 .. 5, мы можем добавить случайное число в качестве последнего)

Answer 2

Ваш пример из 7 пунктов (0, ..., 6) и 7 "строк" (например, «строка» {0,1,2}). Обратите внимание, что любые две линии «пересекаются» в точке, а любые две точки определяют прямую. (Выберите два числа из 0, ..., 6, и вы увидите, что есть только один набор с обоими этими номерами.)

Таким образом, дизайн, который вы представили, имеет больше ограничений, чем описано. Если вы просто хотите, чтобы каждый пара подмножеств иметь по крайней мере один общий элемент, вы могли бы поставить 0 в каждый набор и получить C подмножества {0,1,2}, {0,1 , 3}, {0,1,4} и т. Д., Что совсем не сложно.

Геометрический язык точек и линий не является совпадением. Если вам нужен дизайн, где каждая пара подмножеств имеет ровно один общий элемент, вам, вероятно, нужен проекционный самолет . Пример, который вы дали, называется Fano plane. Проективные плоскости невозможны для всех комбинаций N и k. Вы должны иметь N = m^2 + m + 1 и k = m + 1, где m называется порядком плоскости. Проективные плоскости легко построить «конструкцией векторного пространства» для m prime с использованием модулярной арифметики (например, m = 2 дает плоскость Фано). Их немного сложнее построить для m степенью простого числа, m = p^k, используя конструкцию векторного пространства и конечные поля. Подробности можно найти во многих разных ссылках.

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

Это то, что вы хотите? Если нет, существуют и другие «комбинаторные конструкции блоков», которые могут обладать свойствами, которые вы хотите, но вы должны быть точными с вашими требованиями.