讨论/面试考题/各位大佬,请问这种问题怎么解决呢?/
各位大佬,请问这种问题怎么解决呢?

假设有个矩阵,里边的值只有0,1,每个行向量都不相同.题目要求找出"最大子空间"的维数

"子空间"的定义为:假设k维子空间,那么有2的k次方个行向量,同时每一列中,0和1的个数相等.
例如有三维子空间:
0 0 0 0 0
1 1 1 0 0
1 1 0 1 0
0 0 1 1 0
0 1 0 0 1
1 0 1 0 1
1 0 0 1 1
0 1 1 1 1
总共有2的3次方,即8个行向量.同时每一列的0和1的个数都是4个.

例:有如下矩阵
00000
00010
00011
00101
00111
01000
01001
01011
01100
01101
10010
10100
10101
11001
11101
11110

里边存在子空间的最大维数为3,为:
0 0 0 0 0
1 1 1 0 0
1 1 0 1 0
0 0 1 1 0
0 1 0 0 1
1 0 1 0 1
1 0 0 1 1
0 1 1 1 1

设行向量长度为n,矩阵的行向量个数一般在(2的n-1次方)左右.题目提供的矩阵中,可以假设矩阵中的行向量对应的二进制数从小到大.

展开讨论
共 1 个讨论

统计每列01个数,贪心,从最大可能的k ,滑窗检测(第一列从上往下滑,找到可能的2 4 8 16…要倒过来,从最大的可能开始滑动)再看每一列,横向检测,找到的就是可能。 可能有 位计算的骚操作…
贪心+深搜, all()函数里判断条件比较费时间, 如果用状压计数, 会快很多.不过写起来,有些麻烦,要设计一个mask去 并.

def f(matrix: list):
    n = len(matrix)
    cols = list(zip(*matrix))
    max_zero_or_one = [min(c.count("0"), c.count("1")) for c in cols]
    max_k = int((min(max_zero_or_one) * 2) ** 0.5)
    status = [0] * n
    find = False
    res = []

    def dfs(cur_status: list):
        nonlocal find, res
        if len(cur_status) == 2 ** max_k:
            if all(cur.count("0") == cur.count("1") == 2 ** (max_k - 1) for cur in zip(*cur_status)):
                # 这行 if 判断可以用状压计数,会快一些.
                find = True
                res = cur_status
            return
        for i, v in enumerate(matrix):
            if find: return
            if not status[i]:
                status[i] = 1
                not find and dfs(cur_status + [v])
                status[i] = 0

    for mk in range(max_k, 0, -1):
        dfs([])
        if find: break
    return res

输入:
图片.png

运行结果:
图片.png