Tag: permute

After racking my brains for almost 4 days (yeah I am a slow learner) I finally created a simple Javascript string combination generator

See the demo http://naiksblog.info/stringcombinations.html

I tried modeling the logic to how databases combine sets in a cross join. All rows from left side are combined with all rows from right side.

The script is as below

	function combine(a, b) {
		var r= new Array();
		for(var i= 0, k= 0; i < a.length; i++) {
			for(var j= 0; j < b.length; j++) {
				if(-1==a[i].indexOf(b[j])) r[k++]= a[i]+ b[j];
			}
		}

		return(r);
	}

You can call this as below

	function permute() {
		var a= "abcd";
		var p= new Array();

		for(var i= 0; i< a.length; i++) p[i]= a.charAt(i);
		var r= p;	// Input string as-is is first permutation
		for(var i= 1; i< a.length; i++) r= combine(r, p);	// Get the permutations
		// r.length - Get the combinations
		// r contains all combinations as an array
	}

Some points worth noting

• If any character is repeated, the combination does not happen successfully since the logic tries to remove same character matching elsewhere
• The number of combinations increase by factorial of the number of characters, hence it will be a good idea to perform this on server side ideally otherwise javascript will hang for large strings
• Logic could be optimized to generate combination in a different better way than using crossjoin strategy