<commit_before>//
//  Permutation.swift
//  SwiftyMath
//
//  Created by <NAME> on 2018/03/12.
//  Copyright © 2018年 <NAME>. All rights reserved.
//

public struct Permutation<n: SizeType>: Multiplicative, MathSet, Hashable {
    public let length: Int
    private let table: [Int : Int]
    
    public init(length: Int, table: [Int : Int]) {
        assert(Set(table.keys) == Set(table.values))
        assert(table.keys.allSatisfy { i in (0 ..< length).contains(i) })
        
        self.length = length
        self.table = table.exclude{ (k, v) in k == v }
    }
    
    public init<S: Sequence>(length: Int, indices: S, fillRemaining: Bool = false) where S.Element == Int {
        if fillRemaining {
            let remain = Set(0 ..< length).subtracting(indices)
            self.init(length: length, indices: Array(indices) + remain.sorted(), fillRemaining: false)
        } else {
            let table = Dictionary(indices.enumerated().map{ ($0, $1) })
            self.init(length: length, table: table)
        }
    }
    
    public init(length: Int, indices: Int...)  {
        self.init(length: length, indices: indices)
    }
    
    public static func transposition(length: Int, indices: (Int, Int)) -> Self {
        let (i, j) = indices
        return .init(length: length, table: [i : j, j : i])
    }
    
    public static func cyclic(length: Int, indices: [Int]) -> Self {
        var d = [Int : Int]()
        let l = indices.count
        for (p, i) in indices.enumerated() {
            d[i] = indices[(p + 1) % l]
        }
        return .init(length: length, table: d)
    }
    
    public subscript(i: Int) -> Int {
        table[i] ?? i
    }
    
    public static func identity(length: Int) -> Self {
        .init(length: length, table: [:])
    }
    
    public var inverse: Self? {
        let inv = table.map{ (i, j) in (j, i)}
        return .init(length: length, table: Dictionary(inv))
    }
    
    // memo: the number of transpositions in it's decomposition.
    // the sign of a cyclic-perm of length l (l >= 2) is (-1)^{l - 1}
    public var signature: Int {
        cyclicDecomposition.multiply { I in (-1).pow( I.count - 1 ) }
    }
    
    public static func *(a: Self, b: Self) -> Self {
        assert(a.length == b.length)
        var d = a.table
        for i in b.table.keys {
            d[i] = a[b[i]]
        }
        return .init(length: a.length, table: d)
    }
    
    public static func ==(a: Self, b: Self) -> Bool {
        a.table == b.table
    }
    
    public func `as`<m>(_ type: Permutation<m>.Type) -> Permutation<m> {
        Permutation<m>(length: length, table: self.table)
    }
    <commit_msg>improve permutation.<commit_after>//
//  Permutation.swift
//  SwiftyMath
//
//  Created by <NAME> on 2018/03/12.
//  Copyright © 2018年 <NAME>. All rights reserved.
//

public struct Permutation<n: SizeType>: Multiplicative, MathSet, Hashable {
    public let length: Int
    public let table: [Int : Int]
    
    public init(length: Int, table: [Int : Int]) {
        assert(Set(table.keys) == Set(table.values))
        assert(table.keys.allSatisfy { i in (0 ..< length).contains(i) })
        
        self.length = length
        self.table = table.exclude{ (k, v) in k == v }
    }
    
    public init<S: Sequence>(length: Int, indices: S, fillRemaining: Bool = false) where S.Element == Int {
        if fillRemaining {
            let remain = Set(0 ..< length).subtracting(indices)
            self.init(length: length, indices: Array(indices) + remain.sorted(), fillRemaining: false)
        } else {
            let table = Dictionary(indices.enumerated().map{ ($0, $1) })
            self.init(length: length, table: table)
        }
    }
    
    public init(length: Int, indices: Int...)  {
        self.init(length: length, indices: indices)
    }
    
    public static func transposition(length: Int, indices: (Int, Int)) -> Self {
        let (i, j) = indices
        return .init(length: length, table: [i : j, j : i])
    }
    
    public static func cyclic(length: Int, indices: [Int]) -> Self {
        var d = [Int : Int]()
        let l = indices.count
        for (p, i) in indices.enumerated() {
            d[i] = indices[(p + 1) % l]
        }
        return .init(length: length, table: d)
    }
    
    @inlinable
    public subscript(i: Int) -> Int {
        table[i] ?? i
    }
    
    public static func identity(length: Int) -> Self {
        .init(length: length, table: [:])
    }
    
    public var inverse: Self? {
        .init(length: length, table: table.invert())
    }
    
    public var indices: [Int] {
        (0 ..< length).map{ self[$0] }
    }
    
    // memo: the number of transpositions in it's decomposition.
    // the sign of a cyclic-perm of length l (l >= 2) is (-1)^{l - 1}
    public var signature: Int {
        cyclicDecomposition.multiply { I in (-1).pow( I.count - 1 ) }
    }
    
    public func extended(_ n: Int) -> Permutation<anySize> {
        .init(length: length + n, indices: indices, fillRemaining: true)
    }

    public func shifted(_ n: Int) -> Permutation<anySize> {
        .init(length: length + n, table: table.mapPairs{ (i, j) in (i + n, j + n) } )
    }
    
    public static func *(a: Self, b: Self) -> Self {
        assert(a.length == b.length)
        return .init(length: a.length, table: b.table.mapValues{ a[$0] }.merging(a.table, overwrite: false))
    }
    
    public static func ==(a: Self, b: Self) -> Bool {
        a.table == b.table
    }
    
    public func `as`<m>(_ type: Permutation<m>.Type) -> Permutation<m> {
        Permutation<m>(length: length, table: self.table)
    }
    
{'fraction_non_alphanumeric': 0.14731277533039647, 'fraction_numerical': 0.00828193832599119, 'mean_word_length': 2.0369181380417336, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 39, 'https://': 0, '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': '3511248', 'n_tokens_mistral': 1898, 'n_tokens_neox': 1829, 'n_words': 534}