基于序列的排列枚举的变体

Question

这是对this thread的一个跟进，主要问题是遍历数组的所有排列，给出["a","b","c"]，使用迭代器获得["bca","acb".. etc]。

感谢Martin R的见解，以及他在另一个thread中的输入，我想出了另一种可能的解决方案，使用迭代器进行“基于序列的排列枚举”问题。问题是我不确定我是否有所有的排列，尽管有充分的迹象表明他们都在那里。该算法保证提供n！排列最多，没有重复。

这种方法背后的想法如下，比如有一个a=["a","b","c"...]大小的n数组。列出所有排列可以被视为从包中挑选元素：

■
■
■
■       ■  
■       ■  ■
■ ...   ■  ■  ■

0 ...  n-3 n-2 n-1

因此算法采用初始数组，并删除一行，递归传递，直到没有行为止。此时，如果可以找到迭代器，则可以独立地处理所有单独的排列。迭代器隐藏在下面的FactorialSequence中，其中一个方法next()允许从相邻点移动。

public struct FactorialSequence : Sequence, IteratorProtocol {

    private var current: [Int]

    public init(size:Int) {
        self.current = Array(repeating: 0, count: size)
    }

    public mutating func next() -> [Int]? {
        return self.__next();
    }

    private mutating func __next() -> [Int]? {
        var next = current
        defer {
            current = next;
        }

        for i in self.current.indices.reversed() {
            if next[i] < current.count - i - 1  {
                next[i] += 1
                return next;
            }
            next[i] = 0
        }
        return nil
    }
}

func permute(seq:[String],at:[Int]) -> String? {
    if seq.count > 0 {
        var ss = seq;
        let uu = seq[at.first!]
        var cc = at;
        _ = ss.remove(at: cc.first!)
        _ = cc.remove(at: 0);
        return uu + (permute(seq:ss,at:cc) ?? "")
    }
    return nil ;
}

调用permute()函数传递从FactorialSequence计算的迭代器（数组）：

var fs = FactorialSequence(size: 3)
print("\(fs.current):\(permute(seq:["a","b","c"], at: fs.current)!)")

while let uu = fs.next() {
    print("\(uu):\(permute(seq:["a","b","c"], at: uu)!)")
}

并给出（以展平字符串格式）：

   [-0.000][-0.000][171]    [0, 0, 0]:abc
   [0.0009][0.0009][174]    [0, 1, 0]:acb
   [0.0016][0.0007][174]    [1, 0, 0]:bac
   [0.0024][0.0008][174]    [1, 1, 0]:bca
   [0.0032][0.0008][174]    [2, 0, 0]:cab
   [0.0040][0.0008][174]    [2, 1, 0]:cba

关于'无重复'的注释：由于使用数组（迭代器）访问排列，如果两个迭代器相差一个元素，则它们指向两个不同的排列。虽然有点薄，但我认为这是没有重复的论据。

剩下的唯一问题是“他们都在那里吗？”。可以说有n！不同的数组指向给定的排列，但我不太确定该论证的有效性，因为它来自'绘图'......指针欢迎。

我没有彻底擦洗SO以检查这是否已经以这种方式或以类似的方式制定（尽管原始线程中的链接使用其他方法）。如果有，请道歉。

Answer 1

对于给定大小的N，FactorialSequence产生所有阵列的序列

[ i.0, i.1, ..., i.(N-1) ]

这样的

0 <= i.0 < N, 0 <= i.1 < N-1, ..., 0 <= i.(N-1) < 1

这正是

N * (N-1) * ... * 1 = N!

元素。然后permute()函数从给定数组中使用i.0元素选择具有索引N的元素，然后从剩余的i.1元素中选择具有N-1的元素，依此类推。

所以是的，这确实产生了阵列的所有可能的排列。

但是，代码可以简化一点。首先，FactorialSequence不返回初始数组[ 0, ..., 0 ]，对应于身份置换。另外，单独的__next()方法似乎是不必要的。

如果我们将代码更改为

public struct FactorialSequence : Sequence, IteratorProtocol {

    private var current: [Int]
    private var firstIteration = true

    public init(size:Int) {
        self.current = Array(repeating: 0, count: size)
    }

    public mutating func next() -> [Int]? {
        if firstIteration {
            firstIteration = false
            return current
        }

        for i in self.current.indices.reversed() {
            if current[i] < current.count - i - 1  {
                current[i] += 1
                return current;
            }
            current[i] = 0
        }
        return nil
    }
}

然后返回所有排列（包括初始标识），并且不再需要defer语句。

permute()函数可以略微简化，并且通用：

func permute<E>(array: [E], at: [Int]) -> [E] {
    if at.isEmpty { return [] }
    var at = at
    var array = array
    let firstIndex = at.remove(at: 0)
    let firstElement = array.remove(at: firstIndex)
    return [firstElement] + permute(array: array, at: at)
}

现在

let array = ["a", "b", "c"]
let fs = FactorialSequence(size: 3)
for p in fs {
    print(permute(array: array, at: p).joined())
}

产生预期的输出。

但请注意，permute()会产生大量的中间数组，因此我认为它的效率低于您引用的其他方法。

另一种方法是将拾取的元素交换到新的位置，这样可以避免递归和临时数组：

func permute<E>(array: [E], at: [Int]) -> [E] {
    var result = array
    for (i, j) in at.enumerated() {
        result.swapAt(i, i + j)
    }
    return result
}

（但它以不同的顺序产生排列。）