Воссоздать наборы из комбинаций этих наборов

Question

Я столкнулся с конкретной проблемой и искал какой-то алгоритм для нее. Решаемая проблема описана ниже.

Допустим, у нас есть комбинации, как показано ниже

1 - 3 - 5

1 - 4 - 5

1 - 8 - 5

2 - 4 - 5

3 - 4 - 5

2 - 4 - 7

Эти комбинации были сгенерированы из заданных наборов, в данном конкретном случае, скажем, из

{1}, {3,4,8}, {5}

{2,3}, {4}, {5} * * тысяча двадцать-один * * {Тысяча двадцать-дв 2}, {4}, {7} * * тысяча двадцать-три

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

1-й раствор

{1}, {3, 4, 8}, {5}

{2, 3}, {4}, {5}

{2}, {4}, {7}

2-й раствор

{1}, {3, 8}, {5}

{1, 2, 3}, {4}, {5}

{2}, {4}, {7}

3-й раствор

{1}, {3, 4, 8}, {5}

{3}, {4}, {5}

{2}, {4}, {5, 7}

Но окончательным (оптимальным) решением будет решение с как можно меньшим набором или случайное решение, если все они эквивалентны с точки зрения количества наборов.

Существуют ли алгоритмы для такой проблемы? Я ценю, если кто-нибудь, кто имел дело с такой проблемой, может дать мне несколько советов.

РЕДАКТИРОВАТЬ: похоже, что я ищу, это разложение n-арного продукта (декартово произведение для N)

РЕДАКТИРОВАТЬ: после дополнительных исследований по этой теме я обнаружил, что проблема известна в «теории графов» как проблема «минимального покрытия клики»

С уважением, Баз

Answer 1

Это не совсем ответ, скорее расширенный комментарий. Ваши «сжатые представления» на самом деле вообще не экономят места.

В несжатом представлении вы храните:

• правило, которое гласит, что каждая группа состоит из 3 символов; и
• 18 (в вашем примере) символов.

Это может быть сохранено в 1R + 18S (где R - пространство, необходимое для хранения правила, S - пространство, необходимое для хранения символа)

В ваших предполагаемых сжатых представлениях вы должны хранить:

• правило, которое гласит, что каждая группа состоит из 3 наборов символов;
• символы в каждом наборе; и
• другой символ, который отделяет каждый набор от следующего.

В вашем первом «сжатом» представлении я считаю 1R + 12S + 8D (где D - пространство, необходимое для хранения одного разделителя). Если S == D, то это 1R + 20S - больше, чем ваше несжатое представление.

В двух других ваших «сжатых» представлениях я считаю одинаково: 1R + 12S + 8D и 1R + 12S + 8D.

Я не выяснил, является ли это отсутствие сжатия существенной особенностью вашего предложения или случайной особенностью выбранного вами примера.

Вы имеете в виду, когда вы пишете, что

количество элементов в комбинации на самом деле N

что некоторые комбинации будут иметь 3 элемента, другие 4, другие 2 или 5 и т. Д.?

Предлагаю вам уточнить свой вопрос.

РЕДАКТИРОВАТЬ: @bazeusz: теперь кажется, что вы ищете декартово произведение наборов.