在 n x nCr 矩阵中找到上三角

Question

给定矩阵 n x nCr，求唯一组合的布尔矩阵：

对于 n x n，这是微不足道的，唯一组合的布尔矩阵：

[['AA', 'AB', 'AC'],
 ['BA', 'BB', 'BC'],
 ['CA', 'CB', 'CC']]

n=3时的唯一组合为：

> mask = np.arange(3)[:, np.newaxis] < np.arange(3)
array([[False,  True,  True],
       [False, False,  True],
       [False, False, False]])

好的，现在当 n=7 且 r=2 且 n x nCr 矩阵时：

  AB AC AD AE AF AG BC BD BE BF BG CD CE CF CG DE DF DG EF EG FG <- 7C2 
A  0  0  0  0  0  0  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
B  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  1  1 
C  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1
D  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1
E  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1
F  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
G  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

我试图找到一种方法，当 n=7 和 c=2 时，找到一个 7x21（即 7x7C2）布尔值矩阵，其真值位于正确的位置。即在给我 ABC、ACD、ABE、ABF...EFG

的地方

显然它不是三角形，但我可以应用什么函数来创建一个遮罩，其中 returns 一个正确布尔值的 7x21 矩阵。

我实际上正在处理 > 50 的组合，所以理想情况下我不会构建一个 21x21 矩阵然后切出我不需要的东西，因为这是一个非常内存敏感的问题。

Answer 1

经过反复试验，我想到了这个：

import numpy as np
from scipy.special import comb

def comb_upper_triangular(n, r):
    k = comb(n, r, exact=True)
    ut = np.zeros((n, k), dtype=int)

    for i in range(n - r):
        ut[i, -comb(n - i - 1, r, exact=True):] = 1

    return ut

所以 comb_upper_triangular(7, 2) 我们得到：

array([[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])

对于替代的纯 numpy（和 scipy）解决方案，我们可以使用 mgrid：

def comb_upper_triangular2(n, r):
    k = comb(n, r, exact=True)
    x, y = np.mgrid[:n, :k]
    return (comb(n - x - 1, r) > np.fliplr(y)).astype(int)

此解决方案在内存中创建了几个大数组，但避免了 python 循环。

在 n x nCr 矩阵中找到上三角

Find the upper triangle in an n x nCr matrix

python

numpy

matrix

numpy-ndarray

array-broadcasting