Generating subsets - Algorithm Design and Analysis

In this post, we will discuss the problem of generating all subsets of a given set of elements. A subset is a collection of elements that are selected from a set. The table below shows all subsets of the set {1, 2, 3}:

Subsets {1,2,3}
{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}
-----------------------------

For a set of n elements, there are 2^n subsets. The problem of generating all subsets of a set of elements is a common problem in computer science and has applications in various fields, such as combinatorial optimization, cryptography, and data analysis.

1. The Binary reflected Gray code algorithm¶

To generate all subsets, the binary reflected Gray code algorithm generates the subsets by reflecting the binary representation of the subset index. The Gray code is a binary numeral system where two successive values differ in only one bit. The reflected Gray code is obtained by reversing the order of the bits of the Gray code.

If n=1 make list L of two bit strings 0 and 1
else
generate recursively list L1 of bit strings of length n-1 copy list L1 in reverse order to get list L2 add 0 in front of each bit string in list L1 add 1 in front of each bit string in list L2 append L2 to L1 to get L return L


We can implements the algorithm using recusion as follows:  


::::{tab-set}
:::{tab-item} Python
```python
def gray_code(n):
    if n == 1:
        return ['0', '1']
    else:
        L1 = gray_code(n - 1)
        L2 = L1[::-1]
        L1 = ['0' + x for x in L1]
        L2 = ['1' + x for x in L2]
        return L1 + L2

:::{tab-item} Java
```java
List<String> generate(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("n must be greater than 0");
        }

        List<String> grayCodeList = new ArrayList<>();
        if (n == 1) {
            grayCodeList.add("0");
            grayCodeList.add("1");
            return grayCodeList;
        }

        // Recursively generate Gray code for (n-1) bits
        List<String> smallerGrayCode = generate(n - 1);

        // Copy the list and reverse it
        List<String> reversedGrayCode = new ArrayList<>(smallerGrayCode);
        Collections.reverse(reversedGrayCode);

        // Add '0' prefix to the original list
        for (int i = 0; i < smallerGrayCode.size(); i++) {
            smallerGrayCode.set(i, "0" + smallerGrayCode.get(i));
        }

        // Add '1' prefix to the reversed list
        for (int i = 0; i < reversedGrayCode.size(); i++) {
            reversedGrayCode.set(i, "1" + reversedGrayCode.get(i));
        }

        // Merge both lists
        smallerGrayCode.addAll(reversedGrayCode);

        return smallerGrayCode;
    }
```


The function `gray_code(n)` generates the Gray code for n bits. The base case is when n=1, in which case the function returns the list ['0', '1']. Otherwise, the function generates the Gray code for (n-1) bits and then copies the list in reverse order. It then adds '0' as a prefix to each bit string in the original list and '1' as a prefix to each bit string in the reversed list. Finally, the function appends the reversed list to the original list and returns the result.

We can avoid unnecessary copying of the list by using a single list and swapping the elements in place. The following **iterative** implementation demonstrates this approach:

::::{tab-set}
:::{tab-item} Python
```python
def gray_code(n):
    if n <= 0:
        raise ValueError("n must be greater than 0")

    gray_code_list = ['0', '1']
    for i in range(2, n + 1):
        for j in range(len(gray_code_list) - 1, -1, -1):
            gray_code_list.append('1' + gray_code_list[j])

        for j in range(len(gray_code_list) // 2):
            gray_code_list[j] = '0' + gray_code_list[j]

    return gray_code_list
```
:::
:::{tab-item} Java
```java
List<String> generateIterative(int n){
        List<String> grayCodeList = new ArrayList<>();
        grayCodeList.add("0");
        grayCodeList.add("1");

        for (int i = 2; i <= n; i++) {
            int size = grayCodeList.size();

            // Reflect and add '1' prefix
            for (int j = size - 1; j >= 0; j--) {
                grayCodeList.add("1" + grayCodeList.get(j));
            }

            // Add '0' prefix to the first half (already exists, just update)
            for (int j = 0; j < size; j++) {
                grayCodeList.set(j, "0" + grayCodeList.get(j));
            }
        }
        return grayCodeList;
    }
```
:::