On Sun, Nov 8, 2009 at 11:52 AM, Dan Bishop <danb...@yahoo.com> wrote: > On Nov 8, 4:43 am, Ozz <notva...@wathever.com> wrote: >> Hi, >> >> > My first question is: >> > 1. given a list of invoives I=[500, 400, 450, 200, 600, 700] and a >> > check Ch=600 >> > how can I print all the different combinations of invoices that the >> > check is possibly cancelling >> >> Incidentally, I'm currently learning python myself, and was working on >> more or less the same problem as an exercise; >> >> For listing all different subsets of a list (This is what I came up >> with. Can it be implemented shorter, btw?): >> >> def subsets(L): >> S = [] >> if (len(L) == 1): >> return [L, []] >> else: >> for s in subsets(L[1:]): >> S.append(s) >> S.append(s + [ L[0]]) >> return S > > You can avoid the S list my making it a generator: > > def subsets(L): > if L: > for s in subsets(L[1:]): > yield s > yield s + [L[0]] > else: > yield []
What you're describing is the powerset operation. Here's the example from the python docs: def powerset(iterable): "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" s = list(iterable) return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) What I find interesting is that running it through timeit, it is much slower than the code suggested by Dan Bishop. setup = """ from itertools import chain, combinations x = list(range(100)) def subsets1(L): S = [] if (len(L) == 1): return [L, []] else: for s in subsets1(L[1:]): S.append(s) S.append(s + [ L[0]]) return S def subsets2(L): if L: for s in subsets(L[1:]): yield s yield s + [L[0]] else: yield [] def subsets3(iterable): s = list(iterable) return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) """ #timeit.timeit("subsets1(x)", setup) doesn't appear to terminate timeit.timeit("subsets2(x)", setup) timeit.timeit("subsets3(x)", setup) I'm getting numbers roughly 3:1 in Dan's favor. Geremy Condra -- http://mail.python.org/mailman/listinfo/python-list