Алгоритм для покрытия множества k-комбинаций M с подмножествами M

Question

Я работаю над приложением, для которого я хочу взять множество C всех возможных k-комбинаций элементов в M (с || M | | = m) и накрываем C множествами k-комбинаций подмножеств N_i из M, причем || N_i || = n < m ∀ N_i

Итак, есть (m выбрать k) комбинации для покрытия, и каждый набор Q_i из n элементов будет содержать (n выбрать k) комбинации.

То, что я хотел бы это алгоритм, который строит множества Qi такие, что д минимизируется (т.е., как можно ближе к (м выберите к)/(п выбирают к), как это возможно)

Так, например, , если m = 100, k = 3 и n = 10, мне понадобится наименьший набор множеств из 10 элементов, чтобы их соответствующие наборы 3-комбинаций покрывали множество (100 выбирают 3) 3-комбинации M.

Answer 1

Я пересекаю отправленный this question on Math Overflow

оказывается, что это хорошо протоптанной проблема в комбинаторике под названием покрытие дизайн про blem.

Существует, как правило, алгоритм, который гарантирует минимум, хотя существуют алгоритмы, которые близки к минимуму. Вы можете найти существующие известные покрытия и исследования here

Answer 2

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

1. Вывод всех K-указателей в хорошем формате для любого N выбирает K в файл. K-индексы могут быть заменены более описательными строками или буквами. Этот метод позволяет решить этот тип задачи довольно тривиально.

2. Преобразует K-индексы в соответствующий индекс записи в таблице отсортированных биномиальных коэффициентов. Этот метод намного быстрее, чем более старые опубликованные методы, основанные на итерации. Он делает это, используя математическое свойство, присущее Треугольнику Паскаля. В моей статье говорится об этом. Я считаю, что я первый, кто открыл и опубликовал эту технику, но я мог ошибаться.

3. Преобразует индекс в таблицу отсортированных биномиальных коэффициентов в соответствующие K-индексы.

4. Использование метода Mark Dominus для вычисления биномиального коэффициента, который значительно реже переполняется и работает с большими числами.

5. Класс написан на .NET C# и предоставляет способ управления объектами, связанными с проблемой (если есть), используя общий список. Конструктор этого класса принимает значение bool, называемое InitTable, которое, когда true, создаст общий список для хранения объектов, которые будут управляться. Если это значение ложно, то оно не создаст таблицу. Таблицу не нужно создавать, чтобы выполнить описанные выше методы. Для доступа к таблице предоставляются методы доступа.

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

Чтобы прочитать об этом классе и загрузить код, см. Tablizing The Binomial Coeffieicent.

Это не должно быть сложно преобразовать этот класс на выбранный вами язык.

Из вашего описания проблемы, похоже, что вы должны установить один цикл для N (другой для K, если он также изменится), а затем создать объект биномиального коэффициента (BC) для этой комбинации N, K. Вызовите беззначную длинную версию GetBinCoeff() с объектом BC, чтобы получить общее количество комбинаций. Затем настройте еще один цикл, чтобы пройти общее количество комбинаций каждого объекта BC. Внутри этого цикла вызовите метод BC GetKIndexes, чтобы получить K-индексы для каждого индекса (например, комбинацию), а затем выполните ваши вычисления. Я не совсем уверен, что вы пытаетесь свести к минимуму. Если мое предложение недостаточно ясное или полезное, попробуйте опубликовать более подробный пример, который четко показывает результаты, которые вы ищете.