Re: Fast powerset function

Discussion in 'Python' started by Evan Klitzke, Jul 13, 2007.

  1. Evan Klitzke

    Evan Klitzke Guest

    On 7/12/07, Arash Arfaee <> wrote:
    > I need a powerset generator function. It's really slow with recursion. Does
    > anybody have any idea or code(!!) to do it in an acceptable time?
    > Thanks
    > -Arash


    Here's a much simpler (and faster) solution I got from a coworker:

    s = range(18)
    result = []

    l = len(s)
    for i in range(2**l):
    n = i
    x = []
    for j in range(l):
    if n & 1:
    x.append(s[j])
    n >>= 1
    result.append(x)

    print result


    --
    Evan Klitzke <>
     
    Evan Klitzke, Jul 13, 2007
    #1
    1. Advertising

  2. 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
     
    Mark Dickinson, Jul 14, 2007
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. matt

    powerset operation

    matt, Jan 17, 2004, in forum: Perl
    Replies:
    0
    Views:
    1,298
  2. Tim Rowe

    Powerset

    Tim Rowe, Sep 15, 2003, in forum: Python
    Replies:
    0
    Views:
    535
    Tim Rowe
    Sep 15, 2003
  3. Gunnar G

    powerset

    Gunnar G, Aug 9, 2005, in forum: C++
    Replies:
    1
    Views:
    517
    Karl Heinz Buchegger
    Aug 9, 2005
  4. Evan Klitzke

    Re: Fast powerset function

    Evan Klitzke, Jul 13, 2007, in forum: Python
    Replies:
    6
    Views:
    998
    Carsten Haese
    Jul 13, 2007
  5. Evan Klitzke

    Re: Fast powerset function

    Evan Klitzke, Jul 13, 2007, in forum: Python
    Replies:
    0
    Views:
    424
    Evan Klitzke
    Jul 13, 2007
Loading...

Share This Page