Fast powerset function

[Arash Arfaee]

Hi All

With your help I found lots of good method and algorithm. Also I found out
if I exchange all for loop with while loop it make the program much faster
and also it consumes less memory (almost half!)
Just wanna thank you all.
Cheers,
Arash

On 7/13/07, Mark Dickinson <dickinsm at gmail.com> wrote:
>
> If you don't care about the order of the results, you can use a Gray
> code (http://en.wikipedia.org/wiki/Gray_code): this has the advantage
> of only adding or removing a single element to get from one subset to
> the next.
>
> def powerset(s):
>     d = dict(zip(
>             (1<<i for i in range(len(s))),
>             (set([e]) for e in s)
>             ))
>
>     subset = set()
>     yield subset
>     for i in range(1, 1<<len(s)):
>         subset = subset ^ d[i & -i]
>         yield subset
>
> >>> list(powerset('abc'))
> [set([]), set(['a']), set(['a', 'b']), set(['b']), set(['c', 'b']),
> set(['a', 'c', 'b']), set(['a', 'c']), set(['c'])]
>
> If you're using the subsets as they appear and don't need to store
> them all at once, then it's significantly faster (on my machine) if
> you replace the line subset = subset ^ d[i & -i] with an in-place
> update:  subset ^= d[i & -i].
>
> Mark
>
>
> --
> http://mail.python.org/mailman/listinfo/python-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20070718/911ade30/attachment.html>