[ruby-core:123184] [Ruby Feature#21564] Extend permutation, repeated_permutation, combination and repeated_combination argument

[ruby-core:123184] [Ruby Feature#21564] Extend permutation, repeated_permutation, combination and repeated_combination argument

[toy (Ivan Kuchin) via ruby-core]

Issue #21564 has been reported by toy (Ivan Kuchin).

----------------------------------------
Feature #21564: Extend permutation, repeated_permutation, combination and repeated_combination argument
https://bugs.ruby-lang.org/issues/21564

* Author: toy (Ivan Kuchin)
* Status: Open
----------------------------------------
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 if it would accept also a range or a Enumerable:

```ruby
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]]
```

Ruby code to enhance current `permutation` would be:
```ruby
class Array
  alias_method :original_permutation, :permutation

  def permutation(counts, &block)
    return to_enum(__method__, counts) unless block

    if counts.is_a?(Enumerable)
      counts.each do |count|
        original_permutation(count, &block)
      end
    else
      original_permutation(counts, &block)
    end
  end
end
```



-- 
https://bugs.ruby-lang.org/
______________________________________________
 ruby-core mailing list -- ruby-core@ml.ruby-lang.org
 To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/

[ruby-core:123185] [Ruby Feature#21564] Extend permutation, repeated_permutation, combination and repeated_combination argument

[nobu (Nobuyoshi Nakada) via ruby-core]

Issue #21564 has been updated by 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?

----------------------------------------
Feature #21564: Extend permutation, repeated_permutation, combination and repeated_combination argument
https://bugs.ruby-lang.org/issues/21564#change-114516

* Author: toy (Ivan Kuchin)
* Status: Open
----------------------------------------
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 if it would accept also a range or a Enumerable:

```ruby
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]]
```

Ruby code to enhance current `permutation` would be:
```ruby
class Array
  alias_method :original_permutation, :permutation

  def permutation(counts, &block)
    return to_enum(__method__, counts) unless block

    if counts.is_a?(Enumerable)
      counts.each do |count|
        original_permutation(count, &block)
      end
    else
      original_permutation(counts, &block)
    end
  end
end
```



-- 
https://bugs.ruby-lang.org/
______________________________________________
 ruby-core mailing list -- ruby-core@ml.ruby-lang.org
 To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/

[ruby-core:123186] [Ruby Feature#21564] Extend permutation, repeated_permutation, combination and repeated_combination argument

[mame (Yusuke Endoh) via ruby-core]

Issue #21564 has been updated by 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.

----------------------------------------
Feature #21564: Extend permutation, repeated_permutation, combination and repeated_combination argument
https://bugs.ruby-lang.org/issues/21564#change-114517

* Author: toy (Ivan Kuchin)
* Status: Open
----------------------------------------
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 if it would accept also a range or a Enumerable:

```ruby
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]]
```

Ruby code to enhance current `permutation` would be:
```ruby
class Array
  alias_method :original_permutation, :permutation

  def permutation(counts, &block)
    return to_enum(__method__, counts) unless block

    if counts.is_a?(Enumerable)
      counts.each do |count|
        original_permutation(count, &block)
      end
    else
      original_permutation(counts, &block)
    end
  end
end
```



-- 
https://bugs.ruby-lang.org/
______________________________________________
 ruby-core mailing list -- ruby-core@ml.ruby-lang.org
 To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/

[ruby-core:123195] [Ruby Feature#21564] Extend permutation, repeated_permutation, combination and repeated_combination arguments

[toy (Ivan Kuchin) via ruby-core]

Issue #21564 has been updated by 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

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

@mame I've added few use cases

----------------------------------------
Feature #21564: Extend permutation, repeated_permutation, combination and repeated_combination arguments
https://bugs.ruby-lang.org/issues/21564#change-114526

* Author: toy (Ivan Kuchin)
* Status: Open
----------------------------------------
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:

```ruby
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:
```ruby
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

        if counts.is_a?(Enumerable)
          counts.each do |count|
            original_#{method_name}(count, &block)
          end
        else
          original_#{method_name}(counts, &block)
        end
      end
    RUBY
  end
end
```



-- 
https://bugs.ruby-lang.org/
______________________________________________
 ruby-core mailing list -- ruby-core@ml.ruby-lang.org
 To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/

[ruby-core:123214] [Ruby Feature#21564] Extend permutation, repeated_permutation, combination and repeated_combination arguments

[duerst via ruby-core]

Issue #21564 has been updated by 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.)

----------------------------------------
Feature #21564: Extend permutation, repeated_permutation, combination and repeated_combination arguments
https://bugs.ruby-lang.org/issues/21564#change-114544

* Author: toy (Ivan Kuchin)
* Status: Open
----------------------------------------
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:

```ruby
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:
```ruby
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
```



-- 
https://bugs.ruby-lang.org/
______________________________________________
 ruby-core mailing list -- ruby-core@ml.ruby-lang.org
 To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/

[ruby-core:123226] [Ruby Feature#21564] Extend permutation, repeated_permutation, combination and repeated_combination arguments

[toy (Ivan Kuchin) via ruby-core]

Issue #21564 has been updated by toy (Ivan Kuchin).


@duerst 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:
```ruby
alphabet = [*'a'..'z']

alphabet.repeated_permutation(*3..6).find{ … }
```
Doing same with `flat_map` will take long time to materialise all permutations:
```ruby
(3..6).flat_map{ |i| alphabet.repeated_permutation(i).to_a }.find{ … }
```
It is possible to resolve this using `lazy`:
```ruby
(3..6).lazy.flat_map{ |i| alphabet.repeated_permutation(i).lazy }.find{ … }
```
Or using `chain`:
```ruby
Enumerator::Chain.new(*(3..6).map{ |i| alphabet.repeated_permutation(i) }).find{ … }
```
But I think both are harder to write and read

----------------------------------------
Feature #21564: Extend permutation, repeated_permutation, combination and repeated_combination arguments
https://bugs.ruby-lang.org/issues/21564#change-114556

* Author: toy (Ivan Kuchin)
* Status: Open
----------------------------------------
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:

```ruby
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:
```ruby
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
```



-- 
https://bugs.ruby-lang.org/
______________________________________________
 ruby-core mailing list -- ruby-core@ml.ruby-lang.org
 To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/