Один алгоритм

[max(Im)]

Пусть у нас есть какое-то семейство подмножеств некоторого множества. Каким алгоритмом можно выбрать в каждом подмножестве семейства по одному элементу так, что все элементы будут выбраны? Условие на количество пусть соблюдается.
Чем-то похоже на задачу паросочетания, но что-то не получается...

[gris]

Что за условие на количество? Что количество подмножеств должно равняться числу элементов? Множество-то конечное?
То есть в бинарной квадратной матрице надо оставить по одной единичке в каждом столбце и каждой строке?
Или это не программистская задача?

[max(Im)]

Да, именно то, что вы сказали про матрицу

[svv]

Задача может не иметь решения, например:
Множество $U=\{1,2,3,4\}$, его подмножества $A=\{1\}, B=\{2\}, C=\{1, 2\}, D=\{3, 4\}$.
Лишь один из элементов $3$, $4$ может быть выбран описанным способом.
При этом условие на количество соблюдено: 4 элемента и 4 подмножества.

[max(Im)]

Имелось в виду что исходное множество - объединение всех. Да и вообще существование решения предполагается

[svv]

И у меня оно -- объединение всех, разве нет?
Но если предполагается существование решения, то ладно.

[venco]

max(Im) в сообщении #506563 писал(а):

Чем-то похоже на задачу паросочетания, но что-то не получается...

Почему не получается?

[max(Im)]

Хм... Кто его знает. Нечто жадное не работает.
Можно сначала выбрать те столбцы, которые содержат по 1 единице. А как дальше?

[venco]

max(Im) в сообщении #506619 писал(а):

Хм... Кто его знает. Нечто жадное не работает.
Можно сначала выбрать те столбцы, которые содержат по 1 единице. А как дальше?

Так жадное и не обязано работать. Bipartite matching немного сложнее.

[max(Im)]

Ну вот скажите, я разве говорил, что оно должно работать?
Эх...

[venco]

max(Im) в сообщении #506631 писал(а):

Ну вот скажите, я разве говорил, что оно должно работать?
Эх...

Вы сказали, что задача паросочетания (bipartite matching) не подходит. Я спросил, почему вы так решили, ведь ваша задача - один в один bipartite matching.
Как выяснилось, вы неправильно её решали. Bipartite matching не решается жадным алгоритмом.