Ruby - all permutations with any number of elements

Question

I want to transform the array [3, 4, 8] → [3, 4, 8, 34, 38, 48, 43, 83, 84, 348, 384, 834, 843, 438, 483]

I tried array.permutation but this only returns [348, 384, 834, 843, 438, 483]. Is there a clean way of doing this without generating every possible subset first?

Answer 1

Array#permutation takes one optional parameter telling it what maximum permutation size to create.

In your case, you just want all permutations of size 1, then 2, then 3, ... up to your input.count.

So it's as simple as creating a range of those numbers, mapping over them calling permutation with a different number each time, and combining the results:

def all_permutations_of(input)
  (1..input.count).flat_map do |permutation_length|
    input.permutation(permutation_length).to_a
  end
end

p all_permutations_of([3, 4, 8])
# => [
#   [3], [4], [8],
#   [3, 4], [3, 8], [4, 3], [4, 8], [8, 3], [8, 4],
#   [3, 4, 8], [3, 8, 4], [4, 3, 8], [4, 8, 3], [8, 3, 4], [8, 4, 3],
# ]

And if you want those digits as actual numbers like you show in your example, you'll need a little function to combine them together, like this one I affectionately call "smoosh":

# Produces a single number from an array of digits
# E.g. `[1, 2, 3]` becomes `123`
def smoosh(digits)
  exponent = digits.count
  
  digits.sum do |digit|
    exponent -= 1
    digit * (10 ** exponent)
  end
end

p all_permutations_of([3, 4, 8]).map { smoosh(_1) }
# => [3, 4, 8, 34, 38, 43, 48, 83, 84, 348, 384, 438, 483, 834, 843]