## Knuth: Generating All Combinations

November 17, 2007I ran into a tricky little problem today: efficiently generating all combinations of k elements from a set of size N. I came up with some ideas but they weren’t efficient enough. I turned to a Knuth Volume 4 preprint on his website, and found all sorts of crazy algorithms for it. Here is a C# implementation I just coded up and tested that people might find useful. It allows you to make a Combination object, and use foreach on it to get all the members.

Note that I had a chance to use the C# 2.0 yield statement; it let me do a fairly direct translation from the pseudocode, although I made a few tiny changes to simplify things. See the comments for a few ways to improve efficiency a tiny bit but it doesn’t affect time complexity. If I understood Knuth, this algorithm runs in O(N choose t) – it’s linear in the number of elements in the output.

Combination class code: Combination.cs

Test class: CombinationsTest.cs

See also: Combinadic on Wikipedia

Sample output:

`***** CombinationsTest.CombinationTest.Enumerate2_5`

0 1

0 2

1 2

0 3

1 3

2 3

0 4

1 4

2 4

3 4

`*****CombinationsTest.CombinationTest.Enumerate3_5`

0 1 2

0 1 3

0 2 3

1 2 3

0 1 4

0 2 4

1 2 4

0 3 4

1 3 4

2 3 4

Hi

OK heres my assignment question- Write a program that, given n and alphabet Z as inputs, outputs all strings of length n over the alphabet Z.

now alphabet here means a string array where for example Z = {a, c} can be an alphabet of 2 symbols and if I want to out all the strings of length 3, this is what I should get (9 strings in total) –

aaa

aac

aca

caa

acc

cac

cca

ccc

Now i dont have any code as I am still struggling with concepts… First idea I had in mind was like to do a matrix of width n and length = total number of strings…. but, then how do I fill up the matrix??

I have no idea how to approach this problem – there is another idea i came up with which was like initialising the sequence of length n to the first symbol of the alphabet ..But again how would I come around to changing the sequence – I cant figure it out.. any ideas??

by mark slider October 21, 2008 at 11:51 amWhy are all these algorithms generating K elements of N items? I need one that is:

All Combinations of

N elements of N items

(n-1) elements of N items

(n-2) elements of N items

…

1 elemetns of n items.

I mean ALL possible combinations.

by Jaeden Ruiner September 11, 2009 at 3:22 pmIf I understand your question correctly, you can just wrap the algorithm in one loop:

for k = 1 to N

by Eric September 11, 2009 at 4:22 pmrun algorithm with K = k

next K

Hi, any chance of updating links to .cs files?

by roken March 12, 2013 at 6:41 pmYeah, I didn’t know those links died. I hope I can find the files… will let you know. Thx!

by Eric N. March 12, 2013 at 6:47 pmTry these for now:

http://ericpnichols.com/code/Combination.cs

http://ericpnichols.com/code/CombinationTest.cs

Thanks for pointing out the broken links.

by Eric N. March 12, 2013 at 6:56 pmFiles are not accesable.. please help!

by Waqas March 21, 2013 at 7:08 amsee my comment just above; *these* links are working, right?

by Eric N. March 21, 2013 at 3:52 pm