Найти подмножество с различными значениями для каждого столбца

Question

Для простой таблицы, подобной этой:

+---------+---------+---------+
| Column1 | Column2 | Column3 |
+---------+---------+---------+
| A       | J       | Q       |
| A       | K       | S       |
| B       | M       | R       |
| B       | N       | S       |
| B       | J       | Q       |
| C       | K       | R       |
| D       | J       | R       |
| D       | J       | Q       |
| E       | L       | Q       |
+---------+---------+---------+

Можно ли определить, есть ли в этой таблице подмножество из N строк, так что для каждого столбца все N значений различны?

Например, при N = 3 ответом будет да

+---------+---------+---------+
| Column1 | Column2 | Column3 |
+---------+---------+---------+
| A       | J       | Q       |
| B       | N       | S       |
| C       | K       | R       |
+---------+---------+---------+

Существует ли простой алгоритм для решения такого вопроса?

Answer 1

Существует ли простой алгоритм для решения такого вопроса?

Ответ на этот вопрос строго "да"; Вы можете выполнить поиск методом грубой силы по всем (R выберите K) подмножествам K строк, где R - количество строк во всей таблице. Этот алгоритм довольно прост и может быть реализован в несколько строк на таком языке, как Python.

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

Сокращение выглядит следующим образом: для данного графика построить таблицу с одной строкой для каждой вершины. Для каждого ребра на графике добавьте один столбец в таблицу; в этом столбце напишите одну и ту же букву в двух строках, к которым присоединяется ребро, а затем напишите разные другие буквы в каждой из оставшихся строк для этого столбца. Результирующая таблица содержит V строк и E столбцов, поэтому ее размер является полиномиальным по размеру исходного графа и строится за полиномиальное время.

Затем любой набор из K строк, имеющих разные значения в каждом столбец дает K вершин в исходном графе, не связанных ни одним ребром. Это означает, что если вы можете ответить да / нет на то, существует ли такой набор из K строк за полиномиальное время, то вы также можете ответить на форму решения задачи о максимальном независимом наборе за полиномиальное время. Последний является NP-полным, поэтому ваша задача - NP-hard.

Answer 2

Простым решением будет просто поиск (возврат).

Но каждый инструмент / библиотека, решающая проблему CSP (проблема удовлетворения ограничений) может найти решение.

Answer 3

Поскольку вы явно запрашиваете алгоритм , чтобы решить эту проблему:

Если я правильно понимаю проблему (вы используете здесь N два раза, первый раз для строк, а второй время для значений, что немного сбивает с толку), вы хотите найти N строк со ВСЕМИ РАЗЛИЧНЫМИ значениями в данной таблице.

Я бы начал так:

1. Создать данные структура для поиска, если вы уже нашли значение (например, hashmap)
2. Создайте структуру данных для хранения ваших строк результатов, которые соответствуют условию соответствия (все значения разные)
3. Итерация ввода строк таблицы, пока вы не достигнете желаемого размера подмножества или не достигнете конца таблицы
4. Начните с первой строки
5. Во время итерации строки проверяйте каждое значение, если оно находится в вашем структура (создана в 1.), если да -> abort, иначе добавьте значение в lookup-структуру. Когда все значения строк проверены, эта строка в порядке и может быть добавлена ​​к вашему набору результатов.
6. Повторять следующую строку, если она существует

Но, как указано в комментарии, этот алгоритм жадный, который не всегда найдет возможное решение