3
\$\begingroup\$

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")
\$\endgroup\$
2
  • \$\begingroup\$ The above example missing the empty set (). \$\endgroup\$ Jul 9, 2021 at 12:14
  • \$\begingroup\$ @HaruoWakakusa Good point, I forgot to mention that I do not want the empty set to be part of the result. \$\endgroup\$ Jul 10, 2021 at 13:35

3 Answers 3

4
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ The total number of combinations is known in advance, adding allCombinations.reserveCapacity(1 << elements.count) makes it a bit faster. \$\endgroup\$
    – Martin R
    Oct 19, 2021 at 7:08
  • \$\begingroup\$ @MartinR: I've had mixed results with reserveCapacity in the past. I'll do more investigation and get back to you as soon as possible. \$\endgroup\$
    – ielyamani
    Oct 19, 2021 at 11:00
  • 1
    \$\begingroup\$ Wow great answer thank you \$\endgroup\$ Oct 19, 2021 at 11:36
  • \$\begingroup\$ @MartinR: using this benchmarking tool by Apple, this chart doesn't show a valuable gain by reserving capacity. \$\endgroup\$
    – ielyamani
    Oct 19, 2021 at 12:44
2
\$\begingroup\$
  • 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)
\$\endgroup\$
1
  • \$\begingroup\$ No need to initialize a new array. dropFirst method returns a SubSequence which conforms to collection as well. You can also avoid force unwrapping the first element by using prefix(1) instead. isEmpty ? [[]] : dropFirst().powerSet.flatMap { [$0, prefix(1) + $0] }. Btw you can simply pass the set initializer to the map method Set([1, 2, 3].powerSet.map(Set.init)) and you can also pass a sequence with an empty sequence to the subtracting method: subtracting([[]]) \$\endgroup\$
    – Leo Dabus
    Feb 21, 2022 at 2:52
1
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Wow, very interesting, thank you so much for taking the time to do all this. \$\endgroup\$ Aug 16, 2021 at 11:24
  • \$\begingroup\$ In your second improvement, could you please confirm that appending a combination inside the For-loop is faster than append all the contents of combinationsOfRemainingElements at once \$\endgroup\$
    – ielyamani
    Oct 16, 2021 at 22:25
  • \$\begingroup\$ @ielyamani: I am not sure if I understand what you mean. The elements are appended at once in allCombinations.append(contentsOf: combinationsOfRemainingElements). \$\endgroup\$
    – Martin R
    Oct 17, 2021 at 2:12
  • \$\begingroup\$ @ielyamani: I cannot measure a significant time difference. \$\endgroup\$
    – Martin R
    Oct 17, 2021 at 10:02
  • \$\begingroup\$ OK, I see, maybe it's just a TIO thing: At a 99% CPU share, with your code the best I could get was 0.32s; vs 0.26s with this tiny tweak. With a set count of 22, the improvement is a bit more pronounced. \$\endgroup\$
    – ielyamani
    Oct 17, 2021 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.