Выбор n наборов целых чисел, которые максимизируют число n-значных перестановок, удовлетворяющих произвольному условию

Question

Скажите, что у вас есть список всех n-значных чисел, удовлетворяющих определенному произвольному условию. Теперь вы хотите выбрать один набор из k цифр для каждой из n цифр, которые могут быть использованы для создания наибольшего числа n-значных чисел в вашем списке. Таким образом, общее число перестановок будет k^n.

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

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

EDIT: вот пример того, что я имею в виду. Пусть n = 2 и k = 4, то есть я хочу, чтобы программа находила два списка, каждый из которых содержит 4 цифры. Объединив одну цифру из первого списка с одной цифрой из второго списка, вы можете создать двузначный номер. Например, пусть list1 = {0,1,4,7} и list2 = {0,2,3,8}. Набор двухзначных чисел, которые я могу создать с этими двумя списками, - {00,02,03,08,10,12,13,18,40,42,43,48,70,72,73,78}.

Теперь у меня есть произвольное условие, которое проверяется некоторой внешней функцией, скажем, в этом случае это то, является ли двузначное число простым. Для перечисленных выше списков подмножество двухзначных чисел, которые я могу создать, удовлетворяющих этому условию, {02,03,13,43,73}.

У меня есть две отдельные цели:

1. Написать программу, которая может определить, какие цифры в list1 и list2 произведет наибольший возможный набор двузначных чисел, удовлетворяющих уравнению мое. Например, если я изменяю list2, так что теперь это {1,3,7,9}, тогда набор двузначных простых чисел, которые я могу создать, становится {01,03,07,11,13,17,19,41, 43,47,71,73,79}. Таким образом, в этом случае (при условии, что я прав) число равно 13.

2. Напишите программу, которая может определить, какие цифры в списке1 и list2 будут производить набор двузначных чисел с наибольшим соотношением элементов, которые удовлетворяют моему состоянию элементам, которые этого не делают. Для примера с новыми значениями list2 отношение равно 13/16, потому что 09, 49 и 77 не являются первичными.

Answer 1

Редактировать: Этот ответ не является полным, но может управлять другими в правильном направлении.

Во-первых, перечисление всех значений, удовлетворяющих требуется:

Любой алгоритм будет проверять п-значных чисел в определенном порядке, чтобы увидеть, если они удовлетворяют условию. Предположим, что алгоритм проверяет числа n1, n2, n3, ...

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

Отношение к проблеме Maximum Density Subgraph:

Эта задача эквивалентна нахождению максимальной плотности подграф в многодольного графа.

Мы можем преобразовать экземпляр проблемы в многогранный граф следующим образом. Каждому независимому набору в графе соответствует десятичное место, и каждая вершина соответствует возможному значению в этом знаке после запятой. Например, при n = 2 первый независимый набор будет 0_, 1_, 2_, ..., а второй независимый набор будет _0, _1, _2, ...,. Края соответствуют удовлетворяющим значениям. Например, если все простые числа удовлетворяют, мы будем иметь ребра (0_, _ 2), (0_, _ 3), ..., (1_, _1) ... и т. Д.

Теперь выбирая k цифр для каждый из n знаков после запятой эквивалентен выбору k узлов из каждой из частей графика. Мы хотим сделать этот выбор, чтобы максимизировать количество ребер, сохраненных в конечном графе, или максимизировать долю ребер до не-ребер. Это то же самое, что и поиск подграфа с максимальной плотностью при описанном ограничении.

Как описано в связанной статье, Подграф с максимальной плотностью является NP-Hard. Эта проблема может быть немного проще из-за структурных ограничений на графике и ограничить до 10 узлов на часть, но я не уверен. У меня такое чувство, что проблема может быть NP-Hard.