Generating combinations of k from n entries

Hi,

I need to generate combinations from a list of entries. For example, I may have n entries and I want to generate combinations of k (<=n) of those entries.

Example 1:

Entries: a,b   //n=2
k = 1
Output: a,b

Example 2:

Entries: a,b //n=2
k = 2
Output: aa,ab,ba,bb

Example 3:

Entries: a,b,c //n=3
k = 1
Output: a,b,c

Example 4:

Entries: a,b,c //n=3
k = 2
Output: aa,ab,ac,ba,bb,bc,ca,cb,cc

Example 5:

Entries: a,b,c //n=3
k = 3
Output: aaa,aab,aac,aba,abb,abc,aca,acb,acc,baa,bab,bac,bba,bbb,bbc,bca,bcb,bcc,caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc

Entries and k are variable.

I found a number of combination related samples on the web but mostly they are overly complicated and do not cover this specific case I am trying to do.

Any ideas how to do what I am trying to do? If you have a sample code to share, it would be great, otherwise, a possible algorithm or a link to another source that does this are also highly appreciated.

1 Like

If it will always be a comma-delimited list, you could split(‘,’) the list into an array and do a loop within a loop.

This is for homework, isn’t it? :frowning:

I just realized that I didn’t think this through… hang on…

HTH,

:slight_smile:

1 Like

Hi, thanks for your input. A simple loop within a loop will not work, I tried that.

No, it is not for homework, I am not a student. I need that for a part of my application. I thought it would be simpler when I first started but then realized it is not. Having difficulty establishing the algorithm.

Looks like the number of possible combinations is n^k
That could get large quickly and cause some extreme resource use if you’re not careful.

Potentially just how big are you likely to be dealing with?

1 Like

I am considering using a limit for n (6 or so) to prevent so large combinations.

That’s not all that bad I guess.
Assuming k will always be <= n and never > n …

that’s only up to 46,656 possible combinations maximum.
(of course, if by “or so” you mean 7, that jumps to 823,543 !)

Maybe it would be best to have a lot of database tables using the possible values as the index so they’ll all be unique?

2 Likes

No database or such. The application works on client side only.

I have a feeling this is likely to throw “unresponsive script” dialog boxes.
Not so much a problem if you are the only one that’s going to be running it and you don’t mind waiting or the occasional crash.
More so if unsuspecting users enter into a bog out.

Just as 6 → 7 increases dramatically, going from 6 → 5 decreases significantly (3,125)
and 4 even more so (256)

I don’t think 4 should pose any problems, and 5 might even be OK, but IMHO you should think about it and test first

2 Likes

you should seriously think about relaying the work to a WebWorker so the main page does not get blocked while computing.

2 Likes

Thanks for the performance considerations. I will do something to prevent crashes/lockouts once I have a working script.

You just need to use a rudimentary recursion

var strLetters = "a,b,c,d,e,f,g,h";
var arrLetters = strLetters.split(",");
var comboDepth = 3
echo LoopIt(3, "", arrLetters);

function LoopIt(depth, baseString, arrLetters) {
	var returnValue = "";
	for (var i = 0; i < arrLetters.length; i++) {
		returnValue += (depth == 1 ? "," + baseString + arrLetters[i] : LoopIt(depth - 1, baseString + arrLetters[i], arrLetters));
	}
        return returnValue;
}
3 Likes

Okay, so grown-up homework then as an application for a job. We’re still here to help people learn.

Rosetta Code is the best place to find out how to achieve such common tasks, in a variety of languages.
For example: the JavaScript section of their Permutations page has:

<html><head><title>Permutations</title></head>
<body><pre id="result"></pre>
<script type="text/javascript">
var d = document.getElementById('result');
 
function perm(list, ret)
{
	if (list.length == 0) {
		var row = document.createTextNode(ret.join(' ') + '\n');
		d.appendChild(row);
		return;
	}
	for (var i = 0; i < list.length; i++) {
		var x = list.splice(i, 1);
		ret.push(x);
		perm(list, ret);
		ret.pop();
		list.splice(i, 0, x);
	}
}
 
perm([1, 2, 'A', 4], []);
</script></body></html>

Which results in:

1 2 A 4
1 2 4 A
1 A 2 4
1 A 4 2
1 4 2 A
1 4 A 2
2 1 A 4
2 1 4 A
2 A 1 4
2 A 4 1
2 4 1 A
2 4 A 1
A 1 2 4
A 1 4 2
A 2 1 4
A 2 4 1
A 4 1 2
A 4 2 1
4 1 2 A
4 1 A 2
4 2 1 A
4 2 A 1
4 A 1 2
4 A 2 1
2 Likes

Also not for a job :slight_smile: Just for myself learning to do something in JS and then implement it in my own experimental application.

Thank you for the sample and the link. I didn’t hear of that site before, it has some nice examples. That sample code seems to be doing non-repeating combinations though, I need all combinations. In your example, it would have outputted 4^4 = 256 lines (1111,1112,111A,1114,…).

Thank you very much for the sample! I am not much knowledgeable about recursive functions but the one you gave works exactly as I needed. I also like its simplicity, as simple code is easy to follow and understand.

1 Like

Ahh - if you look at the top of the permutations page you’ll see that they link to things like combinations, and permutations with repetitions

There is no JavaScript version on that permutations with repetitions page yet, but plenty of good inspiration is available from the other languages shown there.

1 Like

This topic was automatically closed 91 days after the last reply. New replies are no longer allowed.

There are now several varieties of JavaScript examples of permutations with repetitions, at http://rosettacode.org/wiki/Permutations_with_repetitions#JavaScript

1 Like