Ruby

Feature #21564

Updated by toy (Ivan Kuchin) 2 months ago

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) 
           original_#{method_name}(count, end 
         else 
           original_#{method_name}(counts, &block) 
         end 
       end 
     RUBY 
   end 
 end 
 ```

Back