combine([1,2]) == [[1], [2], [1,2]];

var combine = function(a) {
  var fn = function(n, src, got, all) {
    if (n == 0) {
      if (got.length > 0) {
        all[all.length] = got;
      }
      return;
    }
    for (var j = 0; j < src.length; j++) {
      fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all);
    }
    return;
  }
  var all = [];
  for (var i=0; i < a.length; i++) {
    fn(i, a, [], all);
  }
  all.push(a);
  return all;
}

# From: http://www.rubyonrailsblog.com/articles/2006/08/31/permutations-in-ruby-can-be-fun (in the comments)
# Author: Brian Mitchell

class Array
  # The accumulation is a bit messy but it works ;-)
  def sequence(i = 0, *a)
    return [a] if i == size
    self[i].map {|x|
      sequence(i+1, *(a + [x]))
    }.inject([]) {|m, x| m + x}     # this has to be used instead of flatten so I can sequence something
                                    # like [[[4]]] -> [[[4]]] rather than -> [[4]]; ruby 1.9 has an option for flatten
  end
end


p [(0..3), [4,6]].sequence             #=> [[0, 4], [0, 6], [1, 4], [1, 6], [2, 4], [2, 6], [3, 4], [3, 6]]      
p [(0..3).collect, [4, 6]].sequence



# http://wiki.rubygarden.org/Ruby/page/show/ArrayPermute
# Permute an array, and call a block for each permutation
# Author: Paul Battley

    class Array
        def permute(prefixed=[])
            if (length < 2)
                # there are no elements left to permute
                yield(prefixed + self)
            else
                # recursively permute the remaining elements
                each_with_index do |e, i|
                    (self[0,i]+self[(i+1)..-1]).permute(prefixed+[e]) { |a| yield a }
                end
            end
        end
    end


%w[a b c].permute { |x| puts(x.join('')) } 

[0, 1, 2, 3 ].permute { |x| puts(x.join('-')) } 



# http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/32844
# Author: Steven Grady

class Array
  def permutations
    return [self] if size < 2
    perm = []
    each { |e| (self - [e]).permutations.each { |p| perm << ([e] + p) } }
    perm
  end
end

p (1..4).to_a.permutations



# http://blade.nagaokaut.ac.jp/~sinara/ruby/math/combinatorics/array-perm.rb
# Author: Shin-ichiro Hara
# For many more permutation snippets see: 
# http://blade.nagaokaut.ac.jp/~sinara/ruby/math/combinatorics/

class Array
  def perm(n = size)
    if size < n or n < 0
    elsif n == 0
      yield([])
    else
      self[1..-1].perm(n - 1) do |x|
	(0...n).each do |i|
	  yield(x[0...i] + [first] + x[i..-1])
	end
      end
      self[1..-1].perm(n) do |x|
	yield(x)
      end
    end
  end
end

if $0 == __FILE__
  ["a", "b", "c", "d"].perm(3) do |x|  
    p x
  end
end



# Based on:
# http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/139290
# Author: Endy Tjahjono

class String
   def perm
       return [self] if self.length < 2
       ret = []
    
       0.upto(self.length - 1) do |n|
          #rest = self.split('')                
          rest = self.split(//u)            # for UTF-8 encoded strings
          picked = rest.delete_at(n)
          rest.join.perm.each { |x| ret << picked + x }
       end

       ret
   end
end

p "abc".perm      #=>  ["abc", "acb", "bac", "bca", "cab", "cba"]



require 'permutation'

# http://permutation.rubyforge.org 
# http://permutation.rubyforge.org/doc/classes/Permutation.html
# sudo gem install permutation --remote
# For more examples see permutation-0.1.4/examples/tsp.rb and permutation_0.1.4/lib/permutation.rb:
# curl http://files.rubyforge.vm.bytemark.co.uk/permutation/permutation-0.1.4.tgz | tar xfz -

perm = Permutation.new(3)   
p perm.map { |p| p.value }        #=>  [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

var a = ["A", "B", "C", "D"], j = permute(a);
document.write(
    "<h2>", a.join(" - "), " = ", j.length, "</h2>",
    j.join("<br />")
);

//+ Jonas Raoni Soares Silva
//@ http://jsfromhell.com/array/permute [v1.0]

permute = function(v, m){ //v1.0
    for(var p = -1, j, k, f, r, l = v.length, q = 1, i = l + 1; --i; q *= i);
    for(x = [new Array(l), new Array(l), new Array(l), new Array(l)], j = q, k = l + 1, i = -1;
        ++i < l; x[2][i] = i, x[1][i] = x[0][i] = j /= --k);
    for(r = new Array(q); ++p < q;)
        for(r[p] = new Array(l), i = -1; ++i < l; !--x[1][i] && (x[1][i] = x[0][i],
            x[2][i] = (x[2][i] + 1) % l), r[p][i] = m ? x[3][i] : v[x[3][i]])
            for(x[3][i] = x[2][i], f = 0; !f; f = !f)
                for(j = i; j; x[3][--j] == x[2][i] && (x[3][i] = x[2][i] = (x[2][i] + 1) % l, f = 1));
    return r;
};

var a = ["A", "B", "C", "D"], q = 3, j = simpleArrange(a, q);
document.write(
    "<h2>", a.join(" - "), " : ", q, " = ", j.length, "</h2>",
    j.join("<br />")
);

//+ Jonas Raoni Soares Silva
//@ http://jsfromhell.com/array/simple-arrange [v1.0]

simpleArrange = function(a, n, m){ //v1.0
    var o = a;
    if(n >= o.length) return [];
    for(var j, l, k, p, f, r, q = k = 1, i = (l = o.length) + 1, j = l - n; --i; i <= j ? q *= i : k *= i);
    for(x = [new Array(n), new Array(n), new Array(n), new Array(n)], j = q = k * q / q, k = l + 1, i = -1;
        ++i < n; x[2][i] = i, x[1][i] = x[0][i] = j /= --k);
    for(r = new Array(q), p = -1; ++p < q;)
        for(r[p] = new Array(n), i = -1; ++i < n; !--x[1][i] && (x[1][i] = x[0][i],
            x[2][i] = (x[2][i] + 1) % l), r[p][i] = m ? x[3][i] : o[x[3][i]])
            for(x[3][i] = x[2][i], f = 0; !f; f = !f)
                for(j = i; j;)
                    if(x[3][--j] == x[2][i]){
                        x[3][i] = x[2][i] = (x[2][i] + ++f) % l;
                        break;
                    }
    return r;
};

//+ Jonas Raoni Soares Silva
//@ http://jsfromhell.com/array/arrange [v1.0]

arrange = function( v, n, m ){
 	for( var i, j, k, sep = sep || "", l = v.length, r = new Array( i = Math.pow( l, n ) ), c = ( new Array( n + 1 ) ).join( 0 ).split( "" ); i; )
		for( r[--i] = new Array( j = n ), k = 1; j--; r[i][j] = m ? c[j] : v[c[j]], k && ( ++c[j] != l && --k, c[j] %= l ) );
	return r;
};

document.write( arrange( ["A", "B", "C" ], 3, 1 ).join( "<br />" ), "<hr />" );
document.write( arrange( ["A", "B", "C" ], 3, 0 ).join( "<br />" ) );

//+ Jonas Raoni Soares Silva
//@ http://jsfromhell.com/array/permute [v1.0]

permute = function( v, m ){
	for( var j, l = v.length, i = ( 1 << l ) - 1, r = new Array( i ); i; )
		for( r[--i] = [], j = l; j; i + 1 & 1 << --j && ( r[i].push( m ? j : v[j] ) ) );
	return r;
};

document.write( permute( ["A", "B", "C" ], 1 ).join( "<br />" ), "<hr />" );
document.write( permute( ["A", "B", "C" ], 0 ).join( "<br />" ) );