Generate all subsets of a set

Question

The goal of the function below is to generate all subsets of a given set, i.e. a collection of sets that contain all possible combinations of the elements in the set. Note that for my application I do not want the empty set to be part of the result.

Exemple:

• input: (1,2,3)
• output: ((1),(2),(3),(1,2),(1,3),(2,3),(1,2,3))

Notes about the code:

1. The function uses recursion
2. The Set.removingFirst() method is defined so that the code in the function reads more naturally
3. Basic unit tests are provided

I am interested in comments about the algorithm, swift features usage, naming, code presentation, etc. Any useful comment is appreciated.

Thanks

func combinations<T>(of set: Set<T>) -> Set<Set<T>> {
        
    if set.count == 0 {
      
        return []
        
    } else if set.count == 1 {
     
        return [set]
        
    } else {
        
        var allCombinations: Set<Set<T>> = []
        
        let (firstElement, diminishedSet) = set.removingFirst()
       
        for combinationOfDiminishedSet in combinations(of: diminishedSet) {
            
            allCombinations.insert(
                [firstElement]
            )
            allCombinations.insert(
                combinationOfDiminishedSet.union([firstElement])
            )
            allCombinations.insert(
                combinationOfDiminishedSet
            )
        }
        
        return allCombinations
    }
}


extension Set {
    
    func removingFirst() -> (element: Element, set: Set) {
        
        var set = self
        let element = set.removeFirst()
        
        return (element: element, set: set)
    }
}


assert(
    combinations(of: Set<Int>()) == Set<Set<Int>>(),
    "empty set"
)

assert(
    combinations(of: [1]) == [[1]],
    "set containing only one element"
)

assert(
    combinations(of: [1,2]) == [[1], [2], [1,2]],
    "set containing two elements"
)

assert(
    combinations(of: [1,2,3]) == [[1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]],
    "set containing three elements"
)


print("all tests passed")

Answer 1

Algorithm

Generating combinations of a set is a classic problem. You chose the recursive route, which incurs auxiliary space: All those sets that were not returned will consume temporary memory. You may also be limited in the number of recursive calls by the size of the stack in your system. To overcome this, and with the help of some bit manipulation, you could create a generator that gives you only the next combination. After consuming that combination, you could ask for the next one.

---

Dangerous extension

This extension calls for trouble, since there is no check for non emptiness:

extension Set {
    
    func removingFirst() -> (element: Element, set: Set) {
        
        var set = self
        let element = set.removeFirst()
    
        return (element: element, set: set)
    }
}

With association to your combinations(_:) it's fine since you're checking; BUT! It wouldn't be safe to used it outside this context, since removing from an empty set would result in a fatal error.

The data structures that are more suitable to be consumed from the left and allow appending elements to the right, are: a Linked list or a Deque.

---

Linting (Code presentation)

It would be nice if the use of new lines before and after the curly brackets was consistent (especially after the return keyword). At the end of the day, it's a matter of personal taste.

---

Naming

• firstElement: It could be misleading since a set is not an ordered collection, maybe use head instead.
• diminishedSet: To me, it feels unnatural/unfamiliar. tail would be a more suitable alternative.

---

Alternative implementation

Here is a pretty common way to generate a power set:

func combinations<T>(of elements: Set<T>) -> [[T]] {
    var allCombinations: [[T]] = []
    for element in elements {
        let oneElementCombo = [element]
        for i in 0..<allCombinations.count {
            allCombinations.append(allCombinations[i] + oneElementCombo)
        }
        allCombinations.append(oneElementCombo)
    }
    return allCombinations
}

Note that the return value is [[T]] to avoid unnecessary hashing, since the uniqueness is guaranteed by the fact that elements is a Set<T>.

---

Benchmarks

Here are some benchmarks on TIO with -O optimization on a 20-element set:

Implementation	Time
Original	5.14 seconds
Daniel's	2.05 seconds
Martin's	0.32 seconds
This	0.19 seconds

Answer 2

• Your removingFirst() is not necessary. Set has a first and a dropFirst() that you can use to get those values.

• The typical Swift developer would expect to see this algorithm as an extension rather than a free function.

• This is a power set algorithm with the empty set subtracted. It would probably be better to just implement powerSet and then subtract the empty set. A google search will find a few implementations of powerSet. Here's my favorite:

extension Collection {
    var powerSet: [[Element]] {
        guard !isEmpty else { return [[]] }
        return Array(dropFirst()).powerSet.flatMap { [$0, [self.first!] + $0] }
    }
}

let result = Set(
    [1, 2, 3]
        .powerSet
        .map { Set($0) }
)
.subtracting(Set([Set()]))

print(result)

Answer 3

Some simplifications (with a small performance improvement)

What I noticed first is that your recursive function has two terminating conditions: set.count == 0 and set.count == 0. Why is that necessary?

Well, if we comment out the second terminating condition

//} else if set.count == 1 {
//    return [set]

then it doesn't work anymore:

print(combinations(of: [1, 2, 3]))
// Output: []

But why is that? The reason is that adding the single-element set of the first element

allCombinations.insert([firstElement])

is done inside the loop which iterates of the combinations of the diminished set. If we move that statement before the loop then the code simplifies to

func combinations<T>(of set: Set<T>) -> Set<Set<T>> {
    if set.isEmpty {
        return []
    }
    
    var allCombinations: Set<Set<T>> = []
    let (firstElement, diminishedSet) = set.removingFirst()
    allCombinations.insert([firstElement])
    for combinationOfDiminishedSet in combinations(of: diminishedSet) {
        allCombinations.insert(
            combinationOfDiminishedSet.union([firstElement])
        )
        allCombinations.insert(
            combinationOfDiminishedSet
        )
    }
    return allCombinations
}

This makes the code shorter, simpler, and a bit faster, since the single-element set is added only once, not repeatedly for each subset of the diminished set.

I also prefer isEmpty to check for an empty collection. It makes no real difference for a Set, but for general collection, count can be a \$ O(N) \$ operation, where \$ N \$ is the number of elements in the collection.

In addition, I have omitted the else statement because it is not necessary. That saves one level of indentation for the remaining larger code block.

Choosing the right data structure (and a large performance improvement)

You function returns a Set of all combinations with elements from the given set. All those combinations are different, but each insert() call has to check for duplicates. If we return an Array instead then we can simply append() each combination.

The same happens when building the combinations: in

combinationOfDiminishedSet.union([firstElement])

the firstElement is distinct from all elements in combinationOfDiminishedSet, but the union() call still has to check for duplicates.

I would therefore suggest to return a nested array instead of a nested set.

Changing the input from a set to an array makes the code more flexible: The given elements need not conform to the Hashable protocol anymore, and repeated elements are possible.

Actually it is even better to use an ArraySlice as the input because then removing the first element becomes a \$ O(1) \$ operation. One can still have a wrapper function taking an Array (or a Set if you prefer).

This leads to the following implementation:

func combinations<T>(of elements: ArraySlice<T>) -> [[T]] {
    guard let firstElement = elements.first else {
        return []
    }
    
    var allCombinations: [[T]] = [[firstElement]]
    let combinationsOfRemainingElements = combinations(of: elements.dropFirst())
    for combination in combinationsOfRemainingElements {
        allCombinations.append(combination + [firstElement])
    }
    allCombinations.append(contentsOf: combinationsOfRemainingElements)
    return allCombinations
}

// Wrapper function taking an array:
func combinations<T>(of elements: [T]) -> [[T]] {
    combinations(of: elements[...])
}

// Wrapper function taking a set:
func combinations<T>(of elements: Set<T>) -> [[T]] {
    combinations(of: Array(elements))
}

Performance comparison

All tests were done on a MacBook Air (1.1 GHz Quad-Core Intel Core i5), with the code compiled as a Command Line application in “Release” configuration.

let mySet = Set(1...20)
let start = Date()
let c = combinations(of: mySet)
let end = Date()
print(c.count, end.timeIntervalSince(start))

Results:

Implementation	Time
Original code	3.0 seconds
First improvement	2.5 seconds
Second improvement	0.2 seconds

Reinvent the wheel?

The Swift Algorithms is “an open-source package of sequence and collection algorithms, along with their related types.”

It provides methods to compute the combinations of all sizes or of a given range of sizes from a collection:

for c in [1, 2, 3].combinations(ofCount: 1...3) {
    print(c)
}

Output:

[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]

Even if you want to implement your own code it may be instructive to look at the implementation from that library. It demonstrates how to return the combinations as a “lazy collection” – i.e. as a collection where each combination is computed (efficiently) only when accessed.