Skip to content

Instantly share code, notes, and snippets.

@JadenGeller
Last active October 23, 2023 20:47
Show Gist options
  • Save JadenGeller/6174b3461a34465791c5 to your computer and use it in GitHub Desktop.
Save JadenGeller/6174b3461a34465791c5 to your computer and use it in GitHub Desktop.
Powerset
extension Array {
var powerSet: [[Element]] {
guard !isEmpty else { return [[]] }
return Array(self[1...]).powerSet.flatMap { [$0, [self[0]] + $0] }
}
}
print([1,2,3,4].powerSet) // -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]
extension Array {
var powerSet: [[Element]] {
guard !isEmpty else { return [[]] }
let tailPowerSet = Array(self[1...]).powerSet
return tailPowerSet.map { [self[0]] + $0 } + tailPowerSet
}
}
print([1,2,3,4].powerSet) // -> [[1, 2, 3, 4], [1, 2, 3], [1, 2, 4], [1, 2], [1, 3, 4], [1, 3], [1, 4], [1], [2, 3, 4], [2, 3], [2, 4], [2], [3, 4], [3], [4], []]
@KeithPiTsui
Copy link

KeithPiTsui commented Jul 12, 2018

So cool. If I understand correctly, it is using induction on the length of array.
The base is length zero, an empty array.
The inductive part is support we have the power set of an array of length n, P(An) , we can computer the power set of an array of length (n + 1), P(An+1) , by for each set p of P(An), it would produce two sets, p and p + A[n], that is itself and itself with the new added element, and the set of those all produced sets is the power set of array length (n + 1), i.e. P(An+1).
Moreover, this algorithm not just suitable for array but for any collection. The following code block is my improvement following your idea. I appreciate any information (comment or suggestion) you could give.
PowerSet of Collection

extension Collection {
  public var powerSet: [[Element]] {
    guard let fisrt = self.first else {return [[]]}
    return self.dropFirst().powerSet.flatMap{[$0, [fisrt] + $0]}
  }
}
let s: Set<Int> = [1,2,3]
s.powerSet //[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
let a: Array<Int> = [1,2,3]
a.powerSet //[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

@michzio
Copy link

michzio commented May 25, 2020

what is complexity of power set algorithm it seems to growth hugely in my case like O(n!) or O(n^k)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment