test/collection/unique_permutation_test.cr

• View this file on GitHub
• Last update: 2022-04-10 10:27:41+09:00
• Problem: https://yukicoder.me/problems/no/170

Depends on

• src/collection/unique_permutation.cr

Code

# verification-helper: PROBLEM https://yukicoder.me/problems/no/170
require "../../src/collection/unique_permutation"
s = read_line.chars.sort!

ans1 = -1
s.each_unique_permutation { ans1 += 1 }

ans2 = s.each_unique_permutation.count { true } - 1

ans3 = s.unique_permutations.size - 1

raise "" unless ans1 == ans2 == ans3

puts ans1

# verification-helper: PROBLEM https://yukicoder.me/problems/no/170
# require "../../src/collection/unique_permutation"
class Array(T)
  def next_permutation! : Bool
    i = (1...size).reverse_each.find { |i| self[i - 1] < self[i] } || return false
    j = (0...size).reverse_each.find { |j| self[i - 1] < self[j] }.not_nil!
    swap(i - 1, j)
    Slice.new(to_unsafe + i, size - i).reverse!
    true
  end

  def next_permutation? : Array(T)?
    arr = dup
    arr.next_permutation! ? arr : nil
  end

  def each_unique_permutation(reuse : Bool = false, &block) : Nil
    pool = dup
    loop do
      yield reuse ? pool : pool.dup
      break unless pool.next_permutation!
    end
  end

  def each_unique_permutation(reuse : Bool = false)
    UniquePermutationIterator.new(clone, reuse)
  end

  def unique_permutations : Array(Array(T))
    permutations = [] of Array(T)
    each_unique_permutation { |perm| permutations << perm.dup }
    permutations
  end

  private class UniquePermutationIterator(T)
    include Iterator(T)

    @pool : T

    def initialize(a : T, @reuse : Bool)
      @pool = a.dup
      @first = true
    end

    def next
      if @first
        @first = false
        @reuse ? @pool : @pool.dup
      elsif @pool.next_permutation!
        @reuse ? @pool : @pool.dup
      else
        stop
      end
    end
  end
end

s = read_line.chars.sort!

ans1 = -1
s.each_unique_permutation { ans1 += 1 }

ans2 = s.each_unique_permutation.count { true } - 1

ans3 = s.unique_permutations.size - 1

raise "" unless ans1 == ans2 == ans3

puts ans1

Back to top page