ピーマンとハトと数学を Go 言語で試す

はじめに

• 先日 NHK ETV で放送された "大人のピタゴラスイッチ" で "ピーマンとハトと数学" と題して "ピーマンの袋がどれもほぼ同じ重さになる仕組み" について解説があり面白かった。

ピーマンの袋がどれもほぼ同じ重さになる仕組み

• 12個のピーマンを "組み合わせ計量装置" の上に置くと 150g になる組み合わせを計算して排出する仕組みになっている。
• "組み合わせがない場合もあるのでは？" という問に対しては "98% の確率で組み合わせがあることが数学が保証している" ということ。
• "98%" の根拠が知りたかったが確率の計算がわからなかったので、実際に Go 言語で試して検証してみることにした。

解法

• とりあえずすぐ思いついたのは愚直に全組み合わせを試すパターン。
• togetter みてたら "subset sum" というキーワードが出てきたので検索。
• 部分和問題 というのを知ったのでまた検索して 動的計画法 での解法がわかったので Go 言語に移植してみた。

検証コード

• ピーマンの重さは適当に上限と下限を設定してランダムにしてみた。
• The Go Playground で実際に試せる。
  • Playground は現在時刻が固定でこのコードだと rand が正常に効いていないので何度か試すならローカル環境とかの方が良い。

package main

import (
    "fmt"
    "math/rand"
    "sort"
    "time"
)

type SubsetSumProblem struct {
    Nums   []int
    Target int
}

func NewSubsetSumProblem(nums []int, target int) *SubsetSumProblem {
    sort.Ints(nums)
    s := &SubsetSumProblem{Nums: nums, Target: target}
    return s
}

func (s *SubsetSumProblem) Solve() []int {
    work := make([]int, s.Target+1, s.Target+1)
    work[0] = 0
    for i := 1; i < len(work); i++ {
        work[i] = -1
    }
    for _, n := range s.Nums {
        for i := s.Target; i >= 0; i-- {
            if work[i] == -1 {
                continue
            }
            if i+n <= s.Target && work[i+n] == -1 {
                work[i+n] = n
            }
        }
        if work[s.Target] != -1 {
            break
        }
    }
    return s.ToResult(work)
}

func (s *SubsetSumProblem) ToResult(work []int) []int {
    result := []int{}
    if work[s.Target] != -1 {
        for s.Target > 0 {
            result = append(result, work[s.Target])
            s.Target -= work[s.Target]
        }
    }
    return result
}

// 試行回数
const sample = 10000

// 候補になるピーマンの個数
const length = 12

// 最小のピーマンの重さ
const lowest = 20

// 最大のピーマンの重さ
const highest = 60

// 合計の重さ
const target = 150

func main() {
    rand.Seed(time.Now().Unix())
    count := 0
    for i := 0; i < sample; i++ {
        p := make([]int, length, length)
        for i := range p {
            p[i] = rand.Intn(highest-lowest) + lowest
        }
        s := NewSubsetSumProblem(p, target)
        result := s.Solve()
        if len(result) == 0 {
            count++
        }
    }
    percent := 100.0 - (float32(count) / float32(sample) * 100.0)
    fmt.Printf("%d 回成功 (%.1f%%)", sample - count, percent)
}

結果

• 前記のコードで何度か施行してみると、だいたい 99.7% 前後の結果になった。
• 最大最小の重さを調整すると 98% にすることはできたので前提条件が抜けていると思われる。
• ピーマンは規格があるだろうし、正規乱数とかでランダムな重さを出したほうがいい気がするし。

おわりに

• 動的計画法がよくできていて感動した。アルゴリズムについてちゃんと勉強しようと思った。
• 部分和問題の動的計画法による解法の解説は こちら の PDF が分かりやすかった。