查找属于一列但不属于高阶列的对数。

Question

我有一个n x k二进制numpy数组，我试图找到一种有效的方法来查找属于某些column[j]但不属于任何较高列的对数，在这种情况下，增加索引值的方法更高。

例如，在数组中：

array([[1, 1, 1, 0, 1, 0],
       [1, 0, 1, 1, 1, 0],
       [1, 0, 1, 0, 0, 0],
       [1, 1, 1, 1, 1, 0],
       [1, 0, 1, 0, 1, 1],
       [1, 0, 1, 0, 1, 1],
       [1, 1, 1, 1, 0, 0],
       [1, 1, 1, 0, 1, 0]], dtype=int32)

输出应该是array([ 0, 0, 11, 2, 14, 1], dtype=int32)。这是有意义的，因为我们看到column[2]有所有的列，所以任何一对都必须有至少2的最高列，因为即使column[0]也有所有的列，它也比较低，所以没有一对相同的最高列。在我考虑的任何情况下，column[0]都会拥有所有的。

下面是一些有用的示例代码，我相信是类似于O(n^2k)的代码。

def hcc(i, j, k, bin_mat):

    # hcc means highest common columns

    # i: index i
    # j: index j
    # k: number of columns - 1
    # bin_mat: binary matrix
    for q in range(k, 0, -1):
        if (bin_mat[i, q] and bin_mat[j, q]):
            return q
    return 0

def get_num_pairs_columns(bin_mat):
    k = bin_mat.shape[1]-1
    num_pairs_hcc = np.zeros(k+1, dtype=np.int32)  # number of one-pairs in columns

    for i in range(bin_mat.shape[0]):
        for j in range(bin_mat.shape[0]):
            if(i < j):
                num_pairs_hcc[hcc(i, j, k, bin_mat)] += 1
    return num_pairs_highest_column

我认为解决问题的另一种方法是通过集合。因此，每个列都有自己的集合，每一行的索引都会被添加到这样的集合中。因此，对于上面的示例，如下所示：

set = [{0, 1, 2, 3, 4, 5, 6, 7},
 {0, 3, 6, 7},
 {0, 1, 2, 3, 4, 5, 6, 7},
 {1, 3, 6},
 {0, 1, 3, 4, 5, 7},
 {4, 5}]

这样做的目的是找出set[j]中没有较高集合的对数(可以在较低的集合中，而不是更高的集合中)。因为，我前面提到过，所有情况都有列0和所有的情况，每一组都是set[0]的子集。因此，使用这种方法执行的代码更糟糕，如下所示：

def generate_sets(bin_mat):
    sets = []
    for j in range(bin_mat.shape[1]):
        column = set()
        for i in range(bin_mat.shape[0]):
            if bin_mat[i, j] == 1:
                column.add(i)
        sets.append(column)
    return sets

def get_hcc_sets(bin_mat):
    sets = generate_sets(bin_mat)
    pairs_sets = []
    num_pairs_hcc = np.zeros(len(sets), dtype=np.int32)
    for subset in sets:
        pairs_sets.append({p for p in itertools.combinations(sorted(subset), r = 2)})
    for j in range(len(sets)-1):
        intersections = [pairs_sets[j].intersection(pairs_sets[q]) for q in range(j+1, len(sets))]
        num_pairs_hcc[j] = len(pairs_sets[j] - set.union(*intersections))
    num_pairs_hcc[len(sets)-1]=len(pairs_sets[len(sets)-1])
    return num_pairs_hcc

我没有检查这个设置实现是否总是产生与前一个相同的结果，但是在我尝试过的有限的很多情况下，它都是有效的。但是，我100%肯定我的第一个实现给出了我所需要的结果。

另一个参考例子：

投入：

array([[1, 1, 0],
       [1, 1, 0],
       [1, 1, 0],
       [1, 1, 0],
       [1, 0, 1],
       [1, 0, 1],
       [1, 0, 1],
       [1, 0, 1]], dtype=int32)

产出：

array([16,  6,  6], dtype=int32)

有没有办法胜过我的O(n^2k)实现。这似乎是相当野蛮的力量，应该有一些东西，我可以利用，使这一计算更快。在很多情况下，我总是期望n比k大一个数量级。所以我宁愿k指数比n指数高。

Answer 1

如果要使用python中的O(n² k)方法，则可以使用itertools和set来使用更短的代码；代码也可能更高效。

import itertools

t = [[1, 1, 1, 0, 1, 0],
     [1, 0, 1, 1, 1, 0],
     [1, 0, 1, 0, 0, 0],
     [1, 1, 1, 1, 1, 0],
     [1, 0, 1, 0, 1, 1],
     [1, 0, 1, 0, 1, 1],
     [1, 1, 1, 1, 0, 0],
     [1, 1, 1, 0, 1, 0]]
n,k = len(t),len(t[0])

# build set of pairs of 1 in column j
def candidates(j):
  return {(i1, i2) for (i1, i2) in itertools.combinations(range(n), 2) if 1 == t[i1][j] == t[i2][j]}

# build set of pairs of 1 in higher columns
def badpairs(j):
  return {(i1, i2) for (i1, i2) in itertools.combinations(range(n), 2) if any(1 == t[i1][j0] == t[i2][j0] for j0 in range(j+1, k))}

# set difference
def finalpairs(j):
  return candidates(j) - badpairs(j)

# print pairs
for j in range(k):
  print(j, finalpairs(j))

# 0 set()
# 1 set()
# 2 {(2, 4), (1, 2), (2, 7), (4, 6), (0, 6), (2, 3), (6, 7), (0, 2), (2, 6), (5, 6), (2, 5)}
# 3 {(1, 6), (3, 6)}
# 4 {(0, 1), (0, 7), (0, 4), (3, 4), (1, 5), (3, 7), (0, 3), (1, 4), (5, 7), (1, 7), (0, 5), (1, 3), (4, 7), (3, 5)}
# 5 {(4, 5)}

# print number of pairs
for j in range(k):
  print(j, len(finalpairs(j)))

# 0 0
# 1 0
# 2 11
# 3 2
# 4 14
# 5 1

badpairs的交替定义

def badpairs(j):
  return set().union(*(candidates(j0) for j0 in range(j+1, k)))

badpairs略有不同的方法:避免构建

def finalpairs(j):
  return {(i1, i2) for (i1, i2) in itertools.combinations(range(n), 2) if 1 == t[i1][j] == t[i2][j] and not any(1 == t[i1][j0] == t[i2][j0] for j0 in range(j+1, k))}