spec/collection/unique_permutation_spec.cr

• View this file on GitHub
• Last update: 2022-04-10 10:27:41+09:00

Depends on

• src/collection/unique_permutation.cr

Code

require "spec"
require "../../src/collection/unique_permutation"

describe Array do
  rng = Random.new(42)
  arrays = [
    [] of Int32,
    [0],
    [0, 0],
    (0...8).to_a,
  ] + Array.new(100) {
    Array.new(8) { rng.rand(3) }
  }

  it "#next_unique_permutation, #each_unique_permutation" do
    arrays.each do |a|
      perms = a.sort.permutations.uniq!.skip_while(&.!= a)

      b, i = a.dup, 0
      while i + 1 < perms.size
        b.next_permutation!.should be_true
        b.should eq perms[i += 1]
      end
      b.next_permutation!.should be_false
      b.should eq perms.last

      b, i = a.dup, 0
      while i + 1 < perms.size
        (b = b.next_permutation?.not_nil!).should eq perms[i += 1]
      end
      b.next_permutation?.should be_nil

      a.unique_permutations.should eq perms

      a.each_unique_permutation.to_a.should eq perms
      i = 0
      a.each_unique_permutation(true).each do |b|
        b.should eq perms[i]
        i += 1
      end

      i = 0
      a.each_unique_permutation do |b|
        b.should eq perms[i]
        i += 1
      end
      i = 0
      a.each_unique_permutation(reuse: true) do |b|
        b.should eq perms[i]
        i += 1
      end
    end
  end
end

require "spec"

# 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

describe Array do
  rng = Random.new(42)
  arrays = [
    [] of Int32,
    [0],
    [0, 0],
    (0...8).to_a,
  ] + Array.new(100) {
    Array.new(8) { rng.rand(3) }
  }

  it "#next_unique_permutation, #each_unique_permutation" do
    arrays.each do |a|
      perms = a.sort.permutations.uniq!.skip_while(&.!= a)

      b, i = a.dup, 0
      while i + 1 < perms.size
        b.next_permutation!.should be_true
        b.should eq perms[i += 1]
      end
      b.next_permutation!.should be_false
      b.should eq perms.last

      b, i = a.dup, 0
      while i + 1 < perms.size
        (b = b.next_permutation?.not_nil!).should eq perms[i += 1]
      end
      b.next_permutation?.should be_nil

      a.unique_permutations.should eq perms

      a.each_unique_permutation.to_a.should eq perms
      i = 0
      a.each_unique_permutation(true).each do |b|
        b.should eq perms[i]
        i += 1
      end

      i = 0
      a.each_unique_permutation do |b|
        b.should eq perms[i]
        i += 1
      end
      i = 0
      a.each_unique_permutation(reuse: true) do |b|
        b.should eq perms[i]
        i += 1
      end
    end
  end
end

Back to top page