求盲盒概率

nrooks.py

# 原问题：
# https://www.v2ex.com/t/743836

from itertools import *

# 算法来源：
# https://codegolf.stackexchange.com/a/97083
def perm_ryser(a): # Ryser's formula, using matrix entries
    maxn = len(a)
    n_list = range(1,maxn+1)
    s_list = chain.from_iterable(combinations(n_list,i) for i in range(maxn+1))
    total = 0
    for st in s_list:
        stotal = (-1)**len(st)
        for i in range(maxn):
            stotal *= sum(a[i][j-1] for j in st)
        total += stotal
    return total*((-1)**maxn)

# 矩阵格式：
# 盒子  A B C D E F
# 物品1 0 1 0 1 0 1 - 0代表不可放置，1代表可放置
mat_source = [
    [0,1,0,1,0,1],
    [1,1,1,0,0,0],
    [1,0,0,0,1,1],
    [1,0,1,1,0,0],
    [0,0,0,0,1,1],
    [0,1,1,1,1,0],
]

if len(mat_source) != len(mat_source[0]):
    raise ValueError('wtf')

# 总的可能排列数
p = perm_ryser(mat_source)

def main():
    result = []
    for _ in range(len(mat_source)):
        result.append([0] * len(mat_source))

    # 每一格的排列数相当于假设这个物品放到了这个位置之后，
    # 删除这个位置对应的行和列，剩余的矩阵总的排列个数
    for i in range(len(mat_source)):
        for j in range(len(mat_source[i])):
            if mat_source[i][j] == 0:
                result[i][j] = 0
            else:
                mat_slice = mat_source[:i] + mat_source[i+1:]
                for k in range(len(mat_slice)):
                    mat_slice[k] = mat_slice[k][:j] + mat_slice[k][j+1:]
                result[i][j] = perm_ryser(mat_slice) / p * 100

    print('Matrix:')
    print('\n'.join('['+', '.join(f'{j}'.rjust(2) for j in a)+']' for a in mat_source))
    print('Permanent:')
    print(p)
    print('Result:')
    print('\n'.join('['+', '.join(f'{int(j)}'.rjust(2) for j in a)+']' for a in result))

if __name__ == '__main__':
    main()

# Permanent:
# 17
# Result:
# [ 0, 41,  0, 41,  0, 17]
# [35, 29, 35,  0,  0,  0]
# [29,  0,  0,  0, 35, 35]
# [35,  0, 35, 29,  0,  0]
# [ 0,  0,  0,  0, 52, 47]
# [ 0, 29, 29, 29, 11,  0]


# Matrix:
# [ 1,  1,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1]
# [ 1,  1,  1,  0,  0,  1,  0,  1,  1,  1,  1,  1]
# [ 0,  0,  0,  0,  1,  1,  0,  1,  1,  1,  1,  1]
# [ 1,  1,  1,  0,  1,  1,  1,  0,  0,  1,  1,  1]
# [ 1,  0,  1,  1,  1,  1,  1,  1,  1,  1,  0,  1]
# [ 1,  1,  1,  1,  1,  1,  1,  1,  0,  0,  1,  0]
# [ 0,  1,  1,  1,  1,  0,  1,  0,  1,  1,  0,  1]
# [ 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  0,  0]
# [ 1,  1,  0,  1,  0,  1,  1,  0,  1,  1,  1,  1]
# [ 1,  1,  1,  1,  0,  0,  1,  1,  1,  0,  1,  1]
# [ 1,  0,  1,  1,  1,  1,  0,  1,  0,  1,  1,  1]
# [ 0,  1,  1,  1,  1,  0,  1,  1,  1,  0,  1,  0]
# Permanent:
# 16674094
# Result:
# [ 9,  9,  0,  9,  8,  9,  9,  9,  8,  9,  8,  8]
# [11, 11, 11,  0,  0, 11,  0, 11, 10, 11, 10, 10]
# [ 0,  0,  0,  0, 14, 14,  0, 14, 14, 14, 14, 14]
# [11, 11, 11,  0, 10, 11, 11,  0,  0, 11, 10, 10]
# [10,  0,  9, 10,  9, 10, 10,  9,  9,  9,  0,  9]
# [11, 11, 11, 11, 10, 11, 11, 11,  0,  0, 10,  0]
# [ 0, 12, 12, 12, 12,  0, 12,  0, 12, 12,  0, 12]
# [10, 10,  9, 10,  9, 10, 10,  9,  9,  9,  0,  0]
# [11, 11,  0, 11,  0, 11, 11,  0, 10, 11, 10, 10]
# [11, 11, 11, 11,  0,  0, 11, 11, 10,  0, 10, 10]
# [11,  0, 11, 11, 10, 11,  0, 11,  0, 11, 10, 10]
# [ 0, 12, 12, 12, 12,  0, 12, 12, 12,  0, 12,  0]