www.webdeveloper.com
Results 1 to 10 of 10

Thread: recursive combinations of string

  1. #1
    Join Date
    Aug 2009
    Posts
    38

    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

  2. #2
    Join Date
    Aug 2007
    Posts
    3,767
    And do what with them? The are easy to find with regular expressions, but what do you want to do with them.

  3. #3
    Join Date
    Aug 2009
    Posts
    38
    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

  4. #4
    Join Date
    Aug 2007
    Posts
    3,767
    var string = "ajrdvbfomfkswkmbncrfu".replace(/(b|f|k)/ig,"$1\"");

  5. #5
    Join Date
    Aug 2009
    Posts
    38
    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; 01-23-2010 at 08:50 PM.

  6. #6
    Join Date
    Aug 2007
    Posts
    3,767
    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.

  7. #7
    Join Date
    Jan 2005
    Location
    Los Angeles, CA
    Posts
    4,887
    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.length-this.replace(/[bfk]/gi,"").length);
    }//function
    String.prototype.showPermutations=function(){
    var digits=this.length-this.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>

  8. #8
    Join Date
    Aug 2009
    Posts
    38
    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,

  9. #9
    Join Date
    Jan 2005
    Location
    Los Angeles, CA
    Posts
    4,887
    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.length-this.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.length-digits,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; 01-26-2010 at 12:12 AM.

  10. #10
    Join Date
    Aug 2009
    Posts
    38
    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
  •  
HTML5 Development Center



Recent Articles