CODEWITHSUNDEEP
stringrecursionpermutation
HarvP
HarvP

Reputation: 190

String Permutations of Different Lengths

I have been trying to wrap my head around something and can't seem to find an answer. I know how to get all the permutations of a string as it is fairly easy. What I want to try and do is get all the permutations of the string in different sizes. For example:

Given "ABCD" and a lower limit of 3 chars I would want to get back ABC, ABD, ACB, ACD, ADB, ADC, ... , ABCD, ACBD, ADBC, .. etc.

I'm not quite sure how to accomplish that. I have it in my head that it is something that could be very complicated or very simple. Any help pointing me in a direction is appreciated. Thanks.

Upvotes: 0

Views: 67

Answers (1)

user652038
user652038

Reputation:

If you've already got the full-length permutations, you can drop stuff off of the front or back, and insert the result into a set.

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

Upvotes: 0

Related Questions