尝试自己在 Python 中编写组合函数，但无法正常工作

Question

我正在尝试解决此问题：https://codingbat.com/prob/p252079?parent=/home/peter@norvig.com

In math, a "combination" of a set of things is a subset of the things. We define the function combinations(things, k) to be a list of all the subsets of exactly k elements of things. Conceptually, that's all there is, but there are some questions to settle: (A) how do we represent a subset? (B) What order are the elements within each subset? (C) What order to we list the subsets? Here's what we will agree to: (A) a subset will be a list. (B) The order of elements within a list will be the same as the order within 'things'. So, for example, for combinations([1, 2, 3], 2) one of the subsets will be [1, 2]; whereas [2, 1] is not a subset. (C) The order of subsets will be lexicographical or sorted order -- that is, combinations([1, 2, 3], 2) returns [ [1, 2], [1, 3], 2, 3] ] because [1, 2] < [1, 3] < [2, 3]. You might want to use the function 'sorted' to make sure the results you return are properly ordered.

combinations([1, 2, 3, 4, 5], 2) → [[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]]

combinations([1, 2, 3], 2) → [[1, 2], [1, 3], [2, 3]]

combinations([1, 2, 3, 4, 5, 6], 5) → [[1, 2, 3, 4, 5], [1, 2, 3, 4, 6], [1, 2, 3, 5, 6], [1, 2, 4, 5, 6], [1, 3, 4, 5, 6], [2, 3, 4, 5, 6]]

这是我的代码：

def combinations(things, k):
  if k == 0 or k == len(things):
    return [things]
  elif len(things) < k:
    return
  else:
    finalcomb = []
    subcomb1 = combinations(things[1:], k - 1)
    subcomb2 = combinations(things[1:], k)
    for i in range(len(combinations(things[1:], k - 1))):
      firstelement = [things[0]]
      firstelement += combinations(things[1:], k - 1)[i]
      finalcomb.append(firstelement)
    for j in range(len(combinations(things[1:], k))):
      finalcomb.append(combinations(things[1:], k)[j])
    return finalcomb

然而，这是输出： Haven't hit 10 reputation yet so it's a link to the error. 我不确定我做错了什么，有人可以帮助我吗？非常感谢。

Answer 1

问题是这样的。当 k == 0 时，它不应该 return [things]。它应该 return 一个空数组。类似于len(things) < k:。这是因为，当 k == 0 时，这意味着我们已经找到了该特定组合的所有数字。

但是还有一个问题。我们正在 return 创建一个空数组。但是，在 for 循环中，我们迭代 returned 数组。因此，如果数组为空，则什么也不会发生。所以我们真正应该 return 的是一个空的二维数组。我不会详细说明问题是什么，因为您最好尝试了解它为什么不起作用。尝试在 for 循环内外添加打印语句。

无论如何，工作代码如下所示：

def combinations(things, k):
  if k == len(things):
    return [things[:]]
  if len(things) < k or k == 0:
    return [[]]
  finalcomb = []
  subcomb1 = combinations(things[1:], k - 1)
  subcomb2 = combinations(things[1:], k)
  for comb in subcomb1:
    firstelement = [things[0]]
    firstelement += comb
    finalcomb.append(firstelement)
  finalcomb += subcomb2
  return finalcomb

注意几点：

使用您已经分配的变量（我假设您忘记了它们）
可以使用 + 连接列表，类似于字符串。如果在 if 语句中 return，下一行不需要 else，因为如果满足 if 语句，它肯定不会转到 else.

Answer 2

您可以尝试使用 itertools:

import itertools
output = []
for nums in itertools.combinations([1, 2, 3, 4, 5], 2):
    output.append(list(nums))
print(output)

输出:

[[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]]

对于 3 个数字：

import itertools
output = []
for nums in itertools.combinations([1, 2, 3, 4, 5], 3):
    output.append(list(nums))
print(output)

输出:

[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

尝试自己在 Python 中编写组合函数，但无法正常工作

Trying to write a combinations function in Python on my own, not working

python

combinations