3.1.   Two Approaches To Combinatorial Generation

In this post we will look at two approaches to solving combinatorial generation problems. Let's consider both of them here briefly.

Recursive: Combinatorial generation interview questions are likely to have simple recursive solutions, based on simple observations about the recursive structure of the combinatorial objects. At times, the recursive solution can be as simple as literally following the definition of the combinatorial set. Combinatorial objects are often defined recursively. For example, consider the definition of a binary tree. The recursive solutions often suffer from exponential space usage, or exponential time, or both, depending on implementation. However, they are often very simple to implement, requiring minimal code. They are also usually readable and easy to understand. As such, you should make sure you master the basic recursive solutions and provide them as the first solution. This way you will have at least one working solution by the end of the interview (which will, in my experience of interviewing candidates, set you apart from the majority of candidates). Ideally, you should aim to provide a simple recursive solution in 5 to 10 minutes at most, leaving the majority of the rest of the interview time to space and time complexity analysis and to provide the improved iterative solution.

Iterative: In the iterative approach, we move from one object to the next by modifying the object in-place. A common iterative approach is to generate all objects in lexicographic order. This approach has several benefits. First, since the generation is done by modifying the input in-place, space complexity is often constant or at least not exponential. Second, we produce the objects in lexicographic order. Furthermore, by formulating the problem as how to move from one object to the next in lexicographic order, we can come up with a general problem solving strategy that works for many problems. To quote Knuth, "lexicographic order usually suggests the most convenient way to generate combinatorial configurations" (The Art Of Computer Programming, Volume 4, section 7.2.1.3).

We will approach multiple example problems using both the above approaches and analyze their time and space complexity. Hopefully by the end of the article, both approaches will be second nature to you and provide systematic way of approaching any combinatorial generation problem you might encounter.

3.2.   Time And Space Complexity Of Generation Algorithms

In most cases, the output set of a combinatorial generation problem is exponential in size (or infinite at times), and hence as a whole the program must run in exponential time to generate all the objects (or run indefinitely until terminated externally, in cases of generating infinite sets). Because of this, we will often consider time needed to generate each object in the set (on average, or worst case). Similarly, we will look at the maximum space needed by the program at any point during its execution. For programs that need to run indefinitely (i.e., ones that generate infinite sets), we look at how space usage grows as the program keeps on running.

Similar to the two approaches to solving the problems, this more nuanced approach to time and space complexity will also be made more clear by looking at multiple examples.

3.3.   What "Generate" Means

The simplest way to generate the objects is to collect all the output in a list. However, we can not improve space complexity to be better than the size of the output set (which is often exponential), if we want to keep all the generated objects in memory at once. Therefore, for combinatorial generation problems , "generate" can also mean any of the following:

• Print a representation of each object to standard output.
• Yield each object using a generator.
• Visit each object by calling a provided visit function with the object passed as the argument.

In this article, when we try to avoid unnecessary (and often exponential) memory usage, we will use a simple generator pattern and yield each resulting object instead of placing them in an in-memory collection. You can read about Python's generators in PEP 255 or in my post on iterators and generators. As the name of the pattern suggests, Python generators are very well-suited for combinatorial generation.

3.4.   Output Order

A good clarifying question to ask for combinatorial generation problems is whether there is an expectation on the order of the output objects. You might learn that the output order does not matter, or the interviewer might ask the output to be in lexicographic (i.e., dictionary) order. Rarely, you might also come across a problem that asks for an order that minimizes the difference between two subsequent objects. This order is often referred to as Gray order, named after Bell Labs researcher Frank Gray. I hope to write a follow-up to this post at some point to go over some examples of Gray order generation. For now, in our basic recursive solutions we tend to not worry about the order of the output, and just ensure every object is generated exactly once. In the iterative approach, we will generate objects in lexicographic order.

4.1.   Problem Definition

Let's start by looking at a simple problem: given an alphabet A which is guaranteed to be a non-empty list of distinct single character strings, and a non-negative integer n, generate all strings of length n. For example, given A = ['0', '1', '2'] and n = 2 we expect the output to be:

00
01
02
10
11
12
20
21
22

To make sure the question is clear, let's look at another example. Given A = ['a', 'b'] and n = 3 we expect the output to be:

aaa
aab
aba
abb
baa
bab
bba
bbb

4.2.   Basic Recursive Solution

The basic recursive structure of the set we are generating can be easily seen as follows: given all strings of length $n - 1$ , we can form all strings of length $n$ by appending all possible characters in the alphabet set to the strings. This leads to the following very basic recursive solution:

def strings(A, n):
   if n == 0:
      return ['']
   return [s + c for s in strings(A, n - 1) for c in A]

Example usage:

In [1]: strings(['0', '1', '2'], 2)
Out[1]: ['00', '01', '02', '10', '11', '12', '20', '21', '22']

4.3.   Analysis Of Basic Recursive Solution

Space usage of this solution is easy to analyze. Let's let $k = len(A)$ , that is $k$ is the size of the alphabet set. We hold the entire output for $n$ in memory, in addition to the output for $n - 1$ . Note that subsequent outputs for strings of length smaller than $n - 1$ can be deallocated as they are no longer needed and we do not keep a reference to them. The total space used by the program can be summarized as $O(k^n + k^{n-1}) = O(k^n)$ . That means we use exponential memory assuming $k > 1$ .

Now let's look at time complexity. The key operation here is appending to a string. It is easy to modify the code to use preallocated lists/strings instead of appending to a string which in Python requires linear work. Let's assume for now that appending to a strong is an $O(1)$ operation. How many string concatenations do we do total? Let's define the total number of concatenations for generating strings of length $n$ as as $T(n)$ . Then we have

Let's let the base case $T(0) = 1$ for simplicity of the math that follows (as we will see, the exact value of the base does not make a difference in the asymptotic behaviour of the function anyway). The recurrence relation for $T(n)$ is easily solved as

Therefore, the total number of concatenations is exponential. However, as discussed we are more interested in the amount of work done per string so we we care more about

Therefore, we do constant work on average per string generated. A combinatorial generation algorithm that does $O(1)$ work per output object is referred to as a constant amortized time (CAT) algorithm. CAT algorithms are usually considered good solutions (assuming they do not use exponential space, which our solution does!), since they do constant amount of work on average. The only classification better than simply CAT for a combinatorial generation algorithm is for it to be "loopless". Loopless algorithms, as the name suggests, involve no looping per output object, which means they do constant work not just on average but worst case as well. We will not discuss loopless algorithms in this article though as that is a more advanced subject (see resources in Further Reading if you are interested in learning more about loopless algorithms.)

4.4.   Exercises

Exercise 4.4.1 (Easy): What if $k = 1$ ? What is the output of the program? What about space and time complexity?

Exercise 4.4.2 (Medium): Modify the recursive solution to modify preallocated lists of the correct size instead of appending to strings.

Exercise 4.4.3 (Easy): Modify the solution to keep count of how many string concatenations take place. Verify that our closed formula for $T(n)$ is correct.

Exercise 4.4.4 (Easy): Modify the recursive solution to return a generator instead (i.e., use yield instead of return and yield one string at a time instead of returning the whole list).

Exercise 4.4.5 (Medium): Analyze the time and space complexity of the generator solution you came up with in Exercise 4.4.4. How does it compare with the basic recursive solution?

4.5.   Iterative Solution With Lexicographic Order

As discussed, the simple recursive solution provided uses exponential memory and because of that, it is not ideal. To provide a better solution, instead of looking at the recursive structure of the set we are generating, we look at the pattern of how we move from one string to the next when we list all the objects in lexicographic order.

First let's look at part of the output for A = ['0', '1', '2'] and n = 5.

...
21211
21212
21220
21221
21222
22000
22001
22002
22010
22011
22012
22020
22021
...

Let's look at 21222 in this example. The next string is 22000. How do we go from 21222 to 22000? To get to the next item in lexicographic order we need to increment the first letter that we can, going from right to left. Going from right to left, the first letter is 2 which is the last letter in our alphabet (remember our alphabet is A = ['0', '1', '2'], so ``2 is the last letter). We keep moving left until we find the first letter that's not a 2, which is the 1, the second letter in 21222. We change this letter to be the next one in our alphabet, and then we replace everything following it by the smallest possible lexicographic string which is 000, getting 22000, the result. In fact, if we are clever, we can replace everything to the right of the 1 with a 0 (here 0 is special only because it is the first letter in the given alphabet) as we keep looking for the first letter to increment.

The above leads to the following solution:

def strings_2(A, n):
    index_of = {x: i for i, x in enumerate(A)}
    s = [A[0]] * n
    while True:
        yield ''.join(s)
        for i in range(1, n + 1):
            if s[-i] == A[-1]:  # Last letter of alphabet, can not increment
                s[-i] = A[0]
            else:
                s[-i] = A[index_of[s[-i]] + 1]  # Modify to next letter
                break
        else:
            break

Here we use Python's for and else combination to determine if the break never happened. Notice that break does not happen if we never find any letter to increment, which would imply we are at the very last lexicographic string.

4.6.   Analysis Of The Iterative Solution

As before, let $k = len(A)$ , that is $k$ is the size of the alphabet set. Space usage is again quite simple. We use an additional dictionary index_of which holds $k$ elements in it, and the list s which is of length $n$ . This means our space usage is $O(n) + O(k) = O(n)$ since we assume $k$ is going to be small, and constant for most applications. Linear space usage! Not bad at all. In fact, since by definition of the problem we have to have the generated string in memory this is the best possible space complexity we are going to get.

Now let's look at time complexity. It is relatively easy to see that the only operation that is repeated per string is is the resetting of trailing occurrences of the last letter of the alphabet. Everything else happens at most once per string. To understand the amortized run-time of the algorithm, we need to find out how many times this operation takes place. Let's call the operation of resetting a trailing occurrences of the last letter of alphabet a "reset" operation for short.

Let $T(n)$ be the total number of reset operations that takes place while generating all strings of length $n$ . For $(k-1)k^{n-1}$ strings, we do zero resets. Then we have $k^{n-1}$ strings for which we reset the very last letter (in addition to possible other letters). This gives us the following recurrence relation

with $T(0) = 0$ . This is a simple tail recurrence with closed form

Therefore the amortized run-time of the algorithm is

Therefore, the algorithm, somewhat surprisingly, is CAT. This is intuitive though, since we notice the strings requiring more repetitive work are exponentially rarer while the work is only linearly more (in the extreme, only one out of $k^n$ strings requires $n$ resets).

This makes this algorithm quite ideal for producing strings in lexicographic order as it uses linear space and constant amortized time.

4.7.   Exercises

Exercise 4.7.1 (Easy): Modify the source code provided to count the number of resets. Experimentally verify that our closed form formula for $T(n)$ is correct.

Exercise 4.7.2 (Medium): Assume the alphabet is fixed as A = [0, 1] so you are generating all binary strings of a given length. Simplify the code assuming this hard-coded alphabet.

Exercise 4.7.3 (Medium): The main operation in this algorithm is very similar to a particular arithmetic operation. What operation is that? Can you re-implement the algorithm using arithmetic operations? In particular, for the binary alphabet given in Exercise 4.7.2, can you implement this algorithm very efficiently using bitwise operations and basic arithmetic?

Exercise 4.7.4 (Medium): Modify the strings_2 solution to just take as input the alphabet set A and generate all strings over that alphabet. Your program should first generate all strings of length $0$ , then of length $1$ , then $2$ , and so on.

5.1.   Problem Definition

Let's turn our attention to permutations next. Given a set A which is guaranteed to be a non-empty list of distinct single character strings, we want to write a program that generates all permutations of it (i.e., all possible ways to order items in A). For example, given A = ['1', '2', '3'] we expect the output to be the following (in any order):

123
132
213
231
312
321

5.2.   Basic Recursive Solution

Let $n = len(A)$ . Given all permutations of A[1:], we can generate all permutations of A by inserting A[0] in all possible $n$ locations. In the example above, there are two permutations of A[1:] = ['2', '3'] which are 23 and 32. We then take A[0] = '1' and insert it in all three possible positions for each of these permutations to get 123, 213, 231 and so on.

Let's turn this into code:

def perms_1(A):
    if not A:
        return [[]]
    perms = []
    for pi in perms_1(A[1:]):
        for i in range(len(A)):
            perms.append(pi[:i] + [A[0]] + pi[i:])
    return perms

The output of this program for A = ['1', '2', '3'] is shown below:

123
213
231
132
312
321

Notice that the output is not in lexicographic order.

5.3.   Analysis Of Basic Recursive Solution

Space usage, as usual, is easy to analyze. Let's let $n = len(A)$ . We hold the entire output for $n$ in memory, in addition to the output for $n - 1$ . Note that subsequent outputs for permutations of length smaller than $n - 1$ can be deallocated as they are no longer needed and we do not keep a reference to them. The total space used by the program can be summarized as $O(n! + (n-1)!) = O(n!)$ . Our memory usage is worse than exponential!

Now let's look at time complexity. The key operation here is inserting A[0] into each sub-permutation. The way we implemented the algorithm, this operation takes $O(n)$ time, and we do it $n$ times. This gives the following recurrence:

with $T(1) = 1$ . The tail recurrence is easy to unwrap, giving

This sum has a nice and easy closed form given by

Therefore, we have $T(n) = (n + 1)! - 1$ . Of course we are interested in the amortized complexity so we look at

Therefore, the amortized time complexity of our algorithm is $O(n)$ . That means we do, on average, a linear number of operations to generate each permutation. Now, if you are thinking that worse than exponential space usage and linear amortized time do not sound so great, you are right. This is a very naive solution with a pretty bad implementation, but it is a very easy translation of the recursive idea to code. Let's improve it a bit before looking at the lexicographic iterative solution.

5.4.   Exercises

Exercise 5.4.1 (Easy): Write a program that calculates $\sum_{i=1}^n i\cdot i!$ and $(n + 1)! - 1$ for $1 \le n \le 10$ . Verify that equality holds for at least the first ten values of $n$ .

Exercise 5.4.2 (Easy): Prove $\sum_{i=1}^n i\cdot i! = (n + 1)! - 1$ . (Hint: try induction.)

Exercise 5.4.3 (Easy): Modify the basic recursive function given above to be a generator instead (i.e., use yield instead of return and yield one string at a time instead of returning the whole list).

Exercise 5.4.4 (Medium): Analyze the space complexity of the generator solution you came up with in Exercise 5.4.3. How does it compare with the basic recursive solution?

Exercise 5.4.5 (Medium): Modify strings_2 to only take A as a parameter, and generate the infinite set of all strings over A (also called the Kleene closure of A and written as $A^*$ ). Below is the first few lines of the expected output of the program for A = ['0', '1', '2'].

''
'0'
'1'
'2'
'00'
'01'
'02'
'10'
'11'
'12'
'20'
'21'
'22'
'000'
...

5.5.   A Better Recursive Solution

A quick improvement to make to the previous solution is to not do linear work to insert A[0] but to instead do everything in-place. Instead, we can move through each permutation of A[1:] recursively, and then move A[0] to the right one at a time. We need to be careful to backtrack at the end because otherwise the next recursive call will not operate on the right elements of A. Since we do everything in-memory this time, we will use yield and the generator pattern for the recursion.

def perms_2(A, starting_index):
    if starting_index == len(A) - 1:
        yield A
        return
    for _ in perms_2(A, starting_index + 1):
        yield A
        # Keep moving A[starting_index] to the right one at a time
        for i in range(starting_index, len(A) - 1):
            A[i], A[i + 1] = A[i + 1], A[i]
            yield A
        # Now move it all the way back to where it was at the beginning
        for i in range(len(A) - 1, starting_index, -1):
            A[i], A[i - 1] = A[i - 1], A[i]

Here's how this generator can be used:

In [1]: for pi in perms_2(['1', '2', '3'], 0):
   ...:     print(''.join(pi))
   ...:
123
213
231
132
312
321

5.6.   Analysis Of The Better Recursive Solution

Let's look at space complexity first. It's easy to see that each instance of the generator uses only constant amount of space (not counting A itself which is given as input). Then the question is how many instances of the generator are allocated and it is relatively easy to see that one instance, namely perms_2(A, i) is allocated for $0 \le i < n`$ , meaning a total of $n$ total generators are allocated total. This means we use $O(n)$ space. Not bad!

Now we turn to time complexity. This time, for each permutation of A[1:], we do $n - 1$ transpositions (repeatedly moving A[0] to the right by swapping it with the element to its right), followed by moving it all the way back which does another $n-1$ transpositions. This gives the following recurrence

with $T(1) = 1$ . As before, this is a tail recurrence so we can easily unwrap it as a sum:

The amortized time will be

Therefore this improvement was enough to improve the algorithm from linear amortized time to constant amortized time. Simultaneously, by using a generator and doing the transpositions in-place, we improved the space usage of the algorithm from worse than exponential to linear. Overall, this is a pretty solid solution!

5.7.   Exercises

Exercise 5.7.1 (Difficult): You might have noticed the redundancy of moving A[0] all the way to right, only to move it all the way back at the end. Given that the goal is to have it in all possible positions, we could instead leave it at the end once it reaches there, permute A[0:-1] to the next permutation, and then move A[-1] all the way left, with each transposition to the left now also being useful (as in each yielding a new permutation). Modify perms_2 to do this instead. The output of your program should be the following for A = ['1', '2', '3']:

123
213
231
321
312
132

Exercise 5.7.2 (Medium): Analyze the time and space complexity of your solution to Exercise 5.7.1.

Exercise 5.7.3 (Easy): Consider the output of of the algorithm described in Exercise 14. How is each permutation different from the subsequent one? How about the last and the first permutations? What if $n = len(A)$ is even?

5.8.   Iterative Solution With Lexicographic Order

Now let's try the other approach of finding the next object in lexicographic order. Very similar to our iterative solution for generating strings, we start from the right and move left, looking for the first opportunity to modify the permutation to the next one in lexicographic order. To do this, since we are dealing with permutations, we will need to find the first element we can move to the right. We note that this is impossible to do for as long as we have a decreasing suffix. Therefore, the first step to finding the next permutation in lexicographic order is to look for the shortest non-decreasing suffix.

For example, consider the permutation 7465321. Going from right to left, the suffix 65321 is decreasing, and hence it is not possible to modify it to one that is greater in the lexicographic ordering. However, the suffix 465321 is no longer decreasing. To get the next permutation in lexicographic order, we need to move 4 to the right. It is important that we do this carefully to get the immediate next lexicographic permutation (that is, we should make sure we do not skip over any permutations). The right element to swap 4 with is the smallest element in the suffix that is greater than 4, which is 5 in this case. We swap 4 and 5 to get 564321. Finally, following the established pattern of this approach, we now need to "reset" everything following the 5 to be the smallest possible in lexicographic order. This means simply reversing the suffix since we know it is in decreasing order, and reversing it will sort it. This gives 512346 as the suffix, giving 7512346 as the final permutation to yield.

Transforming the above algorithm to code gives the following.

def perms_3(A):
    while True:
        yield A
        i = len(A) - 1
        while i > 0:
            if A[i - 1] < A[i]:
                break
            i -= 1
        if i > 0:
            # A[i - 1:] is the shortest non-decreasing suffix
            j = len(A) - 1
            while j >= i:
                if A[j] > A[i - 1]:
                    break
                j -= 1
            # A[j] is the smallest element in A[i:] that is greater
            # than A[i - 1]
            A[i - 1], A[j] = A[j], A[i - 1]
            A[i:] = A[-1:i - 1:-1]
        else:
            break

5.9.   Analysis Of The Iterative Solution

Space complexity of this iterative solution is very easy to analyze: we only use two integer variables i and j in addition to the input given. Therefore memory usage of the algorithm is $O(1)$ .

Time complexity is a bit more difficult to analyze but let's give it a shot. It is easy to see that we do at most a linear amount of work for each permutation and hence the algorithm is definitely no worse than $O(n)$ in amortized time. But is it better? It is clear that the number of operations per permutation is a linear function of the length of the shortest non-decreasing suffix. Let's build on this idea.

Given a permutation $\pi$ , let $t(\pi)$ be the length of the shortest non-decreasing suffix of $\pi$ , and let $t(\pi) = n$ if $\pi$ does not have any non-decreasing suffixes. (Note that the latter case only happens for only one permutation, namely the one last in lexicographic order which is in fully decreasing order). Note that $t(\pi)$ is exactly len(A) - i after the first while loop in our program. For example, $t(\mathtt{7465321}) = 6$ because $\mathtt{465321}$ is the shortest non-decreasing suffix of the permutation.

It is then easy to see that we do $C \cdot t(\pi)$ to get the next permutation given $\pi$ , for some constant $C$ . Therefore, to find the amortized time complexity of the algorithm, we need to find the average value of $t(\pi)$ over all permutations. In other words, we are looking for

where $\Pi_A$ is the set of all permutations of the set $A$ . Noting that $2 \le t(\pi) \le n$ , let's consider how frequently various values for $t(\pi)$ occur.

First let's look at $t(\pi) = 2$ . This means $\pi[-2] < \pi[-1]$ (using negative indexing in math notation with the exact same semantics as in Python). How many permutations have this property? Exactly half, because there is a one-to-one correspondence between permutations that have this property, and ones that do not (namely, swapping the last two elements is the bijection). Therefore, for $\frac{n!}{2}$ of the permutations we have $t(\pi) = 2$ .

How about $t(\pi) = 3$ ? This means $\pi[-3] < \pi[-2]$ while $\pi[-2] > \pi[-1]$ . How many permutations have this property? Noting that this property places an exact ordering requirement on the last three elements of the permutation, it is easy to see that given the total $3! = 6$ total possible sub-permutations of the last three elements of a given permutation, only one of them satisfies this property. Therefore, $\frac{n!}{3!}$ of all permutations have $t(\pi)=3$ .

Generalizing the same argument, we get

The last summation in the previous equation might look familiar if you have some calculus background. Let's recall one of possible definitions of the mathematical constant $e$ :

Using this identity, we have

Therefore, we have

Substituting this back into the original equation for amortized time complexity we get

Therefore, this algorithm is CAT. Combined with $O(1)$ space usage, this means this algorithm is quite efficient.

5.10.   Exercises

Exercise 5.10.1 (Easy): Modify perms_3 to sum over all values of len(A) - i for all the generated permutations. This is equivalent to calculating $\sum_{\pi \in \Pi_A}t(\pi)$ . Divide the result by $n!$ and verify that for $1 \le n \le 10$ the result of the division is approaching $e -1 = 1.71828\ldots$ .

Exercise 5.10.2 (Medium): In perms_3, we do one pass to find the right element to swap A[i - 1] with (i.e., the while loop that finds the right value for j), and then effectively another loop to reverse A[i:]. Combine these two loops into the same loop by reversing A[i:] as you look for j.

6.1.   Problem Definition

Given a set A which is guaranteed to be a non-empty list of distinct single character strings, generate all of its subsets. For example, given A = ['1', '2', '3'] we expect the output to be the following (in any order):

''
'1'
'2'
'3'
'12'
'13'
'23'
'123'

Alternatively, we can represent the subsets using binary strings of length $n$ where bit $i$ being set indicates $A[i]$ is in the subset. The output using this representation corresponding to the above output is given below:

000
100
010
001
110
101
011
111

You might have noticed that using the latter representation of binary strings, the problem is reduced to one we have already solved. In fact, the most efficient solution to the problem of generating all subsets is more or less the same as the answer to Exercise 4.7.3. We will look at this when we consider the lexicographic solution to this problem.

6.2.   Basic Recursive Solution

Given the set A, we can generate all subsets by first generating all subsets of A[1:], all of which are also subsets of A, and then adding A[0] to them to get all the subsets. This leads to the following very basic recursive solution:

def subsets(A):
    if not A:
        yield []
    else:
        for s in subsets(A[1:]):
            yield s
            yield [A[0]] + s

6.3.   Analysis Of Basic Recursive Solution

As is convention by this point, let's look at space complexity first. Each instance of the generator needs memory to store the argument it is called with, and creates new lists to generate one at a time. Therefore, subsets(A) called with $A$ of size $n$ will use memory $C_1\cdot n + C_2$ for some constants $C_1$ and $C_2$ . With the recursive call stack reaching the end at $n=0$ , we have the total memory usage as

For time complexity, we observe that a recursive call for a set of size $n-1$ is made so we do $T(n - 1)$ work minimum, and then for each subset $s$ of $A[1:]$ we create a new list of size one greater than the size of the subset $s$ . The run-time cost of creating such a set is linearly proportional to the size of the list as a copy of the list is made. Therefore, all in all, the appending of $A[0]$ will require $2^{n-1}$ operations, and the copying over of $s$ , the sum of the number of all elements in $s$ . The sum over all the lengths of $s$ is not immediately obvious. Let's dig into it a bit.

The question can be rephrased as the following: if you write all the subsets of a set $A$ , and then sum over the lengths of all these subsets, what do you get? Let's look at an example with $n=3$ :

''          0
'1'         1
'2'         1
'3'         1
'12'        2
'13'        2
'23'        2
'123'       3

Sum         12

This is a fun little mathematical puzzle that I encourage you to think about before reading further. One easy way to arrive at the answer is to think about how many times a single element is included in the sum, which is $2^{n-1}$ since exactly half the subsets contain it and half don't. Therefore, the number we are looking for is $n 2^{n-1}$ . Putting this all together we get

Here we can use the following identity to simplify the sum:

Applying this to $T(n)$ gives

Therefore, the total number of copy operations performed to generate all subsets is $n 2^{n-1}$ . The amortized run-time then is given by

This means we have Linear amortized run-time, which means this is not a very good solution.

6.4.   Exercises

Exercise 6.3.1 (Easy): Modify the code to sum over the lengths of the new lists created in the loop (i.e., sum over len([A[0]] + s)) over all the subsets generated. Verify that our formula of $T(n) = n 2^{n-1}$ correctly calculates this number.

Exercise 6.3.2 (Medium): Prove the identity we used to simplify the sum. Namely, prove

Hint: use induction.

Exercise 6.3.3 (Easy): We were a little sloppy with how we handled the recurrence relation for $T(n)$ . Specifically, we did not specify the base case. What is the correct base case? Does it affect the calculations and how the recurrence was expanded to a sum?

6.5.   Iterative Solution With Lexicographic Order

For the iterative lexicographic order approach, let's consider an alternative representation of subsets. Given $A$ of size $n$ , we can represent a subset of $A$ as a binary string of length $n$ in which each element in $A$ is present in the subset if and only if the corresponding bit in the binary string is set to one.

The table below shows all subsets of A = ['1', '2', '3'] in both representations.

Subset         Corresponding binary string
''             000
'1'            001
'2'            010
'12'           011
'1'            100
'13'           101
'12'           110
'123'          111

Representing subsets in this format, the problem is reduced to one we have already solved. Namely, we need to generate all binary strings. Since we already solved this problem in generalized case, here I provide a quick and optimized version that generates all binary strings of length $n$ in lexicographic order using arithmetic and then show how we can use simple bitwise operations to extract the subset given the binary string.

def subsets_2(A):
    n = len(A)
    for k in range(1 << n):
        yield [A[i] for i in range(n) if k & (1 << i)]

I leave the time ans space complexity analysis of this solution as exercises below.

6.6.   Exercises

Exercise 6.6.1 (Easy): Analyze the space complexity and the amortized run-time complexity of the subsets_2 solution above.

7.1.   Problem Definition

Having looked at generating all subsets, next natural step is to turn our attention to the problem generating subsets of a certain size, also known as combinations of a set—after all, we are looking at combinatorial generation problems! Given a set $A$ of size $n$ , and an integer $0 \le k \le n$ , we want to generate all subsets of $A$ of size $k$ . For example, given A = ['1', '2', '3', '4'] and $k=2$ we should generate the following:

12
13
14
23
24
34

As you might remember from basic discrete mathematics,

subsets are listed.

In general, the size of the output, which is the number of combinations of size $k$ chosen from a set of size $n$ , is given by ${n \choose k}$ , which is read "$n$ choose $k$ . We have

which is fairly easy to prove using a basic counting argument.

There is another way to represent combinations in a program. Similar to how subsets of a set of size $n$ can be represented as binary strings of length $n$ , we can represent combinations of size $k$ chosen out of a set of size $n$ as binary strings of length $n$ in which exactly $k$ bits are set to one. Using this representation, the above list of combinations becomes the following:

1100
1010
1001
0110
0101
0011

We will look at generating the combinations using both of these representations.

7.2.   Basic Recursive Solution

Suppose you are given $n$ items and asked to choose $k$ out of them. To do this, you pick the first item and look at it. You have two options. You either pick the item, in which case you have reduced the problem to that of choosing $k-1$ items from the $n-1$ items left, or you can choose not to pick the first item in which the problem is reduced to choosing $k$ from the $n-1$ items left. This observation leads to the recurrence ${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}$ . Of course, the right base cases need to be stated here (see the exercises section coming up).

Following the exact same logic, we can write a very basic recursive solution:

def combinations(A, k):
    if k == 0:
        return [[]]
    if len(A) == k:
        return [list(A)]
    result = [[A[0]] + c for c in combinations(A[1:], k - 1)]
    result += combinations(A[1:], k)
    return result

7.3.   Analysis Of Basic Recursive Solution

For space complexity, we keep the entirety of ${n choose k}$ combinations in memory each of which is a list of length $k$ . Therefore, we are looking at the following space complexity:

Assuming $k$ is constant and small relative to $n$ , we can fairly easily see that the above is $O(n^k)$ . However note that if $k$ is not constant, and is closer to $\frac{n}{2}$ ,

Note that in practice we store both $(k-1){n - 1 \choose k - 1}$ and $(k-1){n \choose k - 1}$ space concurrently with the larger $k{n \choose k}$ space allocated for the larger list due to the recursive calls but since it is easy to see both of those lists use less space than the larger list, storing them concurrently only increases memory usage by a constant factor of the memory used to store the end result. Therefore the big-O characterization of the space complexity of the algorithm above is still correct even though we did not take the extra lists created by the recursive calls into account.

Amortized run-time complexity analysis of this solution is a bit tricky. I am leaving it as an exercise for those of you interested in a challenge.

7.4.   Exercises

Exercise 7.4.1 (Easy): State the correct base case conditions for the recurrence ${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}$ .

Exercise 7.4.2 (Easy): Prove that assuming $k$ is constant we have $\frac{n!}{(k-1)!(n-k)!} = O(n^k)$ .

Exercise 7.4.3 (Difficult): Analyze the amortized run-time complexity of the combinations function as a function of $n$ and $k$ .

7.5.   Iterative Solution With Lexicographic Order

For an iterative solution, let's consider the alternative binary string representation as it lends itself to a simpler lexicographic order iterative solution. Since in this representation the set we are choosing from itself does not matter, we modify our code to simply accept the size of the set, $n$ , instead. Here is what the output should be for $n=4$ and $k=2$ :

0011
0101
0110
1001
1010
1100

As before, the strategy is to find the first element we can increment going from right to left. In this case, to increment an element we need to change it from 0 to 1. To do that, we need to change another 1 to a 0. Noticing all this it is fairly easy to reason that what we should look for is the first instance of 01 which we will then replace with 10. Afterwards we have to reset everything following the 10 to be the smallest lexicographic element that has the right number of ones and zeros. To do this, we need to keep track of how many ones we encounter. Finally, we note that the last item in lexicographic order will always be 11...1100...00 which does not have a 01 in it, and hence if we can't find such an occurrence we know we are at the end of the generation. Here is the implementation of this algorithm:

def combinations_2(n, k):
    c = [0] * (n - k) + [1] * k
    while True:
        yield c
        # Look for the right-most 01 while counting ones encountered.
        i = n - 2
        ones = 0
        while i >= 0 and c[i:i + 2] != [0, 1]:
            if c[i + 1] == 1:
                ones += 1
            i -= 1
        if i < 0:
            break
        # Change the 01 to 10 and reset the suffix to the smallest
        # lexicographic string with the right number of ones and zeros.
        c[i:] = [1] + [0] * (n - i - ones - 1) + [1] * ones

Space complexity of this solution is rather trivial but amortized run-time complexity is a bit tricky. I am leaving both of them as exercises below as by now you should have enough experience with the analysis to be able to tackle them on your own.

7.6.   Exercises

Exercise 7.6.1 (Easy): Write a function convert that given a list A and a binary string of length $n$ returns returns the corresponding subset of $A$ . For example, convert([1, 2, 3, 4], [0, 1, 0 ,1]) should return [2, 4].

Exercise 7.6.2 (Easy): Using the function you wrote in the previous exercise, modify the combinations_2 to take a list A as the input instead of $n$ and have it yield subsets of size $k$ of the list A.

Exercise 7.6.3 (Medium): Prove that the first 01 going from right to left is the first index in which we can switch a 0 and a 1 to get to the next combination in lexicographic order.

Exercise 7.6.4 (Easy): Analyze the space complexity of the combinations_2 solution.

Exercise 7.6.5 (Difficult): Analyze the amortized time complexity of the combinations_2 solution.