问题描述
我在论坛上浏览了类似的帖子,但所有人都建议使用itertools.product
,但我想知道如果不使用它是否可以解决.
I went through similar posts on the forum but all of them suggest using itertools.product
but I was wondering if it can be solved without using it.
我想打印硬币N次翻转的所有结果组合.如果N事先已知,则可以执行此操作.因此,嵌套循环的数量将仅为N.但是,如果必须动态确定N(input()
函数),那么我就不得不在代码中实现它.用通俗易懂的英语,很容易想到for循环的数量与N成正比,但是我该如何实现呢?我必须使用lambda还是递归?下面是N = 4的示例代码.
I want to print all the combinations of outcomes for N flips of a coin. This can be done if N is known in advance. So the number of nested loops will be just N. But if N has to be determined dynamically (input()
function) then I am stuck in implementing it in code. In plain English it is easy to imagine that the number of for loops is proportional to N, but how do I implement it? Do I have to use lambdas or recursion? Below is as example code for N = 4.
results = ["H", "T"]
outcomes = []
for l1 in results:
for l2 in results:
for l3 in results:
for l4 in results:
outcomes.append(l1+l2+l3+l4)
for o in outcomes:
print(o)
先谢谢了.
推荐答案
使用生成器进行DIY
这是不使用内置计算列表product
的一种方法
Here's one way to calculate a product
of lists without using the built-in
def product (*iters):
def loop (prod, first = [], *rest):
if not rest:
for x in first:
yield prod + (x,)
else:
for x in first:
yield from loop (prod + (x,), *rest)
yield from loop ((), *iters)
for prod in product ("ab", "xyz"):
print (prod)
# ('a', 'x')
# ('a', 'y')
# ('a', 'z')
# ('b', 'x')
# ('b', 'y')
# ('b', 'z')
在python中,我们可以使用list
构造函数将生成器的输出收集在一个列表中.请注意,我们还可以计算两个以上输入的乘积,如下所示
In python, we can collect the outputs of a generator in a list by using the list
constructor. Note we can also calculate the product of more than two inputs as seen below
print (list (product ("+-", "ab", "xyz")))
# [ ('+', 'a', 'x')
# , ('+', 'a', 'y')
# , ('+', 'a', 'z')
# , ('+', 'b', 'x')
# , ('+', 'b', 'y')
# , ('+', 'b', 'z')
# , ('-', 'a', 'x')
# , ('-', 'a', 'y')
# , ('-', 'a', 'z')
# , ('-', 'b', 'x')
# , ('-', 'b', 'y')
# , ('-', 'b', 'z')
# ]
由于product
接受 iterables 的列表,因此该产品中可以使用任何可迭代的输入.它们甚至可以混合在一起,如下所示
Because product
accepts a a list of iterables, any iterable input can be used in the product. They can even be mixed as demonstrated below
print (list (product (['@', '%'], range (2), "xy")))
# [ ('@', 0, 'x')
# , ('@', 0, 'y')
# , ('@', 1, 'x')
# , ('@', 1, 'y')
# , ('%', 0, 'x')
# , ('%', 0, 'y')
# , ('%', 1, 'x')
# , ('%', 1, 'y')
# ]
因为product
被定义为生成器,所以即使编写更复杂的程序,我们也能获得很大的灵活性.考虑一下该程序,该程序查找由整数组成的直角三角形,即勾股勾股三元.另外请注意,product
允许您重复进行迭代,作为输入,如下面的product (r, r, r)
Because product
is defined as a generator, we are afforded much flexibility even when writing more complex programs. Consider this program that finds right triangles made up whole numbers, a Pythagorean triple. Also note that product
allows you to repeat an iterable as input as see in product (r, r, r)
below
def is_triple (a, b, c):
return a * a + b * b == c * c
def solver (n):
r = range (1, n)
for p in product (r, r, r):
if is_triple (*p):
yield p
print (list (solver (20)))
# (3, 4, 5)
# (4, 3, 5)
# (5, 12, 13)
# (6, 8, 10)
# (8, 6, 10)
# (8, 15, 17)
# (9, 12, 15)
# (12, 5, 13)
# (12, 9, 15)
# (15, 8, 17)
实施投币程序现在很容易.
Implementing your coin tossing program is easy now.
def toss_coins (n):
sides = [ 'H', 'T' ]
coins = [ sides ] * n
yield from product (*coins)
print (list (toss_coins (2)))
# [ ('H', 'H'), ('H', 'T'), ('T', 'H'), ('T', 'T') ]
print (list (toss_coins (3)))
# [ ('H', 'H', 'H'), ('H', 'H', 'T'), ('H', 'T', 'H'), ('H', 'T', 'T'), ('T', 'H', 'H'), ('T', 'H', 'T'), ('T', 'T', 'H'), ('T', 'T', 'T') ]
没有生成器
但是生成器是一种非常高级的语言功能,我们想知道如何使用纯递归表示product
. product
下面的代码无需使用生成器即可重新实现,现在返回包含所有计算出的子产品的填充数组
But generators are a very high-level language feature and we wonder how we could represent product
using pure recursion. Below product
is reimplemented without the use of generators and now returns a filled array with all calculated sub-products
def map (f, lst):
if not lst:
return []
else:
first, *rest = lst
return [ f (first ) ] + map (f, rest)
def flat_map (f, lst):
if not lst:
return []
else:
first, *rest = lst
return f (first) + flat_map (f, rest)
def product (*iters):
def loop (acc, iters):
if not iters:
return acc
else:
first, *rest = iters
return flat_map (lambda c: map (lambda x: [x] + c, first), loop (acc, rest))
return loop ([[]], iters)
我们现在可以跳过程序中的yield
和list
调用
We can now skip the yield
and list
calls in your program
def toss_coins (n):
sides = [ 'H', 'T' ]
coins = [ sides ] * n
return product (*coins)
print (toss_coins (2))
# [('H', 'H'), ('H', 'T'), ('T', 'H'), ('T', 'T')]
print (toss_coins (3))
# [('H', 'H', 'H'), ('H', 'H', 'T'), ('H', 'T', 'H'), ('H', 'T', 'T'), ('T', 'H', 'H'), ('T', 'H', 'T'), ('T', 'T', 'H'), ('T', 'T', 'T')]
上面,我们定义了map
和flat_map
并尽可能减少了依赖,但是在每个实现中只有一个细微的区别.在下面,我们将每个表示为 fold (使用reduce
),使我们可以更轻松地看到语义差异.还要注意,Python包含自己的map
和reduce
版本(在functools
中),与此处提供的版本略有不同.
Above, we define map
and flat_map
with as few dependencies as possible, however there is only one subtle distinction in each implementation. Below, we represent each as a fold (using reduce
) allowing us to see the semantic difference more easily. Also note Python includes its own version of map
and reduce
(in functools
) that differ slightly from the versions provided here.
def concat (xs, ys):
return xs + ys
def append (xs, x):
return xs + [ x ]
def reduce (f, init, lst):
if not lst:
return init
else:
first, *rest = lst
return reduce (f, f (init, first), rest)
def map_reduce (m, r):
return lambda acc, x: r (acc, m (x))
def map (f, lst):
return reduce (map_reduce (f, append), [], lst)
def flat_map (f, lst):
return reduce (map_reduce (f, concat), [], lst)
def product (*iters):
# this stays the same
这篇关于确定在不使用"itertools.product"的情况下掷硬币的所有组合.的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!