# Thread: recursive combinations of string

1. Registered User
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. Registered User+
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. Registered User
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. Registered User+
Join Date
Aug 2007
Posts
3,767
var string = "ajrdvbfomfkswkmbncrfu".replace(/(b|f|k)/ig,"\$1\"");

5. Registered User
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. Registered User+
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. 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);
</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".showPermutations());//surprisingly not laggy in Firefox or IE although laggy in chrome.
</script>```

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

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

"

"

## X vBulletin 4.2.2 Debug Information

• Page Generation 0.10670 seconds
• Memory Usage 2,945KB
• Queries Executed 13 (?)
Template Usage (33):
• (4)bbcode_code
• (1)footer
• (1)forumjump
• (1)forumrules
• (1)gobutton
• (10)memberaction_dropdown
• (1)navbar
• (1)navbar_moderation
• (1)navbar_noticebit
• (1)navbar_tabs
• (2)option
• (10)postbit
• (10)postbit_onlinestatus
• (10)postbit_wrapper
• (1)spacer_close
• (1)spacer_open
• (1)tagbit_wrapper

Phrase Groups Available (6):
• global
• inlinemod
• postbit
• posting
• reputationlevel
Included Files (26):
• ./global.php
• ./includes/class_bootstrap.php
• ./includes/init.php
• ./includes/class_core.php
• ./includes/config.php
• ./includes/functions.php
• ./includes/class_friendly_url.php
• ./includes/class_hook.php
• ./includes/class_bootstrap_framework.php
• ./vb/vb.php
• ./vb/phrase.php
• ./includes/functions_calendar.php
• ./includes/functions_bigthree.php
• ./includes/class_postbit.php
• ./includes/class_bbcode.php
• ./includes/functions_reputation.php
• ./includes/functions_notice.php
• ./packages/vbattach/attach.php
• ./vb/types.php
• ./vb/cache.php
• ./vb/cache/db.php
• ./vb/cache/observer/db.php
• ./vb/cache/observer.php

Hooks Called (71):
• init_startup
• friendlyurl_resolve_class
• init_startup_session_setup_start
• database_pre_fetch_array
• database_post_fetch_array
• init_startup_session_setup_complete
• global_bootstrap_init_start
• global_bootstrap_init_complete
• cache_permissions
• fetch_foruminfo
• global_state_check
• global_bootstrap_complete
• global_start
• style_fetch
• global_setup_complete
• strip_bbcode
• friendlyurl_clean_fragment
• friendlyurl_geturl
• forumjump
• cache_templates
• cache_templates_process
• template_register_var
• template_render_output
• fetch_template_start
• fetch_template_complete
• parse_templates
• notices_check_start
• notices_noticebit
• process_templates_complete
• friendlyurl_redirect_canonical
• bbcode_fetch_tags
• bbcode_create
• postbit_factory
• postbit_display_start
• postbit_imicons
• bbcode_parse_start
• bbcode_parse_complete_precache
• bbcode_parse_complete
• postbit_display_complete
• memberaction_dropdown
• tag_fetchbit
• tag_fetchbit_complete
• forumrules
• navbits
• navbits_complete