CODEWITHSUNDEEP
pythonalgorithmrecursion
ZengJuchen
ZengJuchen

Reputation: 4811

Is it possible to write a combination function with recursion technique?

Yesterday, I encountered a problem which requires calculating combinations in an iterable with range 5.

Instead of using itertools.combination, I tried to make a primitive function of my own. It looks like:

def combine_5(elements):
    """Find all combinations in elements with range 5."""
    temp_list = []
    for i in elements:
        cur_index = elements.index(i)
        for j in elements[cur_index+1 : ]:
            cur_index = elements.index(j)
            for k in elements[cur_index+1 : ]:
                cur_index = elements.index(k)
                for n in elements[cur_index+1 : ]:
                    cur_index = elements.index(n)
                    for m in elements[cur_index+1 : ]:
                        temp_list.append((i,j,k,n,m))

    return temp_list

Then I thought maybe I can abstract it a bit, to make a combine_n function. And below is my initial blueprint:

# Unfinished version of combine_n
def combine_n(elements, r, cur_index=-1):
    """Find all combinations in elements with range n"""
    r -= 1 
    target_list = elements[cur_index+1 : ]
    for i in target_list:
        cur_index = elements.index(i)
        if r > 0:
            combine_n(elements, r, cur_index)
            pass
        else:
            pass

Then I've been stuck there for a whole day, the major problem is that I can't convey a value properly inside the recursive function. I added some code that fixed one problem. But as it works for every recursive loop, new problems arose. More fixes lead to more bugs, a vicious cycle.

And then I went for help to itertools.combination's source code. And it turns out it didn't use recursion technique.

Do you think it is possible to abstract this combine_5 function into a combine_n function with recursion technique? Do you have any ideas about its realization?

FAILURE SAMPLE 1:

def combine_n(elements, r, cur_index=-1):
    """Find all combinations in elements with range n"""
    r -= 1 
    target_list = elements[cur_index+1 : ]
    for i in target_list:
        cur_index = elements.index(i)
        if r > 0:
            combine_n(elements, r, cur_index)
            print i
        else:
            print i

This is my recent try after a bunch of overcomplicated experiments.
The core ideas is: if I can print them right, I can collect them into a container later.
But the problem is, in a nested for loop, when the lower for-loop hit with an empty list.
The temp_list.append((i,j,k,n,m)) clause of combine_5 will not work.
But in FAILURE SAMPLE 1, it still will print the content of the upper for-loop
like combine_n([0,1], 2) will print 2, 1, 2.
I need to find a way to convey this empty message to the superior for-loop.
Which I didn't figure out so far.

Upvotes: 1

Views: 110

Answers (1)

samgak
samgak

Reputation: 24427

Yes, it's possible to do it with recursion. You can make combine_n return a list of tuples with all the combinations beginning at index cur_index, and starting with a partial combination of cur_combo, which you build up as you recurse:

def combine_n(elements, r, cur_index=0, cur_combo=()):
    r-=1
    temp_list = []
    for elem_index in range(cur_index, len(elements)-r):
        i = elements[elem_index]
        if r > 0:
            temp_list = temp_list + combine_n(elements, r, elem_index+1, cur_combo+(i,))
        else:
            temp_list.append(cur_combo+(i,))
    return temp_list

elements = list(range(1,6))
print = combine_n(elements, 3)

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

The for loop only goes up to len(elements)-r, because if you go further than that then there aren't enough remaining elements to fill the remaining places in the tuple. The tuples only get added to the list with append at the last level of recursion, then they get passed back up the call stack by returning the temp_lists and concatenating at each level back to the top.

Upvotes: 1

Related Questions