iOS swift 排列组合 算法

排列组合的算法有很多，例如递归、穷举，下面我们用位运算的方式来实现全组合的算法

- 原理：

我们以[1, 2, 3]为例，全组合有：

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

刚好有8中组合方式，对应的0-7的二进制数

• [] --- 000
• [1] --- 001
• [2] --- 010
• [1, 2] --- 011
• [3] --- 100
• [1, 3] --- 101
• [2, 3] --- 110
• [1, 2, 3] --- 111

由此得出算法，用代码翻译出来即可

    func combination(t: [Int]) {
        for i in 0..<1<<t.count {
            printEachResult(t: t, index: i)
        }
    }
    
    func printEachResult(t: [Int], index: Int) {
        
        var printArray = [Int]()
        for i in 0..<t.count {
            if (index>>i)&1 == 1 {
                printArray.append(t[i])
            }
        }
        print(printArray)
    }
    
    

当执行

combination(t: [1,2,3])

在控制台打印出来的就是全组合。

PS: 一般我们用不到‘空’这个结果，即 000 对应的结果，那么我们可以将combination方法中的for循环改成从1开始