Все действительные комбинации очков наиболее эффективным способом

Question

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

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

Учитывая N кортежей из двух целых чисел (давайте теперь будем называть их точками, хотя они не в моем случае использования. Хотя они примерно связаны с X / Y), мне нужно вычислить все действительные комбинации для данного правила.

Правило может быть что-то вроде

• «Каждая включенная точка исключает любую другую точку с такой же координатой X»
• «Каждая включенная точка исключает любую другую точку с нечетной координатой X»

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

• Множество точек (N) начинается с малого, но вскоре перерастает 64 (для решений «использовать как битовую маску»)
• Я делаю это в C #, но решения на любом языке должны быть хорошими, если они объясняют основную идею

Спасибо.

---

Обновление в ответ на ответ Влада:

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

• «Каждая включенная точка исключает любую другую точку в треугольнике выше выбранной точки»

По этому правилу и выбрав (2,1) я бы исключил

• (2,2) - прямо над
• (1,3) (2,3) (3,3) - следующая строка
• и т. Д.

Так что правила фиксированные, а не общие. К сожалению, они более сложны, чем образцы X / Y, которые я первоначально дал.

Answer 1

Как насчет "координата x каждой включенной точки является точной суммой некоторого подмножества координат y других включенных точек". Если вам удастся придумать быстрый алгоритм для этой простой задачи об ограничениях, тогда вы действительно станете очень знаменитыми.

Суть в том, что заявленная проблема настолько расплывчата, что допускает NP-завершенные или NP-сложные задачи. Задачи оптимизации ограничений: невероятно сложны ; если вы не можете поставить очень жесткие рамки на проблему, то она очень быстро становится не анализируемой машинами за полиномиальное время.

Answer 2

Мое понимание проблемы таково: учитывая метод bool property( Point x ) const, найдите все точки, множество которых для свойства () равно true. Это разумно?

Подход грубой силы состоит в том, чтобы пропустить все точки через property() и сохранить те из них, которые возвращают true. Временная сложность этого будет O( N ), где (a) N - общее количество баллов, и (b) метод property() - O( 1 ). Я думаю, вы ищете улучшения от O( N ). Это правильно?

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

Answer 3

Для некоторых специальных типов правил ваша задача кажется простой. Например, для вашего примера правила № 1 вам нужно выбрать подмножество всех возможных значений X, а затем для каждого значения из подмножества назначить произвольный Y.

Для общих правил Я сомневаюсь, что возможно построить эффективный алгоритм без ИИ.