Feature #21564: Extend permutation, repeated_permutation, combination and repeated_combination arguments

• Status: Open
• Assignee: -
• Target version: -

[toy (Ivan Kuchin)]

When using functions permutation, repeated_permutation, combination and repeated_combination, often one needs not one, but multiple permutation/combination sizes. Currently all functions accept one Integer argument (for permutation it is optional and defaults to array size), and it would be more powerful (not require iteration of lengths and possibly flattening) if it would accept multiple lengths:

a = [1, 2, 3]

a.permutation(*1..3).to_a # => [[1], [2], [3],
                          #     [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2],
                          #     [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

a.permutation(1, 3).to_a # => [[1], [2], [3],
                         #     [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

a.permutation(3, 1).to_a # => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1],
                         #     [1], [2], [3]]

a.repeated_permutation(2, 1).to_a # => [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3],
                                  #     [1], [2], [3]]

a.combination(*1..3).to_a # => [[1], [2], [3],
                          #     [1, 2], [1, 3], [2, 3],
                          #     [1, 2, 3]]

a.repeated_combination(*1..3).to_a # => [[1], [2], [3],
                                   #     [1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3],
                                   #     [1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 3, 3], [2, 2, 2], [2, 2, 3], [2, 3, 3], [3, 3, 3]]

# find right combination of letters
[*'a'..'z'].repeated_permutation(*3..6).find do |chars|
  correct_combination?(chars)
end

# naïve knapsack solution
def max_knapsack_value(items, weight_max)
  items.combination(*1..items.length)
    .map{ |items| [items.sum(&:weight), items.sum(&:value)] }
    .reject{ |weight_sum, _| weight_sum > weight_max }
    .max_by{ |_, value_sum| value_sum }
    &.last || 0
end

Hack in code to enhance current methods would be:

class Array
  %i[
    combination
    permutation
    repeated_combination
    repeated_permutation
  ].each do |method_name|
    alias_method "original_#{method_name}", method_name

    class_eval <<-RUBY, __FILE__, __LINE__ + 1
      def #{method_name}(*counts, &block)
        return to_enum(__method__, *counts) unless block

        counts.each do |count|
          original_#{method_name}(count, &block)
        end
      end
    RUBY
  end
end

[nobu (Nobuyoshi Nakada)]

I'm not sure whether this is a natural extension of permutation.

And why not array.permutation(count1, count2, count3)?
Is it important to support Range without splatting?

[mame (Yusuke Endoh)]

When proposing new features, I strongly recommend writing a use case. It should be as simple and relatable as possible, but if that is difficult, a concrete example that you are actually facing now and that demonstrates general applicability is acceptable. Appealing to conceptual benefits like "powerful" is weak.

[toy (Ivan Kuchin)]

• Subject changed from Extend permutation, repeated_permutation, combination and repeated_combination argument to Extend permutation, repeated_permutation, combination and repeated_combination arguments
• Description updated (diff)

@nobu (Nobuyoshi Nakada) I was not sure what to select, Enumerable or multiple arguments, changed the proposal to use multiple arguments

@mame (Yusuke Endoh) I've added few use cases

[toy (Ivan Kuchin)]

• Description updated (diff)