Posts

Showing posts from February, 2013

generate all subsets using recursion | how to

Yesterday I wrote another program to generate all subsets of a set (array / list) during my preparation for today's class on backtracking at National Programming Camp. I wrote the code in C but just converted it into Python for the readers of the blog, so that they can understand and appreciate the beauty of recursion / backtracking. taken = [] def process(X): print X def generate_all_subsets(li, X, i, k, m): process(X[0:i]) for j in range(k, m): if taken[j] == False: if i > 0: if li[j] <= X[i-1]: continue taken[j] = True X.append(li[j]) generate_all_subsets(li, X, i+1, j+1, m) taken[j] = False X.pop(i) if __name__ == "__main__": li = [1, 2, 3, 4] X = [] taken.extend([False, False, False, False]) generate_all_subsets(li,

generate permutation using recursion | how to

Here is a Python program to generate all permutations using recursion. I just wrote the code while preparing for a class in national programming camp. If you study it carefully, you will have some idea about backtracking. taken = [] def process(X): print X def recurse(li, X, i, n): if i == n: process(X[0:i]) else: for j in range(0, n): if taken[j] == False: taken[j] = True X.append(li[j]) recurse(li, X, i+1, n) taken[j] = False X.pop(i) if __name__ == "__main__": li = [1, 2, 3, 4] X = [] taken.extend([False, False, False, False]) print taken recurse(li, X, 0, li.__len__())