给定一个整数,在数字之间加上运算符得到n并返回正确答案的列表

2024-03-29 12:50:07 发布

您现在位置:Python中文网/ 问答频道 /正文

我想解决的问题是:

Given an int, ops, n, create a function(int, ops, n) and slot operators between digits of int to create equations that evaluates to n. Return a list of all possible answers. Importing functions is not allowed.

例如

function(111111, '+-%*', 11) => [1*1+11/1-1 = 11, 1*1/1-1+11 =11, ...]

问题建议使用interleave(str1, str2)where interleave('abcdef', 'ab') = 'aabbcdef'product(str1, n)where product('ab', 3) = ['aaa','aab','abb','bbb','aba','baa','bba']。你知道吗

我写了interleave(str1, str2),这是

def interleave(str1,str2):
    lsta,lstb,result= list(str1),list(str2),''
    while lsta and lstb:
        result += lsta.pop(0)
        result += lstb.pop(0)
    if lsta:
        for i in lsta:
            result+= i
    else:
        for i in lstb:
            result+=i
    return result

但是,我不知道如何编写product函数。我假设它与递归有关,所以我尝试为每个产品添加'a''b'。你知道吗

def product(str1,n):
    if n ==1:
        return  []
    else:
        return [product(str1,n-1)]+[str1[0]]

请帮助我理解如何解决这个问题。(不仅仅是产品本身)


Tags: andofreturncreatefunctionresultproductops
1条回答
网友
1楼 · 发布于 2024-03-29 12:50:07

通解

假设您的interleave实现是正确的,您可以将它与product(请参阅下面我建议的实现)一起使用来解决问题,方法如下:

def f(i, ops, n):
    int_str = str(i)
    retval = []
    for seq_len in range(1, len(int_str)):
        for op_seq in r_prod(ops, seq_len):
            eq = interleave(int_str, op_seq)
            if eval(eq) == n:
                retval.append(eq)
    return retval

其思想是将字符串的数字与运算符按不同的顺序交错。基本上,我是用所有可能的长度序列seq_len来实现的,长度从1到max不等,即数字的个数-1(参见下面的假设!)。然后使用built-in functionevalinteleave返回的表达式求值一个特定的运算符序列,并将结果与所需的数字n进行比较。如果表达式的计算结果为n,则将其附加到返回数组retval(最初为空)。在对所有可能的运算符序列的所有表达式求值之后(请参见假设!)返回数组。你知道吗

假设

不清楚是否可以多次使用同一个运算符,或者是否允许省略使用某些运算符。我假设您可以多次使用同一个运算符,并且允许您忽略使用运算符。因此,使用了r_prod(正如您的问题所建议的那样)。在这种限制的情况下,您需要使用操作符组的置换(长度可能不同)。你知道吗

其次,我假设interleave函数的实现是正确的。例如,interleave("112", "*")应该返回“1*12”和“11*2”,还是像您的实现那样只返回“1*12”,目前还不清楚。如果两个都应该返回,那么您还应该迭代可能的方法相同顺序的运算符序列可以与提供的数字交错。我省略了这个,因为我看到你的函数总是返回一个字符串。你知道吗

产品实施

如果您查看itertools docs,您可以看到函数itertools.product的等效代码。使用它,您将拥有:

def product(*args, repeat=1):
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

a = ["".join(x) for x in product('ab', repeat=3)]
print(a)

我猜你想要的是什么。你知道吗

一个更具体(假设iterable是一个字符串),效率更低,但希望更容易理解的解决方案是:

def prod(string, r):
    if r < 1:
        return None
    retval = list(string)
    for i in range(r - 1):
        temp = []
        for l in retval:
            for c in string:
                temp.append(l + c)
        retval = temp
    return retval

想法很简单。第二个参数r给出要生成的字符串的长度。字符串中的字符提供用于构建字符串的元素。因此,首先生成一个长度为1的字符串,该字符串以每个可能的字符开头。然后,通过将旧字符串与所有可能的字符连接起来,为每个字符串生成新字符串。你知道吗

例如,给定一个字符池“abc”,您将首先生成字符串“a”、“b”和“c”。然后将字符串“a”替换为字符串“aa”、“ab”和“ac”。与“b”和“c”类似。重复此过程n次,以从池“abc”中获取由绘制并替换生成的长度为r的所有可能字符串。你知道吗

我认为您最好尝试递归地实现prod函数。你可以在下面看到我难看的解决方案,但我建议你现在不要读这篇文章,试着不看我的建议就去做。你知道吗


扰流板下方


def r_prod(string, r):
    if r == 1:
        return list(string)
    else:
        return [c + s for c in string for s in r_prod(string, r - 1)]

相关问题 更多 >