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, Jan 04 '12 at 22:06
@three Class Array has a [permutation method](http://ruby-doc.org/core-1.9.3/Array.html#method-i-permutation). — steenslag, Jan 04 '12 at 22:32
Are you looking for a powerset? http://stackoverflow.com/questions/8533336/generate-a-powerset-of-a-set-without-keeping-a-stack-in-erlang-or-ruby — steenslag, Jan 04 '12 at 22:36
@steenslag yup, could't recall whether it was in Array or not :) — three, Jan 04 '12 at 23:23

tokland · Answer 1 · 2013-03-15T09:35:45.077

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 '13 at 09:35

answered Jan 04 '12 at 22:28

tokland

66,169
13
144
170

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 – KenGey Jan 05 '12 at 14:28

undur_gongor · Accepted Answer · 2012-01-05T14:04:10.830

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 05 '12 at 14:04

answered Jan 04 '12 at 22:08

undur_gongor

15,657
5
63
75

1

You can use bitwise indexing into integers in Ruby to find out if a certain bit is 1, which leads to simpler code: http://stackoverflow.com/a/8535241/220147 – Michael Kohl Jan 05 '12 at 13:54

score 2 · Answer 3 · answered Jan 04 '12 at 22:29

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 04 '12 at 22:29

Frederick Cheung

83,189
8
152
174

Same problem here, I'm stuck with Ruby 1.8.6... Thanks for the response! – KenGey Jan 05 '12 at 14:28

Ruby Combinations with array elements

3 Answers3