在不使用 "itertools.product" 的情况下确定抛硬币的所有组合

Question

我在论坛上浏览了类似的帖子，但他们都建议使用 itertools.product 但我想知道是否可以不使用它来解决。

我想打印 N 次抛硬币结果的所有组合。如果事先知道 N，则可以这样做。因此嵌套循环的数量将仅为 N。但是如果必须动态确定 N（input() 函数），那么我将无法在代码中实现它。用简单的英语很容易想象for循环的次数与N成正比，但我该如何实现呢？我必须使用 lambda 还是递归？下面是 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)

提前致谢。

Answer 1

用发电机DIY

这是一种计算 product 列表而不使用 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构造函数在列表中收集生成器的输出。请注意，我们还可以计算两个以上输入的乘积，如下所示

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 的列表，任何可迭代的输入都可以在产品中使用。它们甚至可以混合使用，如下所示

print (list (product (['@', '%'], range (2), "xy")))
# [ ('@', 0, 'x')
# , ('@', 0, 'y')
# , ('@', 1, 'x')
# , ('@', 1, 'y')
# , ('%', 0, 'x')
# , ('%', 0, 'y')
# , ('%', 1, 'x')
# , ('%', 1, 'y')
# ]

因为product被定义为一个生成器，即使在编写更复杂的程序时，我们也有很大的灵活性。考虑这个寻找由整数组成的直角三角形的程序，a Pythagorean triple。另请注意，product 允许您重复一个可迭代作为输入，如下面的 product (r, r, r) 所示

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)

现在实施您的抛硬币程序很容易。

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') ]

没有发电机

但是生成器是一种非常 high-level 的语言特性，我们想知道如何使用纯递归来表示 product。 product 下面是在不使用生成器的情况下重新实现的，现在 returns 是一个包含所有计算的 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 调用

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 中），与此处提供的版本略有不同。

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

Answer 2

x=int(input("No. of coin: "))
range_lst=[[] for i in range(2**x)]
i=0
while i<x:
    div=2**(x-1-i)
    alt=0
    for j in range(2**x):
        if alt<div:    
            range_lst[j].append("H")
            alt+=1
        else:
            if alt==((div*2)-1):
                alt-=((div*2)-1)
            else:
                alt+=1
            range_lst[j].append("T")
    i+=1
print(range_lst)

在不使用 "itertools.product" 的情况下确定抛硬币的所有组合

Determine all combinations of flipping a coin without using "itertools.product"

recursion

lambda

probability

itertools

python-3.x