Generating combinations from multiple sets

Discussion in 'Ruby' started by Srinivas Jonnalagadda, Jan 16, 2006.

  1. Dear all,

    I have a requirement as below.

    There are 'n' containers of lengths {l_i}, i = 1,..,n. All these
    containers are collected into an array. Picking one element at a time
    from each container, an array has to be constructed and either yielded
    or accumulated.

    I have written the following code that seems to work reasonably. Are
    there simpler or more efficient ways of doing this?

    Thanks in advance,

    JS

    * * * *

    def generate_combinations(cont_ary, &blk)

    cont_count = cont_ary.length

    return if cont_count < 1

    if cont_count == 1
    if block_given?
    cont_ary[0].each { | el | yield [el] }
    return
    else
    return cont_ary[0].collect { | el | [el] }
    end
    end

    cur_indices = Array.new(cont_count, 0)
    combinations = []

    generate_combinations_iterator(cont_ary, 0, cur_indices,
    :working_set => Array.new(cont_count),
    :accumulator => combinations,
    &blk)

    return combinations unless block_given?

    end

    #

    def generate_combinations_iterator(cont_ary, cur_cont, cur_indices, opts
    = {}, &blk)

    cont_ary[cur_cont].each_with_index do | el, i |

    opts[:working_set][cur_cont] = el

    case cur_cont
    when 0
    cur_indices[cur_cont] = i
    (1...cur_indices.length).each { | j | cur_indices[j] = 0 }
    generate_combinations_iterator(cont_ary, cur_cont + 1,
    cur_indices, opts, &blk)

    when cont_ary.length-1
    if block_given?
    yield opts[:working_set]
    else
    opts[:accumulator] << Array.new(opts[:working_set])
    end

    else
    cur_indices[cur_cont] = i
    generate_combinations_iterator(cont_ary, cur_cont + 1,
    cur_indices, opts, &blk)
    end

    end

    end

    #

    Output
    ------

    irb(main):011:0> load 'combination-generator.rb'
    => true

    irb(main):012:0> ary1 = []
    => []

    irb(main):013:0> generate_combinations(ary1)
    => nil

    irb(main):014:0> ary2 = [[1, 2, 3, 4]]
    => [[1, 2, 3, 4]]

    irb(main):015:0> pp generate_combinations(ary2)
    [[1], [2], [3], [4]]
    => nil

    irb(main):016:0> ary3 = [[1, 2, 3, 4], ['a', 'b', 'c']]
    => [[1, 2, 3, 4], ["a", "b", "c"]]

    irb(main):017:0> pp generate_combinations(ary3)
    [[1, "a"],
    [1, "b"],
    [1, "c"],
    [2, "a"],
    [2, "b"],
    [2, "c"],
    [3, "a"],
    [3, "b"],
    [3, "c"],
    [4, "a"],
    [4, "b"],
    [4, "c"]]
    => nil
    Srinivas Jonnalagadda, Jan 16, 2006
    #1
    1. Advertising

  2. Thank you!

    Preliminary testing seems to show that it indeed is faster. I think it
    is understandable since it is doing inline expansion, rather than
    recursion.

    Nice use of code generation.

    Best regards,

    JS

    Robert Klemme wrote:
    > In case the gateway is broken again:
    >
    > I have a shorter alternative; it may be more efficient but you'll have to
    > test that for yourself:
    >
    > def all_combinations(enum,&bl)
    > pre = ""
    > post = ""
    > middle = []
    > enum.each_with_index do |en,idx|
    > item = "e#{idx}"
    > pre << "enum[" << idx.to_s << "].each {|" << item << "| "
    > middle << item
    > post << "}"
    > end
    > eval(pre << "bl[" << middle.join(",") << "]" << post)
    > end
    >
    > irb(main):053:0> all_combinations([[1,2,3],%w{a b c d}]) {|*a| p a}
    > [1, "a"]
    > [1, "b"]
    > [1, "c"]
    > [1, "d"]
    > [2, "a"]
    > [2, "b"]
    > [2, "c"]
    > [2, "d"]
    > [3, "a"]
    > [3, "b"]
    > [3, "c"]
    > [3, "d"]
    > => [1, 2, 3]
    >
    > You can even change this to work with arbitrary Enumerables - this version
    > depens on "enum" being an Array.
    >
    > Kind regards
    >
    > robert
    >
    Srinivas Jonnalagadda, Jan 16, 2006
    #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. Alex Vinokur
    Replies:
    2
    Views:
    2,791
    Alex Vinokur
    May 13, 2004
  2. Replies:
    16
    Views:
    779
    Scott David Daniels
    May 31, 2006
  3. Generating combinations

    , Dec 6, 2006, in forum: ASP .Net
    Replies:
    1
    Views:
    329
    mark carew
    Dec 7, 2006
  4. johkar
    Replies:
    6
    Views:
    922
    johkar
    Apr 19, 2009
  5. Replies:
    1
    Views:
    105
Loading...

Share This Page