Как найти все наборы столбцов матрицы, которые вместе содержат значение для каждой строки?

Question

Учитывая матрицу логических значений (пример):

    a  b  c
  +--------
X | 1  0  1  
Y | 1  1  1
Z | 0  1  1
  +--------

Каков оптимальный способ найти все последовательности [a | b | c], чтобы каждая последовательность имела хотя бы одно «истинное» (1) значение для каждого из X, Y и Z.

В приведенном выше примере набор последовательностей (в произвольном порядке):

  abc, ab, ac, bc, c

Принимая во внимание, что эти последовательности не удовлетворяют требованию:

  a (doesn't provide Z)
  b (doesn't provide X)

Я на самом деле ищу обобщенный алгоритм для произвольной матрицы.

Есть идеи?

Answer 1

1. Получить последовательность, которая НЕ для каждой строки.
2. Определите все подпоследовательности этих последовательностей.
3. Ваш ответ - все оставшиеся последовательности.

По сути, вы берете объединение (последовательности, которые не предоставляют X) и (последовательности, которые не предоставляют Y) и (последовательности, которые не предоставляют Z), и принимаете дополнение этого набора .

Я думаю, что это обобщает.

Answer 2

В основном вы решаете X & Y & Z, где X = a | c, Y = a | b | c, Z = b | c для a, b и c.

Таким образом, в основном вы ищете все решения SAT по формуле в конъюнктивной нормальной форме . Хотя существуют некоторые упрощения, в основном любой подход будет O (2 ^N ). Алгоритмы эффективного поиска решения этого класса проблем перечислены в статье в википедии ; однако, если вам нужны все решения, вы все равно будете перебирать 2 ^N возможностей, поэтому достаточно просто перечислить их и протестировать.

Несколько тривиальных оптимизаций:

• в формуле нет отрицаний, поэтому, если у вас есть решение, то добавление любой другой переменной к этому решению также будет решением. Ваш ОП говорит, что вы хотите все решения; для больших матриц будет много решений, основанных на той же самой необходимой основе и всех выборках ненужных значений.
• если вы and все значения в столбце и получите 1, то этот столбец является основой для решения (этот столбец и любой выбор других столбцов является решением)
• если вы or все значения в столбце и получите 0, то этот столбец не влияет на основу какого-либо решения
• подходы, основанные на объединении наборов для поиска баз (добавление столбца к набору, если он выбирает строку, которая не выбрана), могут быть лучше, чем подходы, находящие все решения
• если вы подходите к объединению множеств, которые решают / действительно решают проблему - объединению нерешений или пересечению решений - может быть лучше разделить строки на две и использовать положительный подход для строк с несколько единиц, и отрицательный подход для строк с несколькими нулями.

Поскольку это проблема 2 ^N , разумно предположить, что N <64, и поэтому вы можете сделать некоторые оптимизации реализации, но вы не уменьшите размер проблемы. </p>

Answer 3

Вы можете определить множество, удовлетворяющее X (a, ab, ac, abc, bc, c), пересечь его с множеством, удовлетворяющим Y (a, ab, ac, abc, b, bc, c), ипересеките результат с множеством, которое заполняет Z (ab, ac, abc, b, bc, c) и т. д.

Для больших матриц вы можете использовать схему «разделяй и властвуй» из этой операции: выполните половину условийи определить их наборы, взять другую половину условий и определить их наборы, и пересечь оба набора.Повторите для обеих частей ...

Answer 4

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

Так в псевдокоде:

validSequence(vector<columns> cols, vector<columns> sequence)
    // base case for recursion
    if (cols.empty)
        if (validSequence(sequence))
            printSequence(sequence)
        else
            // invalid sequence
    // now we recurse using the next row and not using the next row
    column nextRow = pop(cols)
    validSequence(cols, sequence)
    sequence.push(nextRow)
    validSequence(cols, sequence)

Очевидно, вам все еще нужно реализовать функцию validSequence(sequence), но я почти уверен, что это сработает

Надеюсь, это поможет вам

Answer 5

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

graph G {

A -- X;
A -- Y;
B -- X;
B -- Y;
C -- X;
C -- Y;
C -- Z;

}

ABC может достигать XYZ До н.э. может достичь XYZ AC может достичь XYZ AB может достичь XYZ C может достигать XYZ

A НЕ МОЖЕТ достигать XYZ B не может достичь XYZ

http://rollerjm.free.fr/pro/graphs.html