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)

[duerst (Martin Dürst)]

I don't think this is necessary. It's better to keep different aspects of a calculation separate by using separate methods (building blocks) and combining them to achieve a goal. As an example, your
a.permutation(*1..3).to_a
can easily be written as
(1..3).flat_map { |i| a.permutation(i).to_a }.
(Please note that flat_map is already a combination of two methods, but this was introduced because this combination is really frequent, contrary to yours.)

[toy (Ivan Kuchin)]

@duerst (Martin Dürst) When final number of permutations is small - there is no problem materialising all of them and joining in one array using flat_map, but when number of permutations/combinations is big and there is no need to get all results in memory, using flat_map would be wasteful.

So for example following would be compact and efficient:

alphabet = [*'a'..'z']

alphabet.repeated_permutation(*3..6).find{ … }

Doing same with flat_map will take long time to materialise all permutations:

(3..6).flat_map{ |i| alphabet.repeated_permutation(i).to_a }.find{ … }

It is possible to resolve this using lazy:

(3..6).lazy.flat_map{ |i| alphabet.repeated_permutation(i).lazy }.find{ … }

Or using chain:

Enumerator::Chain.new(*(3..6).map{ |i| alphabet.repeated_permutation(i) }).find{ … }

But I think both are harder to write and read