1

受此视频的数学启发,我很好奇获得一个数字 n 需要多长时间,我可以在其中使用数字 1 以及二进制基数中的加法和减法等一些运算。目前,我有这样的编码:

import itertools as it

def brute(m):
    out = set()
    for combo in it.product(['+','*','|'], repeat=m):
        x = parse(combo)
        if type(x) == int and 0 < x-1:
            out.add(x)
    return out

def parse(ops):
    eq = ""
    last = 1
    for op in ops:
        if op == "|":
            last *= 2
            last += 1
        else:
            eq += str(last)
            eq += op
            last = 1
    eq += str(last)
    return eval(eq)

这里,“|” 指连接,因此combo = ("+","|","*","|","|")将解析为1+11*111 = 1+3*7 = 22. 我正在使用它来建立一个表,其中有多少个数字是 m 操作,并研究它是如何增长的。目前我正在使用 itertools 产品功能来搜索所有可能的操作组合,尽管这有点重复,因为“+”和“*”都是可交换操作。有没有一种干净的方法来只生成可交换的唯一表达式?

目前,我最好的想法是有第二个蛮力程序,brute2(k)它只使用操作“*”和“|”,然后有:

def brute(m):
    out = set()
    for k in range(m):
       for a,b in it.product(brute(k),brute2(m-k)):
           out.add(a+b)

如果我记住事情,这将是相当不错的,但我不确定是否有比这更 Pythonic 或更有效的方法。此外,如果我决定在减法中添加更多操作,这将无法完全概括。

我希望实现的是洞察是否有一些模块或简单的方法可以有效地迭代操作组合。目前,itertools.product复杂度为 O(3^m)。但是,通过记忆和使用该brute2方法,我似乎可以将复杂度降低到 O(|brute(m-1)|),这似乎是渐近的 ~O(1.5^m)。虽然我对第二种方法比较满意,但如果有一种更通用的方法可以扩展到任意数量的操作,其中一些是可交换的,那就太好了。

更新:

我现在已经把我的第二个想法编码了。有了这个,当我的旧代码在 20 次操作后卡住了几个小时时,我能够快速获得 42 次操作中可访问的所有数字。这是新代码:

memo1 = {0:{1}}
def brute1(m):
    if m not in memo1:
        out = set(brute2(m+1))
        for i in range(m):
            for a,b in it.product(brute1(i),brute2(m-i)):
                out.add(a+b)
        memo1[m] = set(out)
    return memo1[m]
    
memo2 = {0:{1}}
def brute2(m):
    if m not in memo2:
        out = set()
        for i in range(m):
            for x in brute2(i):
                out.add(x*(2**(m-i)-1))
        memo2[m] = set(out)
    return memo2[m]

我要概括这一点,您订购所有可交换操作,[op_1,op_2,... op_x],让 brute(n,0) 返回所有可通过 n 个非交换操作到达的数字,然后:

memo = {}
def brute(n,i):
    if (n,i) not in memo:
        out = brute(n,i-1) #in case I don't use op_i
        for x in range(1,n): #x is the number of operations before my last use of op_i, if combo = (op_i,"|","+","+","*","+",op_i,"*","|"), this case would be covered when x = 6
            for a,b in it.product(brute(x,i),brute(n-x-1,i-1)):
                out.add(a op_i b)
        memo[(n,i)] = out
    return memo[(n,i)]

但是,您必须注意操作顺序。如果我先加法再乘法,事情会完全不同,这会说不同的事情。如果有像 PEMDAS 这样的层次结构,并且您不想考虑括号,我相信您只是按优先级降序列出操作,即 op_1 是您执行的第一个操作等。如果您允许一般括号,那么您应该有我相信这样的事情:

memo = {0:1}
def brute(m, ops):
    if m not in memo:
        out = set()
        for i in range(m):
            for a,b in it.product(brute(i),brute(m-i-1)):
                for op in ops:
                    out.add( op(a,b) )
        memo[m] = out
    return memo[m]

我对我们有某种 PEMDAS 系统的情况更感兴趣,括号是由操作顺序暗示的,但仍然欢迎对任何一种情况的有效性/效率提供反馈。

4

0 回答 0