h1

Knuth: Generating All Combinations

November 17, 2007

I 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

About these ads

8 comments

  1. 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??


  2. Why 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.


  3. If I understand your question correctly, you can just wrap the algorithm in one loop:

    for k = 1 to N
    run algorithm with K = k
    next K


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


    • Yeah, I didn’t know those links died. I hope I can find the files… will let you know. Thx!


  5. Try these for now:

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

    Thanks for pointing out the broken links.


  6. Files are not accesable.. please help!


  7. see my comment just above; *these* links are working, right?



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: