permutation.rb in facets-2.2.0

- old
+ new

@@ -1,45 +1,37 @@
-# TITLE:
-#   Permutations
-#
-# DESCRIPTION:
-#   Enumerble permutation extensions.
-#
-# AUTHORS:
-#   - Florian Gross
-
 require 'facets/integer/factorial'
 
-#
 module Enumerable
 
   # Permutation proves the possible orders of an enumerable.
   # Each is index by a permutation number. The maximum number of
   # arrangements is the factorial of the size of the array.
   #
-  # CREDIT Florian Gross
+  #   CREDIT: Florian Gross
 
   def permutation(number)
       arr = to_a
       out = arr[0..0]
       nextfactor = factor = 1
       arr.each_with_index {|x,i|
           case i
-          when 0: next
+          when 0
+            next
           else
               nextfactor = factor * (i+1)
               out.insert(number % nextfactor / factor, x)
               factor = nextfactor
           end
       }
       out
   end
-  alias :permute :permutation
 
+  alias_method :permute, :permutation
+
   # Calculate permutation number.
   #
-  # CREDIT Florian Gross
+  #   CREDIT: Florian Gross
 
   def permutation_number(original_array=self.to_a.sort)
       arr = to_a
       m = 1
       v = 0
@@ -64,43 +56,46 @@
   #   bac
   #   bca
   #   cab
   #   cba
   #
-  # CREDIT Florian Gross
+  #   CREDIT: Daniel Sheppard
 
   def each_permutation()
-      arr = to_a
-      size = arr.size
-      perm_count = (1...size).inject(0) { |s,x| s + x * x.factorial }
-      weights = Array.new(size-1) {|i| (i+1).factorial }
-      s = weights.size
-      x,i,v,pos = nil
-      0.upto(perm_count) do |v|
-          out = arr[0..0]
-          arr.each_with_index {|x,i|
-              case i
-                  when 0: next
-                  when s: out.insert(v / weights[i-1], x)
-                  else out.insert(v % weights[i] / weights[i-1], x)
-              end
-          }
+      pos = Array.new(size) {|i| i}
+      s = (0...size).to_a.reverse
+      out = nil
+      while true
+          out = []
+          pos.each_with_index {|p,i| out.insert(p, self[i]) }
           yield out
+          break if s.each do |i|
+              break if pos[i] > 0 && pos[i] -= 1
+              pos[i] = i
+          end
       end
   end
 
-  #-- OLD VERSION
-  #def each_permutation( prefixed=[] )
-  #  s = self.to_a
-  #  if (length < 2)
-  #    # there are no elements left to permute
-  #    yield(prefixed + self)
-  #  else
-  #    # recursively permute the remaining elements
-  #    s.each_with_index do |e, i|
-  #      (s[0,i]+s[(i+1)..-1]).each_permutation(prefixed+[e]) { |a| yield a }
-  #    end
-  #  end
-  #end
-  #++
+  # OLD VERSION
+  #   #   CREDIT: Florian Gross
+  #
+  #   def each_permutation()
+  #       arr = to_a
+  #       size = arr.size
+  #       perm_count = (1...size).inject(0) { |s,x| s + x * x.factorial }
+  #       weights = Array.new(size-1) {|i| (i+1).factorial }
+  #       s = weights.size
+  #       x,i,v,pos = nil
+  #       0.upto(perm_count) do |v|
+  #           out = arr[0..0]
+  #           arr.each_with_index {|x,i|
+  #               case i
+  #                   when 0: next
+  #                   when s: out.insert(v / weights[i-1], x)
+  #                   else out.insert(v % weights[i] / weights[i-1], x)
+  #               end
+  #           }
+  #           yield out
+  #       end
+  #   end
 
 end