Удалить определенные элементы массива numpy

Question

У меня есть два numpy массива a и b. У меня есть определение, которое создает массив c, элементами которого являются все возможные суммы различных элементов a.

import numpy as np

def Sumarray(a):
    n = len(a)

    sumarray = np.array([0]) # Add a default zero element
    for k in range(2,n+1):
        full = np.mgrid[k*(slice(n),)]
        nd_triu_idx = full[:,(np.diff(full,axis=0)>0).all(axis=0)]
        sumarray = np.append(sumarray, a[nd_triu_idx].sum(axis=0))

    return sumarray

a = np.array([1,2,6,8])
c = Sumarray(a)
print(d)

Затем я выполняю подмножество между элементами c и b: isSubsetSum возвращает элементы b, которые при суммировании дают c [1]. Допустим, я получаю

c[0] = b[2] + b[3]

Затем я хочу удалить:

1. элементы b [2], b [3] (простой бит) и
2. элементы a, которые при суммировании дали c [0]

Как видно из определения Sumarray, порядок сумм различных элементов a сохраняетсяпоэтому мне нужно реализовать некоторое отображение.

Функция isSubsetSum задается как

def _isSubsetSum(numbers, n, x, indices):
    if (x == 0):
        return True
    if (n == 0 and x != 0):
        return False
    # If last element is greater than x, then ignore it
    if (numbers[n - 1] > x):
        return _isSubsetSum(numbers, n - 1, x, indices)
    # else, check if x can be obtained by any of the following
    found = _isSubsetSum(numbers, n - 1, x, indices)
    if found: return True
    indices.insert(0, n - 1)
    found = _isSubsetSum(numbers, n - 1, x - numbers[n - 1], indices)
    if not found: indices.pop(0)
    return found

def isSubsetSum(numbers, x):
    indices = []
    found = _isSubsetSum(numbers, len(numbers), x, indices)
    return indices if found else None

Answer 1

Поскольку вы перебираете все возможные числа терминов, вы также можете напрямую генерировать все возможные подмножества.

Они могут быть удобно закодированы как числа 0,1,2 ,. .. с помощью их двоичных представлений: O означает отсутствие терминов вообще, 1 означает только первое слагаемое, 2 означает только второе, 3 означает первое и второе и т. д.

Используя эту схему, онстановится очень легко восстанавливать термины из индекса суммы, потому что все, что нам нужно сделать, это получить двоичное представление:

ОБНОВЛЕНИЕ: мы можем подавить 1-членную сумму небольшим количеством дополнительного кода:

import numpy as np

def find_all_subsums(a,drop_singletons=False):
    n = len(a)
    assert n<=32 # this gives 4G subsets, and we have to cut somewhere
    # compute the smallest integer type with enough bits
    dt = f"<u{1<<((n-1)>>3).bit_length()}"
    # the numbers 0 to 2^n encode all possible subsets of an n
    # element set by means of their binary representation
    # each bit corresponds to one element number k represents the 
    # subset consisting of all elements whose bit is set in k
    rng = np.arange(1<<n,dtype=dt)
    if drop_singletons:
        # one element subsets correspond to powers of two
        rng = np.delete(rng,1<<np.arange(n))
    # np.unpackbits transforms bytes to their binary representation
    # given the a bitvector b we can compute the corresponding subsum
    # as b dot a, to do it in bulk we can mutliply the matrix of 
    # binary rows with a
    return np.unpackbits(rng[...,None].view('u1'),
                         axis=1,count=n,bitorder='little') @ a

def show_terms(a,idx,drop_singletons=False):
    n = len(a)
    if drop_singletons:
        # we must undo the dropping of powers of two to get an index
        # that is easy to translate. One can check that the following
        # formula does the trick
        idx += (idx+idx.bit_length()).bit_length()
        # now we can simply use the binary representation
    return a[np.unpackbits(np.asarray(idx,dtype='<u8')[None].view('u1'),
                           count=n,bitorder='little').view('?')]


example = np.logspace(1,7,7,base=3)
ss = find_all_subsums(example,True)
# check every single sum
for i,s in enumerate(ss):
    assert show_terms(example,i,True).sum() == s
# print one example
idx = 77
print(ss[idx],"="," + ".join(show_terms(example.astype('U'),idx,True)))

Пример прогона:

2457.0 = 27.0 + 243.0 + 2187.0