by Marko Riedel
The goal is to enumerate all subsets of some set of elements stored in an array. It is true for any such subset that an original element from the array is either present or absent. This means that we can enumerate subsets by counting in binary from 0 to 2n - 1, where n is the number of elements in the array. If bit k is set, then we include the element at k, otherwise it is left out. We could use machine integers to count to 2n - 1, but then the size of a machine integer would limit the size of the array whose subsets we wish to enumerate.
We will implement an enumerator for subsets and add a category to NSArray.
The state of the enumerator is defined by the array whose subsets we wish to enumerate, the number of elements in the array, an array that stores the binary digits of the counter and a flag that indicates whether we are done.
The enumerator retains the array. We store the number of elements in the instance variable count for easy reference. We allocate space for the binary digits of the counter and set them all to zero.
The first part of nextObject computes the current subset. It checks every binary digit and includes the corresponding item if the bit is set.
The second part increments the counter, i.e. it implements binary addition. Scan from the right until you find a zero digit, increment this digit and set remaining positions to zero. We are done enumerating when there is no zero digit, and indicate this by setting the flag done. The result was created with arrayWithCapacity:, so it is autoreleased.
It remains to clean up: free the buffer that holds the binary digits and release the array (this matches the retain from initWithArray.) We put the method subsetEnumerator into a category. The subset enumerator is autoreleased.
You may find yourself wanting to sort subsets according to the number of elements if you use this category. This is done with
We can dispense with the array of digits if the number of subsets fits into an unsigned long integer. This simplifies the algorithm quite a lot, since we need only convert the counter value to binary.
The function subset extracts binary digits one by one and includes an element if the corresponding digit is one. The elements of the subset are collected at the front of the array, and the remaining locations are marked with a NULL pointer.
The loop at the heart of the program counts from zero to 2n - 1.