时间戳

首页 > 解决方案 > Given an integer, add operators between digits to get n and return list of correct answers

python - Given an integer, add operators between digits to get n and return list of correct answers

问题描述

Here is the problem I'm trying to solve:

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.

For example, 

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

The question recommended using interleave(str1, str2) where interleave('abcdef', 'ab') = 'aabbcdef' and product(str1, n) where product('ab', 3) = ['aaa','aab','abb','bbb','aba','baa','bba'].

I have written interleave(str1, str2) which is

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

However, I have no idea how to code the product function. I assume it has to do something with recursion, so I'm trying to add 'a' and 'b' for every product.

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

Please help me to understand how to solve this question. (Not only the product it self)

标签： python

解决方案

一般解决方案

假设您的实现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 到最大值变化的所有可能的长度序列来做到这一点，这将是位数 - 1（参见下面的假设！）。然后，您使用内置函数 计算特定运算符序列eval返回的表达式，并将结果与​​所需的数字进行比较。如果表达式计算结果为您将其附加到返回数组（最初为空）。在评估所有可能的运算符序列的所有表达式后（请参阅假设！），您返回数组。inteleavennretval

假设

目前尚不清楚您是否可以多次使用同一个运算符，或者是否允许您省略使用某些运算符。我假设您可以多次使用相同的运算符，并且允许您省略使用运算符。因此，r_prod使用了（如您的问题所建议的那样）。在这种限制的情况下，您将需要使用一组运算符的排列（可能长度不同）。

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

产品实施

如果您查看itertools 文档，您可以看到该函数的等效代码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)

哪个打印['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb']- 我猜是你所追求的。

一个更具体（假设 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”。然后，您将用字符串“aa”、“ab”和“ac”替换字符串“a”。“b”和“c”也是如此。您重复此过程 n 次，以获取所有可能的长度为 r 的字符串，这些字符串是通过从池“abc”中进行替换绘制而生成的。

我认为尝试以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)]

推荐阅读