Найдите две пары пар, которые суммируются с одинаковым значением

Ответ 1

Вот "ленивый" подход, который масштабируется до n = 10000, используя "только" 4 ГБ памяти и заканчивая за 10 секунд на звонок или около того. Наихудшая сложность случая - O (n ^ 3), но для случайных данных ожидаемая производительность равна O (n ^ 2). На первый взгляд кажется, что вам нужно O (n ^ 3) ops; каждая комбинация строк должна быть произведена и проверена хотя бы один раз. Но нам не нужно смотреть на всю строку. Скорее, мы можем выполнить раннюю стратегию выхода на сравнение rowpairs, как только станет ясно, что они бесполезны для нас; и для случайных данных мы можем сделать этот вывод обычно задолго до того, как мы рассмотрим все столбцы в строке.

import numpy as np

n = 10
#also works for non-square A
A = np.random.randint(2, size=(n*2,n)).astype(np.int8)
#force the inclusion of some hits, to keep our algorithm on its toes
##A[0] = A[1]


def base_pack_lazy(a, base, dtype=np.uint64):
    """
    pack the last axis of an array as minimal base representation
    lazily yields packed columns of the original matrix
    """
    a = np.ascontiguousarray( np.rollaxis(a, -1))
    init = np.zeros(a.shape[1:], dtype)
    packing = int(np.dtype(dtype).itemsize * 8 / (float(base) / 2))
    for columns in np.array_split(a, (len(a)-1)//packing+1):
        yield reduce(
            lambda acc,inc: acc*base+inc,
            columns,
            init)

def unique_count(a):
    """returns counts of unique elements"""
    unique, inverse = np.unique(a, return_inverse=True)
    count = np.zeros(len(unique), np.int)
    np.add.at(count, inverse, 1)        #note; this scatter operation requires numpy 1.8; use a sparse matrix otherwise!
    return unique, count, inverse

def has_identical_row_sums_lazy(A, combinations_index):
    """
    compute the existence of combinations of rows summing to the same vector,
    given an nxm matrix A and an index matrix specifying all combinations

    naively, we need to compute the sum of each row combination at least once, giving n^3 computations
    however, this isnt strictly required; we can lazily consider the columns, giving an early exit opportunity
    all nicely vectorized of course
    """

    multiplicity, combinations = combinations_index.shape
    #list of indices into combinations_index, denoting possibly interacting combinations
    active_combinations = np.arange(combinations, dtype=np.uint32)

    for packed_column in base_pack_lazy(A, base=multiplicity+1):       #loop over packed cols
        #compute rowsums only for a fixed number of columns at a time.
        #this is O(n^2) rather than O(n^3), and after considering the first column,
        #we can typically already exclude almost all rowpairs
        partial_rowsums = sum(packed_column[I[active_combinations]] for I in combinations_index)
        #find duplicates in this column
        unique, count, inverse = unique_count(partial_rowsums)
        #prune those pairs which we can exclude as having different sums, based on columns inspected thus far
        active_combinations = active_combinations[count[inverse] > 1]
        #early exit; no pairs
        if len(active_combinations)==0:
            return False
    return True

def has_identical_triple_row_sums(A):
    n = len(A)
    idx = np.array( [(i,j,k)
        for i in xrange(n)
            for j in xrange(n)
                for k in xrange(n)
                    if i<j and j<k], dtype=np.uint16)
    idx = np.ascontiguousarray( idx.T)
    return has_identical_row_sums_lazy(A, idx)

def has_identical_double_row_sums(A):
    n = len(A)
    idx = np.array(np.tril_indices(n,-1), dtype=np.int32)
    return has_identical_row_sums_lazy(A, idx)


from time import clock
t = clock()
for i in xrange(10):
    print has_identical_double_row_sums(A)
    print has_identical_triple_row_sums(A)
print clock()-t

Extended, чтобы включить вычисление сумм триплетов строк, как вы сказали выше. При n = 100 это все равно занимает около 0,2 с

Изменить: некоторая очистка; edit2: еще одна очистка

Ответ 2

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

def findMatchSets(A):
   B = A.transpose()
   pairs = tuple(combinations(range(len(A[0])), 2))
   matchSets = [[i for i in pairs if B[0][i[0]] + B[0][i[1]] == z] for z in range(3)]
   for c in range(1, len(A[0])):
      matchSets = [[i for i in block if B[c][i[0]] + B[c][i[1]] == z] for z in range(3) for block in matchSets]
      matchSets = [block for block in matchSets if len(block) > 1]
      if not matchSets:
         return []
   return matchSets

Это в основном стратифицирует матрицу в наборах эквивалентности, которые суммируются с одинаковым значением после того, как один столбец был принят во внимание, затем два столбца, затем три и т.д., пока он не достигнет последнего столбца или не будет установлен набор эквивалентности слева с более чем одним членом (т.е. такой пары пар нет). Это будет отлично работать для массивов 100x100, в основном потому, что шансы двух пар рядов суммирования на один и тот же вектор строки бесконечно малы, когда n велико (n * (n + 1)/2 комбинаций по сравнению с 3 ^ n возможных векторных сумм).

UPDATE

Обновлен код, позволяющий искать пары подмножеств n-размера для всех строк по запросу. По умолчанию задано n = 2 по первому вопросу:

def findMatchSets(A, n=2):
   B = A.transpose()
   pairs = tuple(combinations(range(len(A[0])), n))
   matchSets = [[i for i in pairs if sum([B[0][i[j]] for j in range(n)]) == z] for z in range(n + 1)]
   for c in range(1, len(A[0])):
      matchSets = [[i for i in block if sum([B[c][i[j]] for j in range(n)]) == z] for z in range(n + 1) for block in matchSets]
      matchSets = [block for block in matchSets if len(block) > 1]
      if not matchSets:
      return []
   return matchSets

Ответ 3

Вот чистое решение numpy; нет длительных таймингов, но я должен нажимать n до 500, прежде чем я увижу, что мой курсор мигает один раз перед его завершением. это интенсивность памяти, хотя, и будет терпеть неудачу из-за требований к памяти для гораздо большего n. В любом случае, я получаю интуицию, что шансы найти такой вектор геометрически уменьшаются при больших n.

import numpy as np

n = 100
A = np.random.randint(2, size=(n,n)).astype(np.int8)

def base3(a):
    """
    pack the last axis of an array in base 3
    40 base 3 numbers per uint64
    """
    S = np.array_split(a, a.shape[-1]//40+1, axis=-1)
    R = np.zeros(shape=a.shape[:-1]+(len(S),), dtype = np.uint64)
    for i in xrange(len(S)):
        s = S[i]
        r = R[...,i]
        for j in xrange(s.shape[-1]):
            r *= 3
            r += s[...,j]
    return R

def unique_count(a):
    """returns counts of unique elements"""
    unique, inverse = np.unique(a, return_inverse=True)
    count = np.zeros(len(unique), np.int)
    np.add.at(count, inverse, 1)
    return unique, count

def voidview(arr):
    """view the last axis of an array as a void object. can be used as a faster form of lexsort"""
    return np.ascontiguousarray(arr).view(np.dtype((np.void, arr.dtype.itemsize * arr.shape[-1]))).reshape(arr.shape[:-1])

def has_pairs_of_pairs(A):
    #optional; convert rows to base 3
    A = base3(A)
    #precompute sums over a lower triangular set of all combinations
    rowsums = sum(A[I] for I in np.tril_indices(n,-1))
    #count the number of times each row occurs by sorting
    #note that this is not quite O(n log n), since the cost of handling each row is also a function of n
    unique, count = unique_count(voidview(rowsums))
    #print if any pairs of pairs exist;
    #computing their indices is left as an excercise for the reader
    return np.any(count>1)

from time import clock
t = clock()
for i in xrange(100):
    print has_pairs_of_pairs(A)
print clock()-t

Изменить: включена упаковка base-3; теперь n = 2000 возможно, взяв около 2 гб памяти и несколько секунд обработки

Изменить: добавлены некоторые тайминги; n = 100 занимает только 5 мс за звонок на моем i7m.

Ответ 4

Ваш текущий код не проверяет пары строк, которые суммируются с одним и тем же значением.

Предполагая, что на самом деле вы хотите, лучше всего придерживаться чистого numpy. Это порождает индексы всех строк, имеющих равную сумму.

import numpy as np

n = 100
A = np.random.randint(2, size=(n,n))

rowsum = A.sum(axis=1)

unique, inverse = np.unique(rowsum, return_inverse = True)

count = np.zeros_like(unique)
np.add.at(count, inverse, 1)

for p in unique[count>1]:
    print p, np.nonzero(rowsum==p)[0]

Ответ 5

Если все, что вам нужно сделать, это определить, существует ли такая пара, которую вы можете сделать:

exists_unique = np.unique(A.sum(axis=1)).size != A.shape[0]