Combination Generator

Related Articles

• Permutation Generator

Introduction

Roughly speaking, a combination is a selection of letters inside a String. For example, consider the String "abcde". We want to select 3 letters out of it. How many combinations do we have ?
Answer : 10. The full list is :

["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

Divide and Conquer

We can keep breaking down the problem into smaller sub-problems, until the sub-problems have obvious solution. This technique of problem solving is known as "divide and conquer".



Problem : Find all 3-letters combinations from "abcde"
Sub-problems :

1. Find the combination that contains the letter "a"
2. Find the combination that doesn't contains the letter "a"

The second sub-problem is identical to :

Find all 3-letters combinations from "bcde", that would produce the list :

["bcd","bce","bde","cde"]

And the first sub-problem is identical to :
Find all 2-letters combinations from "bcde", then add an "a" in front of each combination

Let's write it in details :

all 2-letters combinations of "bcde" = ["bc","bd","be","cd","ce","de"]
add an "a" in front of each of them = ["abc","abd","abe","acd","ace","ade"]

Combining two sub-problems will give the full solutions :

["abc","abd","abe","acd","ace","ade"] + ["bcd","bce","bde","cde"]
=["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

Implementation

A recursive implementation follows directly from the above algorithm.

Runnable Demonstration

Trace

You may skip this section if you feel you understand the algorithm well enough.

We will trace a smaller problem, find all 3-letters combination from "abcd"

Level 1 expand, divide into 2 sub-problems
combination("","abcd",3)
  1. combination("a","bcd",2)
  2. combination("" ,"bcd",3)

Level 2 expand
combination("","abcd",3)
  1. combination("a","bcd",2)
    1.1 combination("ab","cd",1)
    1.2 combination("a" ,"cd",2)
  2. combination("","bcd",3)
    2.1 combination("b","cd",2)
    2.2 combination("" ,"cd",3) // dead end, cannot pick 3 letters from tail "cd"

Level 3 expand
combination("","abcd",3)
  1. combination("a","bcd",2)
    1.1 combination("ab","cd",1)
      1.1.1 combination("abc","d",0)   // k=0, print "abc"
      1.1.2 combination("ab" ,"d",1)
    1.2 combination("a","cd",2)
      1.2.1 combination("ac","d",1)
      1.2.2 combination("a" ,"d",2)  // dead end, cannot pick 2 letters from tail "d"
  2. combination("","bcd",3)
    2.1 combination("b","cd",2)
      2.1.1 combination("bc","d",1)
      2.1.2 combination("b" ,"d",2)  // dead end, cannot pick 2 letters from tail "d"
    2.2 combination("" ,"cd",3) // dead end, cannot pick 3 letters from tail "cd"

Level 4 expand
combination("","abcd",3)
  1. combination("a","bcd",2)
    1.1 combination("ab","cd",1)
      1.1.1 combination("abc","d",0)   // k=0, print "abc"
      1.1.2 combination("ab" ,"d",1)
        1.1.2.1 combination("abd","",0) // k=0, print "abd"
        1.1.2.2 combination("ab" ,"",1) // dead end, cannot pick 1 letter from tail ""
    1.2 combination("a","cd",2)
      1.2.1 combination("ac","d",1)
        1.2.1.1 combination("acd","",0) // k=0, print "acd"
        1.2.1.2 combination("ac" ,"",1) // dead end, cannot pick 1 letter from tail ""
      1.2.2 combination("a" ,"d",2)  // dead end, cannot pick 2 letters from tail "d"
  2. combination("","bcd",3)
    2.1 combination("b","cd",2)
      2.1.1 combination("bc","d",1)
        2.1.1.1 combination("bcd","",0) // k=0, print "bcd"
        2.1.1.2 combination("bc" ,"",1) // dead end, cannot pick 1 letter from tail ""
      2.1.2 combination("b" ,"d",2)  // dead end, cannot pick 2 letters from tail "d"
    2.2 combination("" ,"cd",3) // dead end, cannot pick 3 letters from tail "cd"