确定在不使用"itertools.product"的情况下掷硬币的所有组合. [英] Determine all combinations of flipping a coin without using "itertools.product"
问题描述
我在论坛上浏览了类似的帖子，但所有人都建议使用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"的情况下掷硬币的所有组合.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
