CODEWITHSUNDEEP
pythonrecursion
charen
charen

Reputation: 371

Using recursion to create a list combination

I'm in trouble creating a combination of elements from list.

What i would like to do is to create a recursive function in Python which returns a combination of elements for example list a = [1,2,3,4,5,6,7,8] and a result will be combinations [1,2,3,4],[1,3,4,5],[1,4,5,6],[1,2,4,5] etc. For 8 elements it should return 70 combinations (if i did my math right). Although the best option would be that the combinations don't repeat.

I tried to code it, but what i get is only [1,2,3,4],[1,3,4,5] etc but not combination [1,5,7,8]

I know there is a special function but i'd like to do it recursively. Any suggestions?

nimed = ["A","B","C","D","E","F","G","H"]


def kombinatsioonid(listike,popitav):
  if len(listike) < 4:
      return
  tyhi = []
  for c in range(len(listike)):
      tyhi.append(listike[c])
  listike.pop(popitav)
  print(tyhi)
  kombinatsioonid(listike,popitav)

kombinatsioonid(nimed,1)

Upvotes: 1

Views: 1222

Answers (2)

georg
georg

Reputation: 214969

For each element x in a, generate all k-1 combinations from the elements right to it, and prepend x to each one. If k==0, simply return one empty combination, thus exiting the recursion:

def combs(a, k):
    if k == 0:
        return [[]]
    r = []
    for i, x in enumerate(a):
        for c in combs(a[i+1:], k - 1):
            r.append([x] + c)
    #print '\t' * k, k, 'of', a, '=', r
    return r

Uncomment the "print" line to see what's going on.

As a side note, it's better to use English variable and function names, just for the sake of interoperability (your very question being an example).

Upvotes: 1

bluefoggy
bluefoggy

Reputation: 1051

This can be done in this way :

def combination(l,n, mylist=[]):
    if not n:  print(mylist)
    for i in range(len(l)):
        mylist.append(l[i])
        combination(l[i+1:], n-1, mylist)
        mylist.pop()

l = ["A","B","C","D","E","F","G","H"]
n=4
combination(l, n)

Upvotes: 2

Related Questions