Вариант последовательного перечисления перестановок

Question

Это продолжение этого потока , основная проблема которого заключалась в том, чтобы перебрать все перестановки массива, которым дано ["a","b","c"], получить ["bca","acb".. etc], используя итератор.

Благодаря выводам Мартина R , а также его материалам в другом потоке я придумал другое возможное решение проблемы «Перечисление перестановок на основе последовательности» с использованием итераторы. Проблема в том, что я не уверен, что у меня есть все перестановки, хотя есть хорошие признаки того, что они все есть. Алгоритм гарантированно предоставит 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() производит много промежуточных массивов, поэтому я предполагаю , что это будет менее эффективным, чем другие методы что вы ссылались.

Альтернативой будет swap выбранный элемент к его новому место, это позволяет избежать рекурсии и временных массивов:

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

(хотя и производит перестановки в другом порядке.)