1

假设有以下代码检查数字的相乘数字是否等于输入数字：

results = [a for a in range(10) if a == input]
results += [a*b for a in range(10) for b in range(10) if a*b == input]
results += [a*b*c for a in range(10) for b in range(10) for c in range(10) if a*b*c == input]
...

我希望它进行更改，以便在尚未找到结果的情况下动态地继续搜索匹配项。所以：

  • 如果一位数没有产生结果，请继续使用两位数
  • 如果两位数没有产生结果，请继续使用三位数
  • 等等 ...

我想以一种优雅的方式做到这一点，如果不是太内卷的话，即使是单线。如果根本没有匹配项，我还需要一个中断条件来避免无限循环。例如，如果输入是一个大于 10 的素数，则没有结果。中断条件应该是这样的：

if(math.pow(2, countOfDigits) > input):
    return

其中countOfDigits是当前在嵌套列表理解中检查的位数。换句话说，我的初始示例的第一行表示countOfDigits == 1，第二行countOfDigits == 2和第三行countOfDigits == 3。

4

4 回答 4

7

哦，那就继续吧：

next(
    sum(x) 
    for i in range(1, input) # overkill
    for x in itertools.product(range(10), repeat = i) 
    if reduce(operator.mul, x) == input
)

编辑：您已将问题更改为返回产品而不是总和，因此吐出input而不是sum(x).

我不能立即确定您是否想要第一个匹配项，或者您想要所有匹配项，其中因素的数量等于可能的最小值。如果是后者，你可以通过吐出input, i这个迭代器来做到这一点，然后itertools.groupby根据元组中的第二个值来收集它们，然后只取结果中的第一个值，然后迭代它以获得所有匹配项（虽然，因为你现在输出input的东西除了它的长度之外有点无趣）。

于 2013-10-31T19:23:42.847 回答
2

编辑：

你想要的是一个可以迭代的东西，但直到尽可能晚才起作用。那不是列表，因此列表理解是错误的工具。幸运的是，您可以使用生成器表达式。您的代码非常复杂，因此我们可能希望使用标准库中定义的一些帮助程序，在itertools.

让我们先看看您的零件的一般情况：

[n

   for x0 in range(10) 
   for x1 in range(10)
   ...
   for xn in range(10) 

 if x0 * x1 * ... * xn == input]

我们要概括三个部分。我们将从嵌套的 for 循环开始，作为 N 的参数。为此，我们将使用itertools.product，它需要一个序列序列，类似于[range(10), range(10), ... , range(10)]并从这些序列中产生每个可能的项目组合。在多次循环序列的特殊情况下，您可以将嵌套深度传递为repeat，因此我们可以得到：

[n

   for x in itertools.product(xrange(10), repeat=n)

 if x[0] * x[1] * ... * x[n] == input]

对于输出中的总和，我们可以用 将其展平为单个值sum()，对于乘积，没有真正的等价物。我们可以用一个reduce函数将两个数字相乘，我们可以从另一个标准库中得到operator.mul：

(n
 for x in itertools.product(xrange(10), repeat=n)
 if reduce(operator.mul, x, 1) == input)

到目前为止一切顺利，现在我们只需要为每个 n 值重复这个内部部分。假设我们想永远搜索，我们可以得到一个无休止的数字序列itertools.count(1)，最后，我们只需要将这个扁平的序列序列变成一个序列，我们可以使用itertools.chain.from_iterable

itertools.chain.from_iterable(
     (n
      for x in itertools.product(xrange(10), repeat=n)
      if reduce(operator.mul, x, 1) == input)
     for n in itertools.count(1)
     if 2 ** n > input))

In [32]: input = 32

In [33]: next(itertools.chain.from_iterable(
        (n
         for x in itertools.product(xrange(10), repeat=n)
         if reduce(operator.mul, x, 1) == input)
        for n in itertools.count(1) if 2 ** n > input))
Out[33]: 6
于 2013-10-31T19:35:14.890 回答
2

您有几个序列，每个序列可能包含也可能不包含解决方案。将它们转换为生成器，用于itertools将序列“链接”在一起，然后请求生成序列的第一个元素（注意不包含解的序列将为空）。

首先，您需要一种方法来n为 any 生成 -tuples序列n。该itertools模块有几个函数，其效果可与嵌套的 for 循环相媲美。与您的算法相匹配的是itertools.product. 以下生成所有n数字元组：

tuples = itertools.product(range(10), repeat=n)

实际上使用 更好itertools.combinations_with_replacement，因为没有必要同时测试(4,5)和(5,4)。它有类似的语法。所以这里有一个生成器，它会给你一个无限的 n 元组序列，用于增加n：

sequences = ( itertools.product(range(10), repeat=n) for n in itertools.count(1) )

接下来，您希望将这些序列串在一起（还没有实际遍历它们），形成一个序列。因为这些是生成器，所以只有在需要时才会对它们进行评估。 

bigchain = itertools.chain.from_iterable(sequences)

bigchain将吐出您需要检查的所有元组。要测试它们，您需要一种方法来乘以任意长度的元组。让我们定义它：

def mytest(x):
    return reduce(operator.mul, x, 1) == target

您现在可以使用此测试“过滤”此序列以仅选择匹配的元组（总会有很多，因为您1在组合中包含数字），然后询问第一个。

print itertools.islice(ifilter(mytest, bigchain), 1).next()

我已经更改了您的代码以将您的解决方案作为一个元组返回，因为否则，您只会得到您正在搜索的数字（例如，32）——这不会告诉您任何您不知道的事情！

这是，所有在一起：

from itertools import *
import operator

target = 32

sequences = ( combinations_with_replacement(range(10), n) for n in count(1) )
bigchain = chain.from_iterable(sequences)

def mytest(x):
    return reduce(operator.mul, x, 1) == target

print islice(ifilter(mytest, bigchain), 1).next()
# prints (4, 8)

您还可以消除上面的中间变量并将所有内容组合成一个表达式；但有什么意义呢？

于 2013-10-31T19:46:18.997 回答
1

我认为您不需要列表理解。我认为发电机在这里会更好：

def generate(x):
    for digits in itertools.count(1):
        for i in itertools.product(range(1, 10), repeat=digits):
            if reduce(operator.mul, i) == x:
                yield i
    if (math.pow(2, digits) > x):
        break

然后你做for i in generate(input_number)。

（您还需要import itertools,from functools import reduce和import math在顶部）。

((math.pow(2, digits) > x) 只是中断条件。)

于 2013-10-31T19:35:30.593 回答