Подмножество и комплект обложки

Question

Нам дается ряд замков, и для открытия этих замков нам нужно именно тот набор людей, чтобы открыть этот замок. Учитывая количество людей, которых у нас есть, и количество блокировок, которые необходимо открыть, нам нужна спецификация того, как распределять ключи среди доступных людей, так что любое количество требуемых людей, чтобы открыть эту блокировку, может открыть ее, но без группы это число необходимых людей может открыть его.

Число людей, будет находиться в диапазоне 1-9 и количество людей, необходимых, чтобы открыть замок будет находиться в диапазоне 0-9

Рассмотрим следующие примеры

Количество людей, доступных = 2

Количество требуемых = 1 Ans: {{0}, {0}}

Любой из них может открыть его, так что они оба дали одни и те же ключи.

Количество людей доступно = 5

Количество требуемых = 3

Ans: {{0, 1, 2, 3, 4, 5}, {0, 1, 2, 6, 7 , 8}, {0, 3, 4, 6, 7, 9}, {1, 3, 5, 6, 8, 9}, {2, 4, 5, 7, 8, 9}}

Может кто-то, пожалуйста, помогите мне, как это сделать.

Спасибо

Answer 1

Пусть п быть общее число людей, и пусть м быть желательно минимальное количество людей, чтобы открыть все замки.

Тогда есть два требования:

• Для каждого замка, любой набор м люди должны содержать по крайней мере один человек с ключом к этому замку. Другими словами, набор людей без данный ключ должен содержать меньше чем m человек. Таким образом, каждый ключ должен быть распределен по меньшей мере до n   -   m   +   1 человек.
• Для каждого набора m   −   1 человек, должен быть хотя бы один замок, к которому у каждого из них нет ключа. Другими словами, если вы перевернуть это на взгляд на «всех остальных» набор, который имеет п   -   м   +   1 человек, вы можете сказать, что для любого множества п   -   m   +   1 человек, должен быть хотя бы один ключ, который только принадлежит этому набору.

Соединяя эти два требования вместе, мы фактически имеем отображение взаимно-однозначное соответствие между (клавиши) и (наборы п   -   м   +   1 человек).

Так что вам просто нужно найти все наборы н   -   м   +   1 человек (что тривиально сделать в O (2 ^п) времени, и не слишком трудно делать в O (с (п,   п   -   м   +   1)) времени). Для каждого набора создайте ключ и распределите его для людей в этом наборе.