四阶幻方数量的计算方法
本文最后更新于 1185 天前,其中的信息可能已经有所发展或是发生改变。

这是一道我今天在知乎上的看到的题目,觉得挺有意思的,就试了一下

原思路

def main():
    count = 0
    r = list(range(1,17))
    for a, b, c, d, e, f, g in permutations(r, 7):
        A = [a, b, c, 34 - a - b - c, d, e, f, 34 - d - e - f, g, -34 + 2*a + b + c + d - f + g, 68 - 2*a - b - c - d - e - g, e + f - g, 34 - a - d - g, 68 - 2*a - 2*b - c - d - e + f - g,  -34 + 2*a + b + d + e - f + g, -34 + a + b + c + d + g]
        if sorted(A) == r:
            # print(A)
            count += 1
    print(count)
def gen_ms():
    # itertools.permutations 函数 可以生成排列组合
    for i in itertools.permutations(range(1, 17), 7):
        (a, b, c, d, e, f, g) = i

        ms = np.zeros(16, dtype=int)
        ms[0] = a
        ms[1] = b
        ms[2] = c
        ms[3] = 34 - a - b - c

        ms[4] = d
        ms[5] = e
        ms[6] = f
        ms[7] = 34 - d - e - f

        ms[8] = 34 - 2 * a - b - c - d + f + g
        ms[9] = g
        ms[10] = 34 - e - f - g
        ms[11] = 2 * a + b + c + d + e - g -34

        ms[12] = a + b + c - f - g
        ms[13] = 34 - b - e - g
        ms[14] = -c + e + g
        ms[15] = -a + f + g

        # 判断
        if np.max(ms) > 16 or np.min(ms) < 1 or len(np.unique(ms)) < 16:
            continue

        print(ms)

这是两种最初的暴力枚举解法

原思路2

上图是暴力枚举需要枚举的元素,注意到 fg 是对称的,所以我们可以将枚举量缩小一半

简单来说,我们先枚举 fg,然后用一个矩阵记录 fg 是否已经计算过,计算过就直接跳过,大致的代码如下所示

    sim = np.zeros([17, 17], dtype=bool)
    for (f, g) in itertools.permutations(range(1, 17), 2):
        if sim[f, g]:
            continue

        sim[f, g] = sim[g, f] = 1

        li = list(range(1, 17))
        li.remove(f)
        li.remove(g)

        for (a, b, c, d, e) in itertools.permutations(li, 5):
            # 判断

最终思路

要将速度最快化,肯定要去除所有重复解的计算(重复解指的是通过翻转和旋转能够使得矩阵一致的解)

对于内侧的4个元素,一共可以用24种组合,但是只有3个是不重复的,就如下图所示

因此,我们可以先枚举内测的4个元素,然后和之前一样枚举外侧的元素,然后将结果乘以8,就得到最终答案了

不过要是要得到具体的矩阵的话,还需要手工对每一个解做翻转,旋转得到其他7个重复解

最终实现

最终的代码如下,注意到对于内侧元素,我采用了枚举三个元素计算第四个元素,然后通过排序后去重的方法,因为集合运算还是相当快的,元素也不多,这样比直接枚举四个元素要快一些

(不去重的话 (1, 2, 3, 4) 就会计算4次,一开始我想了半天没想到为啥结果会大4倍)

另外就是 sorted(ma) == r 是要比 min(ms) >= 1 and max(ms) <= 16 and len(set(ms)) == 16 慢的

def sub_gen(e, f, g, h):
    li = list(range(1, 17))
    li.remove(e)
    li.remove(f)
    li.remove(g)
    li.remove(h)

    r = list(range(1,17))

    ms = [0] * 16
    ms[5] = e
    ms[6] = f
    ms[9] = g
    ms[10] = h

    count = 0
    for (a, b, c, d) in itertools.permutations(li, 4):
        ms[0] = a
        ms[1] = b
        ms[2] = c
        ms[3] = 34 - a - b - c

        ms[4] = d
        ms[7] = 34 - d - e - f

        ms[8] = 34 - 2 * a - b - c - d + f + g
        ms[11] = 2 * a + b + c + d + e - g - 34

        ms[12] = a + b + c - f - g
        ms[13] = 34 - b - e - g
        ms[14] = -c + e + g
        ms[15] = -a + f + g

        if min(ms) >= 1 and max(ms) <= 16 and len(set(ms)) == 16:
        # if sorted(ms) == r:
            count += 1

    return count

def my_new_gen_ms():
    count = 0;
    sets = set()
    for (e, f, g) in itertools.combinations(range(1, 17), 3):
        h = 34 - e - f - g
        if h in [e, f, g] or h < 1 or h > 16:
            continue

        s = tuple(sorted([e, f, g, h]))
        if s in sets:
            continue

        sets.add(s)

        count += sub_gen(e, f, g, h)
        count += sub_gen(e, f, h, g)
        count += sub_gen(e, h, g, f)

    count *= 8
    print ("Total count : %d" % count)
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇