<commit_before>//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//

/// A collection wrapper that generates combinations of a base collection.
public struct Combinations<Base: Collection> {
  /// The collection to iterate over for combinations.
  public let base: Base
  
  @usableFromInline
  internal var k: Int
  
  @usableFromInline
  internal init(_ base: Base, k: Int) {
    self.base = base
    self.k = base.count < k ? -1 : k
  }

  @inlinable
  public var count: Int {
    func binomial(n: Int, k: Int) -> Int {
      switch k {
      case n, 0: return 1
      case n...: return 0
      case (n / 2 + 1)...: return binomial(n: n, k: n - k)
      default: return n * binomial(n: n - 1, k: k - 1) / k
      }
    }
    
    return k >= 0
      ? binomial(n: base.count, k: k)
      : 0
  }
}

extension Combinations: Sequence {
  /// The iterator for a `Combinations` instance.
  public struct Iterator: IteratorProtocol {
    @usableFromInline
    internal let base: Base
    
    @usableFromInline
    internal var indexes: [Base.Index]
    
    @usableFromInline
    internal var finished: Bool
    
    internal init(_ combinations: Combinations) {
      self.base = combinations.base
      self.finished = combinations.k < 0
      self.indexes = combinations.k < 0
        ? []
        : Array(combinations.base.indices.prefix(combinations.k))
    }
    
    /// Advances the current indices to the next set of combinations. If
    /// `indexes.count == 3` and `base.count == 5`, the indices advance like
    /// this:
    ///
    ///     [0, 1, 2]
    ///     [0, 1, 3]
    ///     [0, 1, 4] *
    ///     // * `base.endIndex` reached in `indexes.last`
    ///     // Advance penultimate index and propagate that change
    ///     [0, 2, 3]
    ///     [0, 2, 4] *
    ///     [0, 3, 4] *
    ///     [1, 2, 3]
    ///     [1, 2, 4] *
    ///     [1, 3, 4] *
    ///     [2, 3, 4] *
    ///     // Can't advance without needing to go past `base.endIndex`,
    ///     // so the iteration is finished.
    @usableFromInline
    internal mutating func advance() {
      guard !indexes.isEmpty else {
        // Initial state for combinations of 0 elements is an empty array with
        // `finished == false`. Even though no indexes are involved, advancing
        // from that state means we are finished with iterating.
        finished = true
        return
      }
    
      let i = indexes.count - 1
      base.formIndex(after: &indexes[i])
      if indexes[i] != base.endIndex { return }

      var j = i
      while indexes[i] == base.endIndex {
        j -= 1
        guard j >= 0 else {
          // Finished iterating over combinations
          finished = true
          return
        }
        
        base.formIndex(after: &indexes[j])
        for k in indexes.indices[(j + 1)...] {
          indexes[k] = base.index(after: indexes[k - 1])
          if indexes[k] == base.endIndex {
            break
          }
        }
      }
    }
    
    @inlinable
    public mutating func next() -> [Base.Element]? {
      if finished { return nil }
      defer { advance() }
      return indexes.map { i in base[i] }
    }
  }
  
  public func makeIterator() -> Iterator {
    Iterator(self)
  }
}

extension Combinations: LazySequenceProtocol where Base: LazySequenceProtocol {}
extension Combinations: Equatable where Base: Equatable {}
extension Combinations: Hashable where Base: Hashable {}

//===----------------------------------------------------------------------===//
// combinations(count:)
//===----------------------------------------------------------------------===//

extension Collection {
  /// Returns a collection of combinations of this collection's elements, with
  /// each combination having the specificed number of elements.
  ///
  /// This example prints the different combinations of three from an array of
  /// four colors:
  ///
  ///     let colors = ["fuchsia", "cyan", "mauve", "magenta"]
  ///     for combo in colors.combinations(ofCount: 3) {
  ///         print(combo.joined(separator: ", "))
  ///     }
  ///     // fuchsia, cyan, mauve
  ///     // fuchsia, cyan, magenta
  ///     // fuchsia, mauve, magenta<commit_msg>Fix typo<commit_after>//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//

/// A collection wrapper that generates combinations of a base collection.
public struct Combinations<Base: Collection> {
  /// The collection to iterate over for combinations.
  public let base: Base
  
  @usableFromInline
  internal var k: Int
  
  @usableFromInline
  internal init(_ base: Base, k: Int) {
    self.base = base
    self.k = base.count < k ? -1 : k
  }

  @inlinable
  public var count: Int {
    func binomial(n: Int, k: Int) -> Int {
      switch k {
      case n, 0: return 1
      case n...: return 0
      case (n / 2 + 1)...: return binomial(n: n, k: n - k)
      default: return n * binomial(n: n - 1, k: k - 1) / k
      }
    }
    
    return k >= 0
      ? binomial(n: base.count, k: k)
      : 0
  }
}

extension Combinations: Sequence {
  /// The iterator for a `Combinations` instance.
  public struct Iterator: IteratorProtocol {
    @usableFromInline
    internal let base: Base
    
    @usableFromInline
    internal var indexes: [Base.Index]
    
    @usableFromInline
    internal var finished: Bool
    
    internal init(_ combinations: Combinations) {
      self.base = combinations.base
      self.finished = combinations.k < 0
      self.indexes = combinations.k < 0
        ? []
        : Array(combinations.base.indices.prefix(combinations.k))
    }
    
    /// Advances the current indices to the next set of combinations. If
    /// `indexes.count == 3` and `base.count == 5`, the indices advance like
    /// this:
    ///
    ///     [0, 1, 2]
    ///     [0, 1, 3]
    ///     [0, 1, 4] *
    ///     // * `base.endIndex` reached in `indexes.last`
    ///     // Advance penultimate index and propagate that change
    ///     [0, 2, 3]
    ///     [0, 2, 4] *
    ///     [0, 3, 4] *
    ///     [1, 2, 3]
    ///     [1, 2, 4] *
    ///     [1, 3, 4] *
    ///     [2, 3, 4] *
    ///     // Can't advance without needing to go past `base.endIndex`,
    ///     // so the iteration is finished.
    @usableFromInline
    internal mutating func advance() {
      guard !indexes.isEmpty else {
        // Initial state for combinations of 0 elements is an empty array with
        // `finished == false`. Even though no indexes are involved, advancing
        // from that state means we are finished with iterating.
        finished = true
        return
      }
    
      let i = indexes.count - 1
      base.formIndex(after: &indexes[i])
      if indexes[i] != base.endIndex { return }

      var j = i
      while indexes[i] == base.endIndex {
        j -= 1
        guard j >= 0 else {
          // Finished iterating over combinations
          finished = true
          return
        }
        
        base.formIndex(after: &indexes[j])
        for k in indexes.indices[(j + 1)...] {
          indexes[k] = base.index(after: indexes[k - 1])
          if indexes[k] == base.endIndex {
            break
          }
        }
      }
    }
    
    @inlinable
    public mutating func next() -> [Base.Element]? {
      if finished { return nil }
      defer { advance() }
      return indexes.map { i in base[i] }
    }
  }
  
  public func makeIterator() -> Iterator {
    Iterator(self)
  }
}

extension Combinations: LazySequenceProtocol where Base: LazySequenceProtocol {}
extension Combinations: Equatable where Base: Equatable {}
extension Combinations: Hashable where Base: Hashable {}

//===----------------------------------------------------------------------===//
// combinations(count:)
//===----------------------------------------------------------------------===//

extension Collection {
  /// Returns a collection of combinations of this collection's elements, with
  /// each combination having the specified number of elements.
  ///
  /// This example prints the different combinations of three from an array of
  /// four colors:
  ///
  ///     let colors = ["fuchsia", "cyan", "mauve", "magenta"]
  ///     for combo in colors.combinations(ofCount: 3) {
  ///         print(combo.joined(separator: ", "))
  ///     }
  ///     // fuchsia, cyan, mauve
  ///     // fuchsia, cyan, magenta
  ///     // fuchsia, mauve, magenta
{'fraction_non_alphanumeric': 0.18468271334792122, 'fraction_numerical': 0.012472647702407002, 'mean_word_length': 1.6057582668187, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 15, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2216452', 'n_tokens_mistral': 2760, 'n_tokens_neox': 2579, 'n_words': 856}