require 'facets/core/integer/factorial'

module Enumerable

    # Permutation proves the possible orders of an enumerable.
    # Each is index by a oermutation numnber. The maximum number of
    # arrangements is the factorial of the size of the array.

    def permutation(number)
        arr = to_a
        out = arr[0..0]
        nextfactor = factor = 1
        arr.each_with_index {|x,i|
            case i
            when 0: next
            else
                nextfactor = factor * (i+1)
                out.insert(number % nextfactor / factor, x)
                factor = nextfactor
            end
        }
        out
    end
    alias :permute :permutation

    #

    def permutation_number(original_array=self.to_a.sort)
        arr = to_a
        m = 1
        v = 0
        last_indicies = Hash.new(0)
        original_array.each_with_index {|x,i|
            next if i==0
            m *= i
            done = original_array[0..i]
            v += m * arr.select {|y| done.include?(y)}.rindex(x)
        }
        v
    end

    # Applys a block to each possible permutation of an array/enumerable.
    #
    #   %w[a b c].each_permutation { |x| puts(x.join('')) }
    #
    # produces
    #
    #   abc
    #   acb
    #   bac
    #   bca
    #   cab
    #   cba
    #
    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

    #-- 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
    #++

end


#  _____       _
# |_   _|__ __| |_
#   | |/ -_|_-<  _|
#   |_|\___/__/\__|
#
=begin test

  require 'test/unit'
  require 'set'

  class TCEnumerable < Test::Unit::TestCase

    def test_001
      o = Set.new
      %w[a b c].each_permutation { |x| o << x.join('') }
      r = Set.new(['abc','acb','bac','bca','cab','cba'])
      assert_equal( r, o )
    end
  end

=end


#   ___ _
#  / __| |_  __ _ _ _  __ _ ___ ___
# | (__| ' \/ _` | ' \/ _` / -_|_-<
#  \___|_||_\__,_|_||_\__, \___/__/
#                     |___/
#
=begin changelog

  2005-10-05 (trans):
  - Changed 'Class Array' to 'module Enumerable'
  - Replaced with Daniel Sheppard's code.

=end


#   ___            _ _ _
#  / __|_ _ ___ __| (_) |_ ___
# | (__| '_/ -_) _` | |  _(_-<
#  \___|_| \___\__,_|_|\__/__/
#
=begin credits

  - Daniel Sheppard
  - Paul Battley (old version of each_permutation)

=end