I'm trying to solve this problem here: https://codingbat.com/prob/p252079?parent=/home/[email protected]

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

Here's my code:

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

However, this is the output: Haven't hit 10 reputation yet so it's a link to the error. I'm not sure what I did wrong, can anybody help me out? Thank you so much.

CodePudding user response：

The problem is this. When k == 0 it shouldn't return [things]. It should return an empty array. Similar to when len(things) < k:. This is because, when k == 0, it means we that we have already found all the numbers for that specific combination.

But there's one more problem. We're returning an empty array. However, in the for loops, we're iterating over the returned array. So if the array is empty, nothing happens. So what we should really return is an empty 2D array. I won't go into too much detail about what the problem is since it's better for you to try and understand why it's not working. Try adding print statements inside and outside the for loops.

Anyway, the working code looks like this:

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

Note a few things:

• Use the variables you've already assigned (I'm assuming you forgot about them)
• Lists can be concatenated using , similar to strings. If you return within an if statement, you don't need an else for the next line since if the if statement is satisfied, it would definitely not go to the else.

CodePudding user response：

You simply can try using itertools:

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

output:

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

For 3 nums:

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

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