DZone Snippets: combinatory code

Calculate all combinations (permutations)

troelskn (Troels) — Mon, 19 Feb 2007 12:51:44 GMT

Calculates all combinations, including incomplete results.



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;

}

Permutations in Ruby

ntk () — Fri, 19 Jan 2007 15:56:26 GMT





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

Simple Permutation //JavaScript Function

jonasraoni (Jonas Raoni Soares Silva) — Thu, 29 Dec 2005 04:18:25 GMT

[UPDATED CODE AND HELP CAN BE FOUND HERE]

example



var a = ["A", "B", "C", "D"], j = permute(a);

document.write(

    "", a.join(" - "), " = ", j.length, "",

    j.join("
")

);

code



//+ 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;

};

Simple Arrange //JavaScript Function

jonasraoni (Jonas Raoni Soares Silva) — Thu, 29 Dec 2005 04:16:01 GMT

[UPDATED CODE AND HELP CAN BE FOUND HERE]

example



var a = ["A", "B", "C", "D"], q = 3, j = simpleArrange(a, q);

document.write(

    "", a.join(" - "), " : ", q, " = ", j.length, "",

    j.join("
")

);

code



//+ 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;

};

Arrange //JavaScript Function

jonasraoni (Jonas Raoni Soares Silva) — Fri, 09 Sep 2005 07:24:33 GMT

It arranges elements in an array, the "n" parameter determines the amount of elements in each combination and the "m" one is a boolean which says if the function should return an array with an "index map" or real values.

[UPDATED CODE AND HELP CAN BE FOUND HERE]



//+ 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;

};

Example



document.write( arrange( ["A", "B", "C" ], 3, 1 ).join( "
" ), "" );

document.write( arrange( ["A", "B", "C" ], 3, 0 ).join( "
" ) );

Permute //JavaScript Function

jonasraoni (Jonas Raoni Soares Silva) — Fri, 09 Sep 2005 07:20:40 GMT

It permutes elements in an array, the "m" parameter is a boolean which determines if the function should return an array with an "index map" or the real value.

[UPDATED CODE AND HELP CAN BE FOUND HERE]

//+ 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;

};

Example



document.write( permute( ["A", "B", "C" ], 1 ).join( "
" ), "" );

document.write( permute( ["A", "B", "C" ], 0 ).join( "
" ) );