How to output all possible combinations using loops in Ruby?

Question

I just started to learn programming and am trying to write a function that outputs all possible combinations. So far I've been able to find all possible combinations of size 2 but I'm not sure how to leave the code open ended to deal with combinations of larger sizes. Would some sort of recursion would be useful?

I know I could use the built in combination method but I'm just trying to figure out how to write it from scratch. Any advice would be much appreciated. Thanks!

def two_combos(input)
    list = []
    for index1 in (0...input.length)
        for index2 in (0...input.length)
            if input[index1] != input[index2]
                if list.include?([input[index2],input[index1]])==false
                    list << [input[index1],input[index2]]
                end
            end
        end
    end
    return list
end


two_combos(["A","B","C"])
#outputs
=> [["A", "B"], ["A", "C"], ["B", "C"]]
#Missing
["A","B","C"]

Answer 1

This implementation is like counting recursively in binary:

def combinations(items)
  return [] unless items.any?
  prefix = items[0]
  suffixes = combinations(items[1..-1])
  [[prefix]] + suffixes + suffixes.map {|item| [prefix] + item }
end

> combinations(%w(a b c))
=> [["a"], ["b"], ["c"], ["b", "c"], ["a", "b"], ["a", "c"], ["a", "b", "c"]]

At each stage, the combinations are a concatenation of:

• the first element alone
• the combinations of the following elements (elements 1..n-1)
• the first element combined with the combinations of the following elements

Answer 2

Here is recursive algorithm

def combinations(array, size)
  fail "size is too big" if size > array.size

  combination([], [], array, size)
end

def combination(result, step, array, size)
  steps = size - step.size
  array[0..-steps].each_with_index do |a, i|
    next_step = step + [a]
    if next_step.size < size
      combination(result, next_step, array[i+1..-1], size)
    else
      result << next_step
    end
  end
  result
end

a = ("A".."E").to_a
p combinations(a, 1)
# [["A"], ["B"], ["C"], ["D"], ["E"]]
p combinations(a, 2)
# [["A", "B"], ["A", "C"], ["A", "D"], ["A", "E"], ["B", "C"], ["B", "D"], ["B", "E"], ["C", "D"], ["C", "E"], ["D", "E"]]
p combinations(a, 3)
# [["A", "B", "C"], ["A", "B", "D"], ["A", "B", "E"], ["A", "C", "D"], ["A", "C", "E"], ["A", "D", "E"], ["B", "C", "D"], ["B", "C", "E"], ["B", "D", "E"], ["C", "D", "E"]]
p combinations(a, 4)
# [["A", "B", "C", "D"], ["A", "B", "C", "E"], ["A", "B", "D", "E"], ["A", "C", "D", "E"], ["B", "C", "D", "E"]]