Generating subsets

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}:

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:

• python
• java

• 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
  

• 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:

• python
• java

• 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
  

• 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;
      }
  

• 2025 3
• 2024 3
• 2023 1
• 2022 2