Variant on Sequence-Based enumeration of permutations

Question

This is a follow up on this thread, which main issue was to iterate over all permutations of an array, that is given ["a","b","c"], obtain ["bca","acb".. etc], using an iterator.

Thanks to Martin R's insights, and also his inputs in another thread, I came up with another possible solution for the 'Sequence-Based enumeration of permutations' problem using iterators. The issue is that I'm not sure I have all permutations although there are good indications they're all there. The algorithm is guaranteed to provide n! permutations at the most, with no duplicates.

The idea behind this approach is the following, say there's an array a=["a","b","c"...], of size n. Listing all permutations can be viewed as picking elements from bags:

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

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

So the algorithm takes the initial array, and removes a row, pass it recursively until there is no row left. At this point, if an iterator can be found, all individual permutations can be addressed independently. The iterator is hidden in FactorialSequence below, where a method next() allows to move from adjacents points.

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 ;
}

the permute() function is called passing the iterator (an array) calculated from 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)!)")
}

and gives (in flatten string format):

   [-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

Note on 'no duplicates': Since permutations are accessed using an array (the iterator), if two iterators differ by one elements, they point to two different permutations. Although a little thin, I take this as an argument for not having duplicates.

The only question remaining is 'are they all there?'. One could say that there are n! distinct arrays pointing at a given permutation, but I'm not too sure about the validity of that argument, since it comes from a 'drawing'... Pointers welcome.

I didn't thoroughly scrub SO to check if this had been already formulated this way or in a similar way (although links in the original thread use other approaches). Apologies if it did.

Answer 1

For a given size N the FactorialSequence produces a sequence of all arrays

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

such that

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

that are exactly

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

elements. The permute() function then picks the element with index i.0 from the given array with N elements, then the element with i.1 from the remaining N-1 elements, and so on.

So yes, this indeed produces all possible permutations of the array.

However, the code can be simplified a bit. First, FactorialSequence does not return the initial array [ 0, ..., 0 ], corresponding to the identity permutation. Also the separate __next() method seems unnecessary.

If we change the code to

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
    }
}

then all permutations are returned (including the initial identity), and the defer statement is no longer necessary.

The permute() function can be simplified slightly, and made generic:

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)
}

Now

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

produces the expected output.

Note however that permute() produces a lot of intermediate arrays, therefore I assume it to be less efficient than the other methods that you referenced.

An alternative would be to swap the picked element to its new place, this avoids recursion and temporary arrays:

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

(It produces the permutations in a different order, though.)