CODEWITHSUNDEEP
arraysrubyalgorithmrecursionmultidimensional-array
marinatedpork
marinatedpork

Reputation: 189

How to recursively find permutations of two dimensional array in Ruby

I have an array with elements that are arrays of varying sizes. For example:

[[3],[11,2],[11,2],[3]]

I would like to find permutations of all of the individual items in the nested arrays. For the array above, I'd like a return value of:

[
  [3, 11, 11, 3],
  [3, 11, 2, 3],
  [3, 2, 11, 3],
  [3, 2, 2, 3]
]

I have a solution that works, but it seems particularly long-winded:

array = [[3],[11,2],[11,2],[3]]
array.product(*array).map { |e| e.drop(1) }.uniq

How should I implement a recursive approach to this, and how would that work? I am having trouble wrapping my head around this.

Upvotes: 2

Views: 312

Answers (2)

Cary Swoveland
Cary Swoveland

Reputation: 110675

The conventional way of solving this problem is to use the methods Array#product and Array#drop.

arr = [[3], [11,2], [11,2,7], [4]]

arr.first.product(*arr.drop(1))
  #=> [[3, 11, 11, 4], [3, 11, 2, 4], [3, 11, 7, 4],
  #    [3, 2, 11, 4], [3, 2, 2, 4], [3, 2, 7, 4]]

If any element of arr contains duplicates the return value will also contain duplicates. If duplicates are not wanted, use

arr.map(&:uniq).first.product(*arr.drop(1))

The asker has, however, requested a recursive solution. That could be written as follows:

def prod(arr)
  return arr if arr.size == 1
  t = prod(arr.drop(1))
  arr.first.flat_map { |x| t.map { |a| [x] + a } }
end

prod arr
  #=> [[3, 11, 11, 4], [3, 11, 2, 4], [3, 11, 7, 4],
  #    [3, 2, 11, 4], [3, 2, 2, 4], [3, 2, 7, 4]]

Upvotes: 5

aqfaridi
aqfaridi

Reputation: 739

Initialization: 

@arr = [[3],[11,2],[11,2],[3]]
@perms = []

Function Definition:

def recursion(idx, temp = [])
    if (idx == @arr.size) then @perms.push(temp.clone); return end
    @arr[idx].each { |x|  recursion(idx+1, temp << x); temp.pop }
end

Call :

recursion(0)
p @perms
 => [[3, 11, 11, 3], [3, 11, 2, 3], [3, 2, 11, 3], [3, 2, 2, 3]]

Upvotes: 1

Related Questions