Power Set Generator Using Binary Numbers

PowerSetGenerator.java

/* File:    PowerSetGenerator.java
 * Created: 9/28/2018
 * Author:  Sabbir Manandhar
 *
 * Copyright (c) 2018 Hogwart Inc.
 */

//=======================================================================================

import java.util.ArrayList;
import java.util.List;

//=======================================================================================

/**
 * @author Sabbir Manandhar [email protected]
 * @version 1.0
 */
public class PowerSetGenerator {

  /**
   * Driver method
   * @param args
   */
  public static void main(String[] args) {
    PowerSetGenerator generator = new PowerSetGenerator();
    for (List<Character> set : generator.generatePowerSets(new char[]{'A', 'B', 'C', 'D'})) {
      System.out.println(set.toString());
    }
  } // main

  //-------------------------------------------------------------------------------------

  /**
   * For each of the number from 0 to 2^n - 1, generate a sub set represented by the number.
   * Assemble all the subsets together to generate Power Set.
   * @param set Input Set.
   * @return Power Set of the given input set.
   */
  public List<List<Character>> generatePowerSets(char[] set) {
    List<List<Character>> powerSets = new ArrayList<>();
    int max = 1 << set.length; // max = 2^n formed by right shifting 1 for n times
    for (int i = 0; i < max; i++) {
      powerSets.add(convertNumberToSet(set, i)); // for each binary number from 0 to 2^n - 1, generate sub set
    }
    return powerSets;
  } // generatePowerSets

  //-------------------------------------------------------------------------------------

  /**
   * Generate subset represented by given number
   * @param set Given Input set.
   * @param number Given number which represents a subset
   * @return Subset represented by given number
   */
  private List<Character> convertNumberToSet(char[] set, int number) {
    List<Character> subset = new ArrayList<>();
    int index = 0;
    for (int i = 1; index < set.length; i = i << 1, index++) {
      if ((number & i) == i) { // determine if index th bit is 1 or 0 in the given number
        subset.add(set[index]); // include index th number if corresponding bit is 1 in the given number
      }
    }
    return subset;
  } // convertNumberToSet

} // PowerSetGenerator