How to make combinations of an array to produce all possible expressions?

Discussion in 'Ruby' started by Erik Terpstra, May 13, 2004.

  1. I have an array 'conds', which contains some sub-expressions for an
    xpath query:

    conds = ["@title='Foo'", "@edition='Bar'", "@date='20040513'"]

    Is there an existing library that lets me construct all possible
    combinations like this?

    puts conds.<some Array extension method>.collect{|n| n.join ' and '}

    which produces:

    @title='Foo' and @edition='Bar' and @date='20040513'
    @title='Foo' and @edition='Bar'
    @title='Foo' and @date='20040513'
    @edition='Bar' and @date='20040513'
    @title='Foo'
    @edition='Bar'
    @date='20040513'
     
    Erik Terpstra, May 13, 2004
    #1
    1. Advertising

  2. "Erik Terpstra" <> schrieb im Newsbeitrag
    news:40a333fc$0$65124$4all.nl...
    > I have an array 'conds', which contains some sub-expressions for an
    > xpath query:
    >
    > conds = ["@title='Foo'", "@edition='Bar'", "@date='20040513'"]
    >
    > Is there an existing library that lets me construct all possible
    > combinations like this?
    >
    > puts conds.<some Array extension method>.collect{|n| n.join ' and '}
    >
    > which produces:
    >
    > @title='Foo' and @edition='Bar' and @date='20040513'
    > @title='Foo' and @edition='Bar'
    > @title='Foo' and @date='20040513'
    > @edition='Bar' and @date='20040513'
    > @title='Foo'
    > @edition='Bar'
    > @date='20040513'


    Not yet, but:

    module Enumerable
    def combine
    masks = inject([[], 1]){|(ar, m), e| [ar<<m, m<<1]}[0]
    all = masks.inject(0){|al, m| al|m}

    result = []

    for i in 1..all do
    tmp = []

    each_with_index do |e, idx|
    tmp << e unless (masks[idx] & i) == 0
    end

    result << tmp
    end

    result
    end
    end


    irb(main):098:0> puts conds.combine.collect{|n| n.join ' and '}
    @title='Foo'
    @edition='Bar'
    @title='Foo' and @edition='Bar'
    @date='20040513'
    @title='Foo' and @date='20040513'
    @edition='Bar' and @date='20040513'
    @title='Foo' and @edition='Bar' and @date='20040513'
    => nil

    robert
     
    Robert Klemme, May 13, 2004
    #2
    1. Advertising

  3. Erik Terpstra

    Harry Ohlsen Guest

    Re: How to make combinations of an array to produce all possibleexpressions?

    Erik Terpstra wrote:

    > I have an array 'conds', which contains some sub-expressions for an
    > xpath query:
    >
    > conds = ["@title='Foo'", "@edition='Bar'", "@date='20040513'"]

    <snip>

    There's no method I know of, but this seems to work (note that I've explicitly avoided generating an empty set, because you didn't have one in your example, but it should probably be included if we wanted to call this method "subsets" as I have) ...

    module Enumerable
    def subsets
    values = []

    (2 << length - 1).times do |n|
    items = []

    length.times do |i|
    if n == 1
    items << self
    end
    end

    if items.length > 0 # I'd omit this test for a real "subsets"
    values << items
    end
    end

    return values
    end
    end

    conds = ["@title='Foo'", "@edition='Bar'", "@date='20040513'"]

    conds.subsets.collect { |subset| p subset.join(" and ") }
     
    Harry Ohlsen, May 13, 2004
    #3
  4. "Harry Ohlsen" <> schrieb im Newsbeitrag
    news:...
    > Erik Terpstra wrote:
    >
    > > I have an array 'conds', which contains some sub-expressions for an
    > > xpath query:
    > >
    > > conds = ["@title='Foo'", "@edition='Bar'", "@date='20040513'"]

    > <snip>
    >
    > There's no method I know of, but this seems to work (note that I've

    explicitly avoided generating an empty set, because you didn't have one in
    your example, but it should probably be included if we wanted to call this
    method "subsets" as I have) ...
    >
    > module Enumerable
    > def subsets
    > values = []
    >
    > (2 << length - 1).times do |n|
    > items = []
    >
    > length.times do |i|
    > if n == 1
    > items << self
    > end
    > end
    >
    > if items.length > 0 # I'd omit this test for a real "subsets"
    > values << items
    > end
    > end
    >
    > return values
    > end
    > end


    Ah, similar idea but nicer coding. I like especially your calculation of
    the counting range and int[idx] as bit test. I didn't know that one.

    Btw, you don't need the test for length 0 if you do

    for n in 1 ... (2<<length) do
    ....

    Regards

    robert
     
    Robert Klemme, May 13, 2004
    #4
  5. On Thu, 13 May 2004 10:38:19 +0200, Erik Terpstra wrote:

    > I have an array 'conds', which contains some sub-expressions for an
    > xpath query:
    >
    > conds = ["@title='Foo'", "@edition='Bar'", "@date='20040513'"]


    Hi,
    I have found at least to ways.
    Using recursion (maybe not so efficient):

    class Array
    def combine
    comb = Proc.new do |a, *t|
    tail = (t.empty? ? [] : comb[t])
    [[a]] + tail.collect{ |e| [a] + e} + tail
    end
    comb[self]
    end
    end

    The following should perform better:

    class Array
    def combine2
    (1..(2**(size) - 1)).collect do |i|
    i <<= 1
    self.select { (i >>= 1) & 1 == 1}
    end
    end
    end

    irb(main):018:0> puts conds.combine.collect{|n| n.join ' and '}
    @title='Foo'
    @title='Foo' and @edition='Bar'
    @title='Foo' and @edition='Bar' and @date='20040513'
    @title='Foo' and @date='20040513'
    @edition='Bar'
    @edition='Bar' and @date='20040513'
    @date='20040513'
    => nil
    irb(main):019:0> puts conds.combine2.collect{|n| n.join ' and '}
    @title='Foo'
    @edition='Bar'
    @title='Foo' and @edition='Bar'
    @date='20040513'
    @title='Foo' and @date='20040513'
    @edition='Bar' and @date='20040513'
    @title='Foo' and @edition='Bar' and @date='20040513'
    => nil


    Kristof
     
    Kristof Bastiaensen, May 13, 2004
    #5
  6. Erik Terpstra

    Harry Ohlsen Guest

    Re: How to make combinations of an array to produce all possibleexpressions?

    Robert Klemme wrote:

    > Ah, similar idea but nicer coding.


    Coming from you, that's a much appreciated compliment!

    > I like especially your calculation of
    > the counting range and int[idx] as bit test. I didn't know that one.


    I discovered during a re-browse of pickaxe a couple of months ago, but this is the first time I've actually had a chance to use it.

    > Btw, you don't need the test for length 0 if you do
    >
    > for n in 1 ... (2<<length) do


    Good point.

    Something I was thinking about was that the power set (set of subsets) becomes large very quickly (obvious from the "2 << length", I guess). It might be nice to have an iterator, too. The method that returns the collection of subsets could then just use it.

    Something like this (I've removed the empty set test, since I think this is cleaner in a mathematical sense) ...

    module Enumerable
    def each_subset(&block)
    (2 << length - 1).times do |n|
    subset = []

    length.times do |i|
    if n == 1
    subset << self
    end
    end

    yield subset
    end
    end

    def subsets
    subsets = []

    each_subset { |s| subsets << s }

    return subsets
    end
    end

    if __FILE__ == $0

    conds = ["@title='Foo'", "@edition='Bar'", "@date='20040513'"]

    puts "Using iterator ..."
    puts

    conds.each_subset { |subset| p subset.join(" and ") }

    puts
    puts "Using aggregate ..."
    puts

    conds.subsets.collect { |subset| p subset.join(" and ") }

    end
     
    Harry Ohlsen, May 14, 2004
    #6
  7. "Harry Ohlsen" <> schrieb im Newsbeitrag
    news:...
    > Robert Klemme wrote:
    >
    > > Ah, similar idea but nicer coding.

    >
    > Coming from you, that's a much appreciated compliment!


    You're welcome! :)

    > > I like especially your calculation of
    > > the counting range and int[idx] as bit test. I didn't know that one.

    >
    > I discovered during a re-browse of pickaxe a couple of months ago, but

    this is the first time I've actually had a chance to use it.
    >
    > > Btw, you don't need the test for length 0 if you do
    > >
    > > for n in 1 ... (2<<length) do

    >
    > Good point.
    >
    > Something I was thinking about was that the power set (set of subsets)

    becomes large very quickly (obvious from the "2 << length", I guess). It
    might be nice to have an iterator, too. The method that returns the
    collection of subsets could then just use it.

    Another good point!

    > Something like this (I've removed the empty set test, since I think this

    is cleaner in a mathematical sense) ...

    That might be handled by an additional flag with a default value (which
    one, the mathematical or the practical?). Practically you often don't
    need / want the empty set.

    Funny to see how this evolves. My current vesion looks like this:

    module Enumerable
    def each_subset(skip_empty = false)
    for n in (skip_empty ? 1 : 0) ... (1 << size) do
    subset = []

    each_with_index do |elem, i|
    subset << elem if n
    end

    yield subset
    end

    self
    end

    def powerset(skip_empty = false)
    subsets = []

    each_subset(skip_empty) { |s| subsets << s }

    return subsets
    end
    end


    Changes / Improvements:

    - self[index] is not used since it is not available with all Enumerables
    - flag 'skip_empty' added
    - self returned from iterator
    - renamed #subsets to #powerset (this is the mathematical correct term,
    isn't it)
    - changed (2 << length - 1) to (1 << length)

    Here's another experimental version that works even if #size is not
    supported. This really needs only #each. Alternatively one could do an
    initial iteration to calculate the size - that saves the intermediate
    array.

    module Enumerable
    def each_subset(skip_empty = false)
    enum = respond_to?( :size ) ? self : to_a

    for n in (skip_empty ? 1 : 0) ... (1 << enum.size) do
    subset = []

    enum.each_with_index do |elem, i|
    subset << elem if n == 1
    end

    yield subset
    end

    self
    end

    def powerset(skip_empty = false)
    subsets = []

    each_subset(skip_empty) { |s| subsets << s }

    return subsets
    end
    end

    # test class
    class Test
    include Enumerable

    def initialize(n); @n=n; end
    def each; @n.times {|c| yield c}; self; end
    end

    p Test.new(3).powerset


    Kind regards

    robert
     
    Robert Klemme, May 14, 2004
    #7
  8. Re: How to make combinations of an array to produce all possibleexpressions?

    > module Enumerable
    > def each_subset(skip_empty = false)
    > enum = respond_to?( :size ) ? self : to_a
    >
    > for n in (skip_empty ? 1 : 0) ... (1 << enum.size) do
    > subset = []
    >
    > enum.each_with_index do |elem, i|
    > subset << elem if n == 1
    > end
    >
    > yield subset
    > end
    >
    > self
    > end
    >
    > def powerset(skip_empty = false)
    > subsets = []
    >
    > each_subset(skip_empty) { |s| subsets << s }
    >
    > return subsets
    > end


    irb(main):013:0> def powerset( x )
    irb(main):014:1> x.inject([[]]) {|m, n| m.map {|b| [n] + b} + m }
    irb(main):015:1> end
    irb(main):017:0> a = [1,2,3]
    => [1, 2, 3]
    irb(main):018:0> powerset a
    => [[3, 2, 1], [3, 2], [3, 1], [3], [2, 1], [2], [1], []]
    irb(main):019:0>

    Only works for arrays, but it might be possible to generalize it?
     
    Linus Sellberg, May 14, 2004
    #8
  9. Erik Terpstra

    Harry Ohlsen Guest

    Re: How to make combinations of an array to produce all possibleexpressions?

    Robert Klemme wrote:
    > Funny to see how this evolves. My current vesion looks like this:
    >
    > module Enumerable
    > def each_subset(skip_empty = false)
    > for n in (skip_empty ? 1 : 0) ... (1 << size) do
    > subset = []
    >
    > each_with_index do |elem, i|
    > subset << elem if n
    > end
    >
    > yield subset
    > end
    >
    > self
    > end
    >
    > def powerset(skip_empty = false)
    > subsets = []
    >
    > each_subset(skip_empty) { |s| subsets << s }
    >
    > return subsets
    > end
    > end


    The first version in your latest e-mail didn't work for me. It just gave me the complete array every time.

    I think it's because when n is zero, that's not the same as false, hence the "if" always succeeds.

    You just need to change that line to

    subset << elem if (n == 1)

    The second version worked fine.

    I like all of your clean-ups. I wonder whether re-coding in C would increase performance?

    Anyway, it might be worth creating an RCR to have this added to Enumerable.

    Cheers,

    Harry O.
     
    Harry Ohlsen, May 17, 2004
    #9
  10. "Harry Ohlsen" <> schrieb im Newsbeitrag
    news:...

    > The first version in your latest e-mail didn't work for me. It just

    gave me the complete array every time.
    >
    > I think it's because when n is zero, that's not the same as false,

    hence the "if" always succeeds.
    >
    > You just need to change that line to
    >
    > subset << elem if (n == 1)
    >
    > The second version worked fine.


    Yeah, I noticed the error but apparently didn't recheck the first version.
    You're right of course.

    > I like all of your clean-ups.


    Thank you!

    > I wonder whether re-coding in C would increase performance?


    Dunno. I didn't write a ruby extension yet but I heard it's pretty easy.
    :)

    > Anyway, it might be worth creating an RCR to have this added to

    Enumerable.

    Maybe. The crucial point is, is this general enough to place it there?
    Well, the vote might show it.

    Regards

    robert
     
    Robert Klemme, May 17, 2004
    #10
    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. rbt

    all possible combinations

    rbt, Jul 13, 2005, in forum: Python
    Replies:
    36
    Views:
    21,523
    Steve Holden
    Jul 28, 2005
  2. Replies:
    16
    Views:
    809
    Scott David Daniels
    May 31, 2006
  3. Replies:
    5
    Views:
    483
    Luc The Perverse
    Oct 27, 2006
  4. Teme Rosi

    All possible letter combinations?

    Teme Rosi, Dec 11, 2008, in forum: Ruby
    Replies:
    3
    Views:
    225
    Martin Carpenter
    Dec 16, 2008
  5. Ed W.
    Replies:
    1
    Views:
    145
    J├╝rgen Exner
    Oct 22, 2003
Loading...

Share This Page