Ruby Combinations with array elements

Question

Ok, i've searched the internet for answers and also searched for hours in my ruby programmer but i cant sort this out. I'm writing a script for making all sorts of combinations from elements in an array.

ar = ["a","b","c","d"]

At this point I am able to make these combinations:

["a"],["a","b"],["a","b","c"],["a","b","c","d"],["b"],["b","c"],["b","c","d"],["c"],["c","d"],["d"]

This is OK, but I can't find a way for searching these combinations, for example ["a","c"] or ["a","c","d"] or ["a","d"], etc...

For now my code looks like:

def combinaties(array)
  combinaties = []
  i=0
  while i <= array.length-1
    combinaties << array[i]
    unless i == array.length-1
      array[(i+1)..(array.length-1)].each{|volgend_element|
        combinaties<<(combinaties.last.dup<<volgend_element)
      }
    end
    i+=1
  end
end

are you looking for permutations? You could try that with the array indexes. — three
– three, Commented Jan 4, 2012 at 22:06
Are you looking for a powerset? stackoverflow.com/questions/8533336/… — steenslag
– steenslag, Commented Jan 4, 2012 at 22:36
@steenslag yup, could't recall whether it was in Array or not :) — three
– three, Commented Jan 4, 2012 at 23:23

tokland · Accepted Answer · 2013-03-15 09:35:45Z

9

Functional approach (needs Ruby >= 1.9) to create the powerset of an array (except for the empty element you don't seem to need):

xs = ["a", "b", "c", "d"]
yss = 1.upto(xs.size).flat_map do |n|
  xs.combination(n).to_a
end

#[
#  ["a"], ["b"], ["c"], ["d"],
#  ["a", "b"], ["a", "c"], ["a", "d"], ["b", "c"], ["b", "d"], ["c", "d"],
#  ["a", "b", "c"], ["a", "b", "d"], ["a", "c", "d"], ["b", "c", "d"],
#  ["a", "b", "c", "d"],
#]

edited Mar 15, 2013 at 9:35

answered Jan 4, 2012 at 22:28

tokland

68.2k13 gold badges151 silver badges174 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

KenGey Over a year ago

That looks like what I need! Only thing is that I'm stuck with Ruby 1.8.6... It's for a Google SketchUp plugin that I'm working on so upgrading Ruby is not an option. Thanks for the response anyway! Greetings

michael_wu · Accepted Answer · 2012-01-05 14:04:10Z

4

There is a trivial correspondence (bijection) between such combinations and the numbers in [1..(2^m - 1)] (m being the array length).

Consider such a number n. It's binary representation has m digits (including leading zeros). The positions of the digits that are 1 are the indices of the elements in the corresponding combination.

The code would be:

def combinations(array)
  m = array.length
  (1...2**m).map do | n |
    (0...m).select { | i | n[i] == 1 }.map { | i | array[i] }
  end
end

edited Jan 5, 2012 at 14:04

answered Jan 4, 2012 at 22:08

michael_wu

16k5 gold badges66 silver badges77 bronze badges

1 Comment

Michael Kohl Over a year ago

You can use bitwise indexing into integers in Ruby to find out if a certain bit is 1, which leads to simpler code: stackoverflow.com/a/8535241/220147

Frederick Cheung · Accepted Answer · 2012-01-04 22:29:04Z

2

Or in ruby 1.9

%w(a b c d e).combination(3).to_a

will give you all the combinations of size 3.

answered Jan 4, 2012 at 22:29

Frederick Cheung

84.3k9 gold badges157 silver badges175 bronze badges

1 Comment

KenGey Over a year ago

Same problem here, I'm stuck with Ruby 1.8.6... Thanks for the response!

Collectives™ on Stack Overflow

Ruby Combinations with array elements

3 Answers 3

1 Comment

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related