时间戳

首页 > 解决方案 > 不同长度的字符串排列

string - 不同长度的字符串排列

问题描述

我一直在试图围绕某些事情思考，但似乎找不到答案。我知道如何获得字符串的所有排列，因为它相当容易。我想要尝试做的是获得不同大小的字符串的所有排列。例如：

给定“ABCD”和 3 个字符的下限，我想返回 ABC、ABD、ACB、ACD、ADB、ADC、...、ABCD、ACBD、ADBC 等。

我不太确定如何做到这一点。我的想法是，它可能非常复杂或非常简单。感谢任何为我指明方向的帮助。谢谢。

标签： stringrecursionpermutation

解决方案

如果你已经得到了全长排列，你可以从前面或后面放下东西，然后将结果插入到一个集合中。

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

推荐阅读