a Java algorithm to iterate through any set's power set

The power set of a set is the set of all subsets of the set, including the set itself and the empty set. There are often occasions in computer science where it is necessary to walk through the power set of a set and examine its members.

If the size of a set is n, then the size of the set's power set is 2ⁿ. Thus, building an entire power set at once can consume a very large amount of memory for large sets. Here is a Java implementation of an algorithm to generate a power set and process its members "on the fly," so there is no need to hold the entire power set in memory. This algorithm is iterative and does not actually accumulate a "set of subsets," but rather it performs the processing action immediately on each member and then forgets about it.

If instead you wish to build the entire power set at once, storing it in memory as a set of sets, to be processed afterwards, you can still do that. Just create an action that accumulates the members as they are processed.

interface PowerSetAction

import java.util.Set;

/**
 * Power set action.
 *
 * <p><b>Details:</b> This interface defines an action to be performed on each
 * member of a power set.  {@link PowerSetProcessor} invokes this action by
 * calling {@link #processSet(Set)}.</p>
 *
 * @param <Type> the type of element in the set
 */
public interface PowerSetAction<Type>
{

    /**
     * Performs action.
     *
     * <p><b>Details:</b> This method is called by the power set processor to
     * perform an action on the given power set member.  If the power set
     * processor should continue to perform this action on subsequent members,
     * this method returns {@code false}, {@code true} otherwise.</p>
     *
     * @param ipSet the set to process
     * @return true iff power set processing should abort
     */
    boolean processSet(Set<Type> ipSet);

}

class PowerSetProcessor

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class PowerSetProcessor
{

    /**
     * Iterates on power set.
     *
     * <p><b>Details:</b> This method performs the given action on each member
     * of the given set's power set until the entire power set has been
     * processed or the action result for one of the power set's members
     * indicates that power set processing should abort.  This method returns
     * {@code true} if power set processing was aborted before the entire power
     * set was processed, {@code false} otherwise.</p>
     *
     * @param <Type> the type of element in the set
     * @param ipsSet the set
     * @param ipSetAction the action
     * @return true iff power set processing was aborted
     */
    public static <Type> boolean processPowerSet
    (   Set<Type> ipsSet,
        PowerSetAction<Type> ipSetAction
    )
    {
        boolean vzAbort;
        if (ipsSet.isEmpty())
        {
            vzAbort = ipSetAction.processSet(ipsSet);
            return vzAbort;
        }
        List<Type> vplLeft = Collections.emptyList();
        List<Type> vplRight = new ArrayList<Type>(ipsSet);
        return processPowerSet(vplLeft, vplRight, ipSetAction);
    }

    /**
     * Recursion support for processPowerSet method.
     *
     * <p><b>Details:</b> This method is the recursive implementation of
     * {@link #processPowerSet(Set, PowerSetAction)}.  It processes each set
     * produced by combining the "left set" with each member of the power set of
     * the "right set."  Both sets are represented as lists, to facilitate more
     * efficient and predictable processing.  This method returns {@code true}
     * if and only if set processing was aborted before every set could be
     * processed.</p>
     *
     * @param <Type> the type of element in the set
     * @param iplLeft the left set
     * @param iplRight the right set
     * @param ipSetAction the action
     * @return true iff processing was aborted
     */
    private static <Type> boolean processPowerSet
    (   List<Type> iplLeft,
        List<Type> iplRight,
        PowerSetAction<Type> ipSetAction
    )
    {
        boolean vzAbort;
        if (iplRight.size() == 1)
        {
            Set<Type> vpsTestSet = new HashSet<Type>(iplLeft);
            vzAbort = ipSetAction.processSet(vpsTestSet);
            if (vzAbort)
                return true;
            List<Type> vplTestSet = new ArrayList<Type>(iplLeft);
            vplTestSet.addAll(iplRight);
            vpsTestSet = new HashSet<Type>(vplTestSet);
            vzAbort = ipSetAction.processSet(vpsTestSet);
            return vzAbort;
        }
        iplLeft = new ArrayList<Type>(iplLeft);
        iplRight = new ArrayList<Type>(iplRight);
        int vnLast = iplRight.size() - 1;
        Type vpLast = iplRight.remove(vnLast);
        vzAbort = processPowerSet(iplLeft, iplRight, ipSetAction);
        if (vzAbort)
            return true;
        iplLeft.add(vpLast);
        vzAbort = processPowerSet(iplLeft, iplRight, ipSetAction);
        return vzAbort;
    }

}