CODEWITHSUNDEEP
arraysrubyalgorithmcombinationsinstance-eval
boggy
boggy

Reputation: 302

Shortest code for getting all K-item combinations of N-item array, where K <= N

What is the shortest way of getting all K-item combinations of an N-item array where K <= N? I managed to write down the one below :

 > [1,2,3].instance_eval "(1..size).flat_map {|i| self.combination(i).to_a }"

=> [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Any ideas how to get rid of "instance_eval"? It doesn't seem to be very elagant :\

Upvotes: 1

Views: 142

Answers (4)

Cary Swoveland
Cary Swoveland

Reputation: 110655

arr = [1,2,3,4]

(2**arr.size).times.map do |i|
  arr.each_with_index.with_object([]) { |(e,j),a| a << e if i[j] == 1 }
end
  #=> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4],
  # [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]

You could, of course, sort the array that is returned however you like. For example:

(2**arr.size).times.map do |i|
  arr.each_with_index.with_object([]) { |(e,j),a| a << e if i[j] == 1 }
end.sort_by { |a| [a.size,a] }
  #=> [[],
  #    [1], [2], [3], [4],
  #    [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4],
  #    [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4],
  #    [1, 2, 3, 4]]

Upvotes: 1

spickermann
spickermann

Reputation: 106782

I would do something like this:

x = [1,2,3]
1.upto(x.size).flat_map { |i| x.combination(i).to_a }
#=> [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Upvotes: 2

lynn
lynn

Reputation: 10784

Here's a cool, short way to implement a "power set" function, if order/empty list doesn't matter:

>>> [nil].product(*[1, 2, 3].map { |x| [nil, x] }).map(&:compact)
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Upvotes: 2

sschmeck
sschmeck

Reputation: 7685

One version, hope it's correct.

x = [1, 2, 3]
1.upto(x.size).reduce([]) { |a, i| a + x.permutation(i).map(&:sort).uniq.to_a }
# => [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Upvotes: 0

Related Questions