On Sun, Nov 8, 2009 at 12:31 PM, geremy condra <debat...@gmail.com> wrote:
> 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
>
I made a mistake copying it on line 18 of the above; it should be
subsets2, rather than just subsets.
Geremy Condra
--
http://mail.python.org/mailman/listinfo/python-list
