Струнные перестановки различной длины - PullRequest
Новая
       15

Струнные перестановки различной длины

0 голосов
/ 22 марта 2020

Я пытался обернуть голову вокруг чего-то и не могу найти ответ. Я знаю, как получить все перестановки строки, так как это довольно легко. То, что я хочу попробовать, это получить все перестановки строки в разных размерах. Например:

Учитывая "ABCD" и нижний предел в 3 символа, я хотел бы получить обратно AB C, ABD, ACB, ACD, ADB, AD C, ..., ABCD, ACBD, ADB C, .. et c.

Я не совсем уверен, как это сделать. У меня в голове есть мысль, что это может быть очень сложно или очень просто. Любая помощь, указывающая мне направление, приветствуется. Спасибо.

1 Ответ

0 голосов
/ 23 марта 2020

Если у вас уже есть перестановки во всю длину, вы можете сбросить материал с передней или задней части и вставить результат в набор. 

XCTAssertEqual(
  Permutations(["A", "B", "C"]).reduce( into: Set() ) { set, permutation in
    permutation.indices.forEach {
      set.insert( permutation.dropLast($0) )
    }
  },
  [ ["A", "B", "C"],
    ["A", "C", "B"],

    ["B", "C", "A"],
    ["B", "A", "C"],

    ["C", "A", "B"],
    ["C", "B", "A"],

    ["B", "C"],
    ["C", "B"],

    ["C", "A"],
    ["A", "C"],

    ["A", "B"],
    ["B", "A"],

    ["A"],
    ["B"],
    ["C"]
  ]
)

public struct Permutations<Sequence: Swift.Sequence>: Swift.Sequence, IteratorProtocol {
  public typealias Array = [Sequence.Element]

  private let array: Array
  private var iteration = 0

  public init(_ sequence: Sequence) {
    array = Array(sequence)
  }

  public mutating func next() -> Array? {
    guard iteration < array.count.factorial!
    else { return nil }

    defer { iteration += 1 }

    return array.indices.reduce(into: array) { permutation, index in
      let shift =
        iteration / (array.count - 1 - index).factorial!
        % (array.count - index)
      permutation.replaceSubrange(
        index...,
        with: permutation.dropFirst(index).shifted(by: shift)
      )
    }
  }
}

public extension Collection where SubSequence: RangeReplaceableCollection {
  func shifted(by shift: Int) -> SubSequence {
    let drops =
      shift > 0
      ? (shift, count - shift)
      : (count + shift, -shift)
    return dropFirst(drops.0) + dropLast(drops.1)
  }
}

public extension BinaryInteger where Stride: SignedInteger  {
  /// - Note: `nil` for negative numbers
  var factorial: Self? {
    switch self {
    case ..<0:
      return nil
    case 0...1:
      return 1
    default:
      return (2...self).reduce(1, *)
    }
  }
}
...