Быстрый алгоритм для проверки возможности вращения двоичных массивов, чтобы не иметь элементарной суммы над 1

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

Например, допустим, у меня есть следующие три массива: [1, 0, 0, 0], [1, 0, 1, 0] и [1, 0, 0, 0]. Я могу повернуть второй массив на один элемент, а третий - на два элемента, чтобы получить массивы [1, 0, 0, 0], [0, 1, 0, 1], [0, 0, 1, 0] элементарная сумма которого равна [1, 1, 1, 1]. Однако, если бы я не применял вращения, я бы получил сумму [3, 0, 1, 0], которая не соответствует моим требованиям, поскольку один из элементов (3) больше 1.

Теперь, мой вопрос: что такое быстрый способ определить, возможно ли это для произвольного числа массивов? Например, нет возможности повернуть [1, 0, 0, 0], [1, 0, 1, 0], [1, 0, 1, 0] так, чтобы элементы суммы не превышали 1.

Текущая эвристика

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

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

Ответы

Ответ 1

Вы можете уменьшить эту проблему до конкретной проблемы с крышкой и использовать один из известных алгоритмов для точного покрытия (алгоритм Кнута X, целочисленное линейное программирование, SAT-решение, поскольку саша напоминает мне, возможно, другие). Сокращение включает в себя создание всех поворотов каждого входного массива и расширение их с помощью индикатора, чтобы гарантировать, что выбрано ровно одно вращение. Например, для экземпляров [1, 0, 0, 0], [1, 0, 1, 0], [1, 0, 0, 0], точный экземпляр

[1, 0, 0, 0; 1, 0, 0]  # from [1, 0, 0, 0]
[0, 1, 0, 0; 1, 0, 0]
[0, 0, 1, 0; 1, 0, 0]
[0, 0, 0, 1; 1, 0, 0]
[1, 0, 1, 0; 0, 1, 0]  # from [1, 0, 1, 0]
[0, 1, 0, 1; 0, 1, 0]
[1, 0, 0, 0; 0, 0, 1]  # from [1, 0, 0, 0]
[0, 1, 0, 0; 0, 0, 1]
[0, 0, 1, 0; 0, 0, 1]
[0, 0, 0, 1; 0, 0, 1]
[1, 0, 0, 0; 0, 0, 0]  # extra columns to solve the impedance mismatch
[0, 1, 0, 0; 0, 0, 0]  # between zeros being allowed and exact cover
[0, 0, 1, 0; 0, 0, 0]
[0, 0, 0, 1; 0, 0, 0]

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

EDIT: да, эта проблема NP-hard. Там простое сокращение от 3-раздела, которое я продемонстрирую на примере.

Предположим, что экземпляр 3-раздела является [20, 23, 25, 45, 27, 40]. Затем мы создаем двоичный массив

[1, ..(20 ones in total).., 1, 0, ..., 0]
[1, ..(23 ones in total).., 1, 0, ..., 0]
[1, ..(25 ones in total).., 1, 0, ..., 0]
[1, ..(45 ones in total).., 1, 0, ..., 0]
[1, ..(27 ones in total).., 1, 0, ..., 0]
[1, ..(40 ones in total).., 1, 0, ..., 0].

Мы ищем раздел, где каждая из двух частей суммируется до 90, поэтому последний массив является "трафаретом",

[1, 0, ..(90 zeros in total).., 0, 1, 0, ..(90 zeros in total).., 0]

который обеспечивает ограничение 3-раздела.

Ответ 2

~~Я все еще не определился с вопросом, есть ли эта проблема в P или NP-hard.~~ ~~Разумеется, существует много математической структуры для использования.~~ , См. Ответ Дэвида.

Но пока кто-то еще не придет с хорошим решением, здесь что-то, что будет работать в теории и может также на практике.

Основная идея: сформулировать ее как проблему SAT и использовать очень эффективные решатели для такого рода комбинаторных задач.

Решатель SAT-solver, который мы используем здесь, - это решатели на базе CDCL, которые являются полными и надежными (они найдут приемлемое решение или доказательство, что их нет!).

Анализ (наивный подход)

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

Формулировка так же проста, как и получается:

N * M двоичные переменные:
- N marks the data-row; M the roation/shift value
A: препроцесс всех возможных парных конфликтов
B: добавить ограничения, по которым используется по крайней мере одна конфигурация каждой строки
C: добавить ограничения, запрещающие конфликты.

Для N=100 строк M=100 cols будет 4950 упорядоченных пар, каждая из которых умножается на M*M (pairwise rotation-combinations). Таким образом, существует <= 4950 * 100 * 100 = 49.500.000 проверок конфликтов (что даже возможно на медленных языках). Это также верхняя граница числа конфликтов.

Конечно, это может измениться, если у вас есть очень редкие данные, которые позволяют N расти, пока M фиксирован (в мире возможного экземпляра).

Вероятно, возможно много возможных сокращений.

Сообщение о выезде здесь:

Предварительная обработка - это большая работа (асимптотика!), И подход основан на комментарии, длина массива меньше 100
SAT-решение очень быстро связано с распространением, и если P или NP-hard, то виды ограничений, которые мы предоставили, очень эффективны с точки зрения эффективности распространения
Рекомендуется тестирование этого эмпирически (по вашим данным)!

Примечание:

Нет ограничения <= per row и в некоторых случаях могут быть выбраны две конфигурации. Код восстановления решения не проверяет этот случай (но теоретическая проблема отсутствует → просто выберите one => будет совместимым).

Код

from pyCadical import PyCadical  # own wrapper; not much tested; @github
import itertools
import numpy as np

""" DATA """
data = np.array([[1, 0, 0, 0],
                 [1, 0, 1, 0],
                 [1, 0, 0, 0]])

""" Preprocessing """
N = len(data)
M = len(data[0])

conflicts = []
for i, j in itertools.combinations(range(N), 2):
    for rotA in range(M):
        for rotB in range(M):
            if np.amax(np.roll(data[i], rotA) + np.roll(data[j], rotB)) > 1:
                conflicts.append((i, j, rotA, rotB))
conflicts = np.array(conflicts)

""" SAT """
cad = PyCadical()
vars = np.arange(N*M, dtype=int).reshape(N,M) + 1

# at least one rotation chosen per element
for i in range(N):
    cad.add_clause(vars[i, :])  # row0rot0 OR row0rot1 OR ...

# forbid conflicts
for i, j, rotA, rotB in conflicts:
    cad.add_clause([-vars[i, rotA], -vars[j, rotB]])  # (not rowIrotA) or (not rowJrotB)

""" Solve """
cad.solve()

""" Read out solution """
sol = cad.get_sol_np().reshape(N, M)
chosen = np.where(sol > 0)

solution = []  # could be implemented vectorized
for i in range(N):
    solution.append(np.roll(data[i], chosen[1][i]))

print(np.array(solution))

Выход

[[0 1 0 0]
 [1 0 1 0]
 [0 0 0 1]]

Ответ 3

Я буду рассматривать каждый набор бит как (достаточно большой) Integer.

Скажем, у меня такой набор целых чисел на n бит. Вот несколько кода Squeak Smalltalk, которые показывают, как немного уменьшить комбинаторный:

SequenceableCollection>>canPreventsOverlapingBitByRotatingOver: n
    "Answer whether we can rotate my elements on n bits, such as to obtain non overlaping bits"
    | largestFirst nonNul nonSingletons smallest |

    "Exclude trivial case when there are more than n bits to dispatch in n holes"
    (self detectSum: #bitCount) > n ifTrue: [^false].

    "Exclude non interesting case of zero bits"
    nonNul := self reject: [:each | each = 0].

    "Among all possible rotations, keep the smallest"
    smallest := nonNul collect: [:each | each smallestAmongBitRotation: n].

    "Note that they all have least significant bit set to 1"
    [smallest allSatisfy: [:each | (each bitAnd: 1) = 1]] assert.

    "Bit singletons can occupy any hole, skip them"
    nonSingletons := smallest reject: [:each | each = 1].

    "Sort those with largest bitCount first, so as to accelerate detection of overlaping"
    largestFirst := nonSingletons sorted: #bitCount descending.

    "Now try rotations: all the shift must differ, otherwise the shifted LSB would overlap"
    ^largestFirst checkOverlapingBitRotated: n

Где мы имеем следующие утилиты, определенные как:

SequenceableCollection>>checkOverlapingBitRotated: n
    "Answer true if the bits of my elements can be rotated on n bits so as to not overlap"
    ^self checkOverlapingBitRotatedBy: (1 << n - 1) among: n startingAt: 2 accum: self first

SequenceableCollection>>checkOverlapingBitRotatedBy: shiftMask among: n startingAt: index accum: accum
    index > self size ifTrue: [^true].
    (shiftMask bitClear: accum) bitsDo: [:bit |
        | shifted |
        shifted := (self at: index) bitRotate: bit lowBit - 1 among: n.
        ((accum bitAnd: shifted) = 0
            and: [self
                    checkOverlapingBitRotatedBy: shiftMask
                    among: n
                    startingAt: index + 1
                    accum: (accum bitOr: shifted)])
            ifTrue: [^true]].
    ^ false

Это требует дополнительного объяснения: каждый бит в shiftMask указывает (ранг) возможный сдвиг. Поскольку накопитель уже занимает несколько бит, а так как LSB каждого элемента равен 1, мы не можем сдвинуть оставшийся элемент на биты, уже занятые аккумулятором. Таким образом, мы должны очистить бит, занимаемый аккумулятором от маски. Это значительно уменьшает комбинации, и поэтому полезно сначала сортировать наибольший бит.

Во-вторых, охранник (accum bitAnd: shifted) = 0 режет рекурсию, как только мы можем вместо создания бесполезных комбинаций и тестирования невозможности апостериор.

У нас есть те небольшие утилиты:

Integer>>bitRotate: shift among: n
    "Rotate the n lowest bits of self, by shift places"
    "Rotate left if shift is positive."
    "Bits of rank higher than n are erased."
    | highMask lowMask r |
    (r := shift \\ n) = 0 ifTrue: [^self].
    lowMask := 1 << (n - r) - 1.
    highMask := 1 << n - 1 - lowMask.
    ^((self bitAnd: lowMask) << r)
        bitOr: ((self bitAnd: highMask) >> (n - r))

Integer>>smallestAmongBitRotation: n
    "Answer the smallest rotation of self on n bits"
    ^self
        bitRotate: ((1 to: n) detectMin: [:k | self bitRotate: k among: n])
        among: n

Integer>>bitsDo: aBlock
    "Evaluate aBlock will each individual non nul bit of self"
    | bits lowBit |
    bits := self.
    [bits = 0] whileFalse: [
        lowBit := (bits bitAnd: 0 - bits).
        aBlock value: lowBit.
        bits := bits - lowBit].

Он мгновенно работает с небольшими коллекциями:

| collec bitCount |
collec := #( 2r11 2r1001  2r1101 2r11011 2r1110111 2r11001101
       2r11010010111010 2r1011101110101011100011).
bitCount := collec detectSum: #bitCount.
(bitCount to: bitCount*2) detect:
    [:n | collec canPreventsOverlapingBitByRotatingOver: n].

ответит 52, это означает, что нам нужно как минимум 52 бита для получения неперекрывающей комбинации, хотя бит-счет составляет всего 44.

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

Это не в случае моего 32-битного интерпретатора, который создает большие большие числа в коробке, оказывает давление на сборщик мусора и занимает немного времени с 10 наборами в общей сложности около 100 бит:

| collec bitCount |
collec := (1 to: 10) collect: [:i | (1 << 18 - 1) atRandom].
bitCount := collec detectSum: #bitCount.
bitCount ->
    [ collec canPreventsOverlapingBitByRotatingOver: bitCount + 10] timeToRun.

Первая попытка заняла 75 секунд для битCount = 88

Более справедливые (редкие) бит-распределения приводят к более быстрому среднему времени (и все еще ужасающему худшему времени):

| collec bitCount |
collec := (1 to: 15) collect: [:i |
    ((1 to: 4) collect: [:j | (1 to: 1<<100-1) atRandom])
        reduce: #bitAnd:].
bitCount := collec detectSum: #bitCount.
bitCount ->
    [ collec canPreventsOverlapingBitByRotatingOver: (bitCount + 10 max: 100)] timeToRun.

104->1083ms
88->24ms    
88->170ms
91->3294ms
103->31083ms