ピーマンとハトと数学を 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 が分かりやすかった。