Integer Partition - 自然数の分割

readme.md

Fork of dland/Integer-Partition

IntegerPartition.rb

module IntegerPartition
  def zs1
    n = self
    fail 'positive integer only' if n <= 0

    Enumerator.new do |yielder|
      yielder << [n]
      x = [1] * n
      x[0] = n
      m = 0
      h = 0

      while (x[0] != 1)
        if (x[h] == 2)
          m += 1
          x[h] = 1
          h -= 1
        else
          r = x[h] - 1
          x[h] = r

          t = m - h + 1
          while (t >= r)
            h += 1
            x[h] = r
            t -= r
          end
          m = h + (t != 0 ? 1 : 0)
          if t > 1
            h += 1
            x[h] = t
          end
        end
        yielder << x.first(m + 1)
      end
    end
  end

  def zs2
    n = self
    fail 'positive integer only' if n <= 0

    Enumerator.new do |yielder|
      x = [1] * (n + 1)
      yielder << x[1, n]

      x[0] = -1
      x[1] = 2
      h = 1
      m = n - 1
      yielder << x[1, m]

      while x[1] != n
        if m - h > 1
          h += 1
          x[h] = 2
          m -= 1
        else
          j = m - 2;
          while x[j] == x[m-1]
            x[j] = 1
            j -= 1
          end
          h = j + 1
          x[h] = x[m-1] + 1
          r = x[m] + x[m - 1] * (m - h - 1)
          x[m] = 1
          if m - h > 1
              x[m-1] = 1
          end
          m = h + r - 1
        end
        yielder << x[1, m]
      end
    end
  end
end

class Integer
  include IntegerPartition
  alias_method :partition, :zs1
end

usage.md

# 整数 4 の分割
p 4.partition.to_a
# => [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]

# 8の分割のなかで「奇数のみを成分とする」もの
p 8.partition.select { |part| part.all?(&:odd?) }
# => [[7, 1], [5, 3], [5, 1, 1, 1], [3, 3, 1, 1], [3, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1]]

# 8の分割のなかで、「成分が全て異なる」もの
p 8.partition.select { |part| part == part.uniq }
# => [[8], [7, 1], [6, 2], [5, 3], [5, 2, 1], [4, 3, 1]]

via. 自然数の分割 - Wikipedia