Как мне перечислить и дедуплицировать 9 элементов, выделенных в триплетах для каждого из 3 наследников ... и далее?

Question

Этот вопрос относится к контексту, описанному в В поисках решения или эвристического приближения для комбинаторной ситуации с 3 разделами .Задача состоит в том, чтобы распределить приблизительно 48 единиц унаследованных драгоценностей, каждое из которых имеет свою оценочную стоимость, среди 3 наследников, чтобы дать каждому наследнику равную или почти равную ценность.На этот вопрос был дан достаточный ответ для моих законных целей.

Этот новый вопрос возникает из-за моей попытки решить это путем перечисления.Совершенно ненужно по закону.Теперь просто интеллектуальный вызов.

Проблема сейчас:

Присвойте каждому элементу уникальный индекс: вероятно, только целые числа от 1 до 48. Теперь распределите эти 48 каждому из 3 наследников и устранитедубликаты.

Чтобы упростить этот пример, подтвердите, что имеется только 9 предметов, и каждый наследник должен получить ровно 3 предмета.(Обратите внимание, что это расходится с предыдущей целью сделать 3 ячейки почти равными значениями.)

Как устранить дубликаты в последовательности элементов к корзинам?

Пример:
Пусть в корзине 1 содержатся элементы {1,2,3}
Пусть в корзине 2 содержатся элементы {4,5,6}
Пусть в корзине 3 содержатся элементы {7,8,9}

Будет 6 дубликатов конечных значений этого триплета триплетов:
{1,2,3} {4,5,6} {7,8,9}
{4,5,6} {1,2,3} {7,8,9}
{4,5,6} {7,8,9} {1,2,3}
{7,8,9} {1,2,3} {4,5,6}
{7,8,9} {4,5,6} {1,2,3}
и т. Д.

Опять же, как устранить дубликаты в последовательности элементов к корзинам?Не перечисляя весь набор перестановок триплетов.Нет, это не совсем верно.Возможно, мне придется временно отшлифовать все триплеты.Как быстро устранить дублированные комбинации триплетов, основываясь на том, что было сделано априори?

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

Я поставил исходный вопрос о mathoverflow.Я прошу прощения за то, что не понял взаимосвязи между stackoverflow и mathoverflow.

Answer 1

Можно показать, что общее количество ограниченных разделов составляет

, что равно 280.

Это можно изменить следующим образом:

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

С Mathematica вы можете сгенерировать это как:

list = Range[9];
l1 = Subsets[list, {3}, Binomial[9, 3]/3];
l2 = Subsets[Complement[list, #], {3}, Binomial[6, 3]/2] & /@ l1;
Flatten[
  Outer[
    Function[{ll1, ll2}, {ll1, ll2, Complement[list, ll1, ll2]}], 
    {#1}, #2, 1, 1
  ] & @@@ ({l1, l2}\[Transpose]), 
2]

Answer 2

Это хороший вопрос.По сути, это проблема разделов с ограниченным набором.

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

Я буду использовать фигурные скобки для представления списков, как это мне знакомо.

Начните с этого шаблона, который представляет ноль элементов в трех бинах:

{ {{}, {}, {}} }

Для каждого списка в самом внешнем (то есть просто {{}, {}, {}} здесь):

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

2. Сохраните копию всего списка для каждой произведенной замены и объедините их вместе в конце шага.

Этот процесс будет повторяться для 2, 3 и т. Д., Пока все элементы не будут в ячейках или все ячейки не заполнятся.Примеры шагов:

{ {{}, {}, {}} }

{ {{1}, {}, {}} }

{ {{1, 2}, {}, {}}, {{1}, {2}, {}} }

{ {{1, 2, 3}, {}, {}}, {{1, 2}, {3}, {}}, {{1, 3}, {2}, {}}, {{1}, {2, 3}, {}}, {{1}, {2}, {3}} }

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