在 swift 中查找字符串数组的所有组合

Question

我有一个字符串数组，我想找到它的元素的所有可能组合

For Example :

Array = [A,B,C,D]

should produce result as :

[A,AB,AC,AD,ABC,ABD,ACD,ABCD,B,BC,BD,BCD,C,CD,D]

这是我的逻辑：

  var array = ["A", "B", "C","D"]
  var list = [String]()
  for i in 0..<array.count{
    let c = array[i]
    list.append(c)
    var d = c
    for count in 1..<array.count{

        if i+count < array.count{
            for j in i+count..<array.count{
                var a = d
                a.appendContentsOf(array[j])
                print("a : \(a)")
                list.append(a)
            }

        }
        d = c
        d.appendContentsOf(array[count])
        print("d : \(d)")
    }
}
print(list.description)

Its Output is :

["A", "AB", "AC", "AD", "ABC", "ABD", "ACD", "B", "BC", "BD", "BBD", "C", "CD", "D"]

此输出缺少 ABCD 并且错误地将 BCD 打印为 BBD

任何人请通过增强我的代码或为此提出您自己的逻辑来帮助我。

Answer 1

您似乎想要数组的 Power set。

In mathematics, the power set (or powerset) of any set S is the set of all subsets of S, including the empty set and S itself.

我在 GitHub 上找到了这个代码。

extension Array {
    var powerset: [[Element]] {
        if count == 0 {
            return [self]
        }
        else {
            let tail = Array(self[1..<endIndex])
            let head = self[0]

            let withoutHead = tail.powerset
            let withHead = withoutHead.map { [=10=] + [head] }

            return withHead + withoutHead
        }
    }
}

println([1,2,3,4].powerset) -> [[4, 3, 2, 1], [3, 2, 1], [4, 2, 1], [2, 1], [4, 3, 1], [3, 1], [4, 1], [1], [4, 3, 2], [3, 2], [4, 2], [2], [4, 3], [3], [4], []]

Answer 2

@yannick的回答很接近。

通过计算你的集合的幂集，你可以获得所有可能的子集（包括你的原始集和空集）。

获得幂集后，您只需将子集连接成一个字符串即可获得您要查找的结果。

这是完整的解决方案（连同更新的代码和大量评论）：

extension Array {
    var powerset: [[Element]] {
        guard count > 0 else {
            return [[]]
        }

        // tail contains the whole array BUT the first element
        let tail = Array(self[1..<endIndex])

        // head contains only the first element
        let head = self[0]

        // computing the tail's powerset
        let withoutHead = tail.powerset

        // mergin the head with the tail's powerset
        let withHead = withoutHead.map { [=10=] + [head] }

        // returning the tail's powerset and the just computed withHead array
        return withHead + withoutHead
    }
}

let myArray = ["A", "B", "C", "D"]
print(myArray.powerset) // -> [["D", "C", "B", "A"], ["C", "B", "A"], ["D", "B", "A"], ["B", "A"], ["D", "C", "A"], ["C", "A"], ["D", "A"], ["A"], ["D", "C", "B"], ["C", "B"], ["D", "B"], ["B"], ["D", "C"], ["C"], ["D"], []]

// joining the subsets
let myResult = myArray.powerset.map { [=10=].sort().joinWithSeparator("") }
print(myResult) // -> ["A", "AB", "ABC", "ABCD", "ABD", "AC", "ACD", "AD", "B", "BC", "BCD", "BD", "C", "CD", "D", ""]

PS

请注意，此解决方案使用递归方法，而您的解决方案使用迭代方法。

PPS

如果您不想在您的解决方案中使用空字符串 ""，您可以将其过滤掉：

let myResult = myArray.powerset.map({ [=11=].sort().joinWithSeparator("") }).filter({ [=11=] != "" })

print(myResult) // -> ["A", "AB", "ABC", "ABCD", "ABD", "AC", "ACD", "AD", "B", "BC", "BCD", "BD", "C", "CD", "D"]

Answer 3

我找到了一个更简洁的答案。Power set of Collection.

原理是对集合的大小进行归纳，如 link 所示。这是 link 中的代码副本。并归功于其作者。

extension Collection {
  public var powerSet: [[Element]] {
    guard let fisrt = self.first else {return [[]]}
    return self.dropFirst().powerSet.flatMap{[[=10=], [fisrt] + [=10=]]}
  }
}
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]]

Answer 4

我知道已经给出了一些很好的答案，但是来自 Java 的背景，我只是想放弃一些使用位运算符的见解（令人惊讶的是它在 Swift 中仍然有效）。

你可以试试这个：

let len = stringArr.count

for i in 0 ..< (1<<len){
    print("{", terminator: "")

    for j in 0 ..< len {
        if ((i & (1<<j)) > 0) {
            print(stringArr[j], terminator: "")
        }
    }

    print("}")
}

您可以找到有关按位运算符的更多信息here

Answer 5

我也拍一张logic作为参考：

extension RangeReplaceableCollection {
    var subSets : [SubSequence] {
        guard !isEmpty else { return [] }
        let count = self.count
        let n = 1 << count - 1
        var subSequences: [SubSequence] = .init(repeating: SubSequence(), count: n-1)
        (0 ..< n).forEach { x in
            autoreleasepool {
                var counter = 0
                for element in self {
                    if x & 1 << counter > 0 {
                        subSequences[x-1].append(element)
                    }
                    counter += 1
                }
            }

        }
        return subSequences + [self[...]]
    }
}

游乐场测试：

["A", "B", "C","D"].subSets  // [["A"], ["B"], ["A", "B"], ["C"], ["A", "C"], ["B", "C"], ["A", "B", "C"], ["D"], ["A", "D"], ["B", "D"], ["A", "B", "D"], ["C", "D"], ["A", "C", "D"], ["B", "C", "D"], ["A", "B", "C", "D"]]

"ABCD".subSets  // ["A", "B", "AB", "C", "AC", "BC", "ABC", "D", "AD", "BD", "ABD", "CD", "ACD", "BCD", "ABCD"]

在 swift 中查找字符串数组的所有组合

Find all combination of string array in swift

arrays

logic

combinations

swift