Ruby – all permutations with any number of elements

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?

>Solution :

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

In your case, you just want all permutations of size 0, then 1, then 2, … 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]