
recursive combinations of string
I have a string "ajrdvbfomfkswkmbncrfu" where the 3 letters b,k and f can be in three forms: b,b',b" and k,k',k" and f,f',f".
I want to find ALL the possible string combinations.
Is there a simple way to do that in JavaScript? (probably with several for loops)
Ex: Hera are 5 combinations:
ajrdvb"fomfkswk'mbncrfu
ajrdvb'fomfkswkmbncrfu
ajrdvb'fomfkswk'mbncrf"u
ajrdvb'fomfkswkmbncrf'u
ajrdvb'fomf"kswkmb"ncrfu
Thanks.
Alex

And do what with them? The are easy to find with regular expressions, but what do you want to do with them.
Great wit and madness are near allied, and fine a line their bounds divide.

I just want to write out the list of all those strings as I listed those 5 strings as example.
I will very gratefull if you can give me the answer in regexp, cause i am not so good in regexp.
Thank you

var string = "ajrdvbfomfkswkmbncrfu".replace(/(bfk)/ig,"$1\"");
Great wit and madness are near allied, and fine a line their bounds divide.

your solution will only give one combination. I think the right solution will give some 100 different combinations. The problem is that the letters shouldn't be change all at once (so the option "g" should not be used). Every letter of those 3 letters (b,f,k) should be changed in position 0, 1, 2, ... in every step. Let me give a more clear example:
string = "dfk";
all possible combinations are:
d'fk, df'k, dfk', d"fk, df"k, dfk" (only one letter is changed) (6 combinaions)
d'f'k, d'fk', df'k', d"f"k, d"fk", df"k", (two letters are changed) (6 combinaions)
d'f'k', d"F"K" (all three letters are changed) (2 combinaions)

Nbr of combinaions = 15 combinaions (plus the original form "dfk")
so we got 13 combinaions when those 3 letters occur only once in a string. I guess we would have a lot more if we just the occured twice (i.e "dfkdfk")
But the solution should be the same regardless how many times they occur.
Thanx,
Last edited by massalexx; 01232010 at 07:50 PM.

I was giving you a starting point, since you implied that you didn't understand how to use regular expressions. I never had any intention of writing a fully working function. Try it yourself, if you have questions come back and ask us.
Great wit and madness are near allied, and fine a line their bounds divide.

You are missing the 12 combinations that use both ' and ":
d'f"k, d'fk", d"f'k, d"fk', df'k", df"k' for two letter changes.
d'f'k", d'f"k', d'f"k",d"f'k', d"f"k',d"f'k" for three letter changes.
Thus your 15 combinations comes to 27 combinations (3^3).
Also before you were using b, k and f now you are using d, k and f
The math at work here is equivalent to trinary.
Given 3 digits, there are 3^3 combinations that can be expressed with those digits.
For example you could see the math at work by doing:
Code:
<script type="text/javascript">
var blah=new Array();
for(var i=0;i<3;i++)for(var j=0;j<3;j++)for(var k=0;k<3;k++)
blah.push(i+""+j+""+k);
alert(blah.join(','));
alert(blah.length);
</script>
Here's a possible solution:
Code:
<script type="text/javascript">
String.prototype.numberOfPermutations=function(){
return Math.pow(3,this.lengththis.replace(/[bfk]/gi,"").length);
}//function
String.prototype.showPermutations=function(){
var digits=this.lengththis.replace(/[bfk]/gi,"").length
var l=Math.pow(3,digits);
var p=new Array();
var a=['',"'",'"'];
var ar=this.replace(/([bfk])/gi,"$1?bfk?").split('?bfk?');
for(var i=0;i<l;i++){
var tri=(new Array(digits+1).join('0')+i.toString(3)).substr(digits,digits).split('');
var o="";
for(var j=0;j<tri.length;j++)o+=ar[j]+a[tri[j]0];
p.push(o);
}//for
return p;
}//function
alert("ajrdvbfomfkswkmbncrfu".numberOfPermutations());//3 to the 7th power
alert("bfk".numberOfPermutations());//3 to the 3rd power
alert("bfk".showPermutations());
alert("bfk".showPermutations().length);//3 to the 3rd power
alert("ajrdvbfomfkswkmbncrfu".showPermutations());//surprisingly not laggy in Firefox or IE although laggy in chrome.
</script>

Thank you Ultimater. This seems to be an excellent solution. I wonder why I get the same combination for all the elements. Is there something I should do with array "a" that adds ' and " to the word. (i got an outup of an array consisting of 2187 elements where all the elements are the same word).
Thanks,

Ah my bad, I forgot IE's substr method doesn't support negative numbers for its start index.
Well... one option is to override the method altogether:
Code:
(function(){
var x=String.prototype.substr;
String.prototype.substr=function(start,length){
if(length==null){length=this.length;}
if(start<0)start+=this.length;return x.apply(this,[start,length]);
}
})();
Or the more orthodox approach would be to edit my code and add the string length to my negative start index:
Code:
String.prototype.showPermutations=function(){
var digits=this.lengththis.replace(/[bfk]/gi,"").length
var l=Math.pow(3,digits);
var p=new Array();
var a=['',"'",'"'];
var ar=this.replace(/([bfk])/gi,"$1?bfk?").split('?bfk?');
for(var i=0;i<l;i++){
var s=new Array(digits+1).join('0')+i.toString(3);
var tri=s.substr(s.lengthdigits,digits).split('');
var o="";
for(var j=0;j<tri.length;j++)o+=(ar[j]+a[tri[j]]);
p.push(o);
}//for
return p;
}//function
Last edited by Ultimater; 01252010 at 11:12 PM.

Now it works perfectly. Thanks alot for your fast reply :)
Thread Information
Users Browsing this Thread
There are currently 1 users browsing this thread. (0 members and 1 guests)
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

