Set Indexing Experiments

gistfile1.js

// experiments 
// Author: Nils Gehlenborg (@ngehlenborg)

var nextBitPermutation = function( current ) {
	// from: http://www-graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
	var v = current;
	var t = (v | (v - 1)) + 1;
	var w = t | ((((t & -t) / (v & -v)) >> 1) - 1);
	return ( w>>>0 );
};

var factorial = function( n )
{
    var factorial =1;
    for (var i = 2; i <= n; i++)
        factorial = factorial * i;
    return factorial;
};

var choose = function( n, k )
{
	if (n < k) {
		return 0;
	}
	
	if (n === k) {
		return 1;
	}
	
    var n_factorial = 1;
    var nk_factorial;
    var k_factorial;
    
    for (var i = 1; i <= n; i++) {    	
        n_factorial = n_factorial * i;        

        if ( i === n - k ) {
        	nk_factorial = n_factorial;
        }

        if ( i === k ) {
        	k_factorial = n_factorial;
        }    
    }
    
    return n_factorial/( nk_factorial * k_factorial );
};

function pad(n, p, c) {
    var pad_char = typeof c !== 'undefined' ? c : '0';
    var pad = new Array(1 + p).join(pad_char);
    return (pad + n).slice(-pad.length);
}

// sets >= n
var nintersections = function( n, sets ) {
	console.time('timer: ' + n + " of " + sets );

	var current = Math.pow( 2, n ) - 1;
	
	var results = new Array( choose( sets, n) );

	for ( var i = 0; i < results.length; ++i ) {
		//console.log( i + ": " + current + " = " + pad( current.toString( 2 ), sets ) );
		current = nextBitPermutation( current );
		results[i] = current;
	}
	
	console.timeEnd('timer: ' + n + " of " + sets );
	
	return results;
};

var intersections = function( sets ) {
	console.time('timer: ' + sets );
	
	var results = new Array();

	for ( var i = 1; i < sets; ++i ) {
		results = results.concat( nintersections( i, sets ) );
	}

	console.timeEnd('timer: ' + sets );
	
	return ( results );
};