「ディップ Advent Calendar 2024」24日目の記事です！🎄

はじめに

普段休みの日はあまり外に出ず家時間を満喫しているのですが、この時期は外に出ないともったいない気持ちになってきます

完全に余談ですが、先日とあるチャペルでクリスマスイベントのゴスペルコンサートがやってたので行ってみました
初めての経験でしたが、なんかすごく感動しました(語彙力)

自分も何かクリスマスっぽい記事書きたいなー。クリスマスといえばプレゼントよなぁ。
ということで、順位投票アルゴリズムを組んでプレゼント(自分へのご褒美)選びをしたいと思います！！！

やりたいこと

順位投票アルゴリズムである「Ranked Pairs」(Wiki) をプレゼント選びの意思決定に使用できるようにする
↑ に必要なやり取りはターミナルから標準入出力で行う

これでいきましょう！決定！

順位投票アルゴリズムは「CS50」からヒントをいただいて実装していきます

CS50とは？

ここで少し、今回の実装に必要な背景を説明します

CS50とは、コンピュータサイエンスに関するハーバード大学のエントリーレベルのコースで、edX.org(世界中の大学や機関が提供するオンライン学習プラットフォーム)で誰でも無償で受講できます
なお、履修証明書の取得は有料です

cs50.jpで日本語化もされており、今回はそのカリキュラムから第3週目のプログラミング課題である「Tideman」を実装要件の参考にさせていただきました！

(個人的には私が学生時代プログラミングに向き合い、ハマったきっかけでもあり、とても感謝しているカリキュラムです😌)

「Tideman」の要件

しっかり説明すると多分これだけで記事になってしまうので、興味ある方向けに課題ページを載せておきます

これ以上わかりやすい説明はない！かつ読み物としておもしろいと思います

https://cs50.jp/x/2021/week3/problem-set/tideman/ (当時私がやった2021年のもの)

概要をまとめると、

選挙で勝者を決めるための単純なアルゴリズムである「多数決」には欠点がある
- 候補者が同票となった場合、引き分けとなってしまうこと
- さらに別の潜在的な欠点として、第一候補しか当選結果に寄与できていないこと
Nicolaus Tidemanが提唱した「Ranked Pairs」では、複数の候補者に順位付け投票することができる
これにより候補者が同票となった場合でも勝者が出る可能性が上がる。また、「コンドルセ勝者」(候補者同士の各ペアの直接対決で最も強い候補者)を決めることができる

多分こんなところです

あれ、そういえば実際の選挙では使われてるんだっけ？とか、今回やりたいことにもっと適切なアルゴリズムはあるかな？とか浮かんできましたが、まぁ細かいことは置いといてやっていきます

実装の概要

一般的に、Tideman方式は、候補Aから候補Bへの矢印 (エッジ) が、候補Aが候補Bに対して直接対戦で勝つことを示す、候補の「グラフ」を構築することによって機能します。
ただし、矢印を描いてみると、コンドルセ勝者がいない可能性があります。
これを処理するには、Tidemanアルゴリズムでは、候補者のグラフにサイクルが作成されないように注意する必要があります。

先ほどのCS50カリキュラムから引用しました

要するに、直接対戦で勝つことを示すグラフを矢印で表現し、直接対決の強さ順にグラフに矢印を追加していく、
(例：候補A vs 候補Bが 20 : 10 なら A → B のペアの「強さ」は勝者Aの得票数である20となる)
ただしじゃんけん(サイクル)にならないよう、サイクルとなってしまう場合はそのエッジ(矢印)の追加をスキップする処理が必要になるということです

全てのエッジの追加が完了したら、グラフの始点の候補者が勝者となります！

(下記図の数字は強さ順)

このRanked Pairsグラフをコードで表現すると大きく5つの段階があります

投票の入力処理
投票集計
ペアのソート
グラフのロック
勝者判定・出力

次の章で段階ごとに説明します！

ソースコード説明

CS50の実際の課題では、必要な構造体や作成すべき関数などが示されています
大まかな要件と流れは汲みますが、それ以外は思うまま自由に実装することにし、また、C言語ではなくGoを使用しました

後ほど文言等を今回やりたいことに寄せて変更しますが、一旦完全に選挙の投票を想定したCLI UIがこちらです

最終的なディレクトリ構造とmain.goは以下になります

ディレクトリ構造

.
├── build
│   ├── env
│   │   └── .env
│   └── Dockerfile
├── cmd
│   └── main.go
├── internal
│   ├── input
│   │   ├── config.go
│   │   ├── input.go
│   │   └── validate.go
│   ├── lock
│   │   ├── config.go
│   │   └── lock.go
│   ├── sort
│   │   └── sort.go
│   └── tally
│       ├── structs.go
│       └── tally.go
├── pkg
│   └── util
│       └── util.go
├── .gitignore
├── docker-compose.yml
├── go.mod
├── go.sum
├── Makefile
└── README.md

cmd/main.go

const (
    maxCandidates = 10
    maxVoters     = 10
)
    
func main() {
    // 1. コマンドライン引数から候補者を入力
    candidates := os.Args[1:]
    candidateCount := len(candidates)
    if candidateCount < 2 {
        fmt.Println("Usage: make run-app <candidate1> <candidate2> ...\nNote: You need at least 2 candidates to run the election.")
        return
    }
    if candidateCount > maxCandidates {
        fmt.Printf("Usage: make run-app <candidate1> <candidate2> ...\nNote: The number of candidates cannot exceed %d.\n", maxCandidates)
        return
    }

    // 2. ターミナルから投票を入力
    ic := input.NewConfig(
        maxVoters,
        candidateCount,
        candidates,
    )
    // 2-1. 投票者数を入力
    voterCount := ic.GetNumberOfVoters()
    // 2-2. 候補者の順位付けを入力
    votes := ic.GetVotes(voterCount)
    // 2-3. 投票内容を出力
    fmt.Println("Votes:")
    for voter, ranks := range votes {
        fmt.Printf("  Voter: %s, Ranks: %v\n", voter, ranks)
    }
    fmt.Println()

    // 3. 投票結果を集計
    // 3-1. 全てのペアの勝利数を格納するマップを一時的に作成し、初期化
    pairWins := tally.InitializePairWins(candidates)
    // 3-2. votesからpairWinsを加算
    pairWins = tally.TallyPairWins(votes, pairWins)
    // 3-3. Pairのリストを作成
    pairs := tally.FilterWinningPairs(pairWins)

    // 4. ペアのソート
    strengths := map[string][]int{} // ソート時、勝者判定時の処理に使用
    for _, pair := range pairs {
        strengths[pair.Winner] = append(strengths[pair.Winner], pair.Strength)
    }
    maxStrengths := util.GenerateTotalValues(strengths)
    pairs = sort.SortPairs(pairs, maxStrengths)

    // 5. グラフのロック
    incomingEdges := map[int]int{} // 始点は自身に向くエッジの数が0
    for i := 0; i < candidateCount; i++ {
        incomingEdges[i] = 0
    }
    nameToIndex, indexToName := util.NewStringIndexBiMap(candidates)

    ufc := lock.NewUnionFindConfig(candidateCount)
    for _, pair := range pairs {
        winnerIndex, loserIndex := nameToIndex[pair.Winner], nameToIndex[pair.Loser]
        winnerRoot := ufc.Find(winnerIndex)
        loserRoot := ufc.Find(loserIndex)

        // サイクル(無向グラフ)が発生しない かつ 始点が無くならない場合のみエッジをロック
        if ufc.Union(winnerRoot, loserRoot, loserIndex, incomingEdges) {
            incomingEdges[loserIndex]++
        }
    }

    // 6. 勝者を出力
    maxStrengthScore := util.FindMaxSum(strengths)
    for candidateIndex, count := range incomingEdges {
        candidate := indexToName[candidateIndex]
        // 自身に向いているエッジがなく、強さの合計値が最大の候補者
        if count == 0 && maxStrengths[candidate] == maxStrengthScore {
            fmt.Printf("🏆 The winner: %s 🎉🎉🎉\n", candidate)
            fmt.Println()
            break
        }
    }
}

いろいろ凝ってたら結構コード量が多くなってしまったため、main.go以外については必要に応じて載せます！

投票の入力処理

// 1. コマンドライン引数から候補者を入力
candidates := os.Args[1:]
candidateCount := len(candidates)
if candidateCount < 2 {
	fmt.Println("Usage: make run-app <candidate1> <candidate2> ...\nNote: You need at least 2 candidates to run the election.")
	return
}
if candidateCount > maxCandidates {
	fmt.Printf("Usage: make run-app <candidate1> <candidate2> ...\nNote: The number of candidates cannot exceed %d.\n", maxCandidates)
	return
}

// 2. ターミナルから投票を入力
ic := input.NewConfig(
	maxVoters,
	candidateCount,
	candidates,
)
// 2-1. 投票者数を入力
voterCount := ic.GetNumberOfVoters()
// 2-2. 候補者の順位付けを入力
votes := ic.GetVotes(voterCount)
// 2-3. 投票内容を出力
fmt.Println("Votes:")
for voter, ranks := range votes {
	fmt.Printf("  Voter: %s, Ranks: %v\n", voter, ranks)
}
fmt.Println()

% make run-app ARGS="anpan dora kureshin”のような形でコマンドライン引数から候補者を受け取る
投票者数を入力し、その分投票を受け取るようにループを回す
- 型違いや存在しない候補者、既に投票した候補者の重複などバリデーションかけて、その段階から再度入力を求めるようにする
投票内容(投票者ごとの順位)を出力する

投票集計

// 3. 投票結果を集計
// 3-1. 全てのペアの勝利数を格納するマップを一時的に作成し、初期化
pairWins := tally.InitializePairWins(candidates)
// 3-2. votesからpairWinsを加算
pairWins = tally.TallyPairWins(votes, pairWins)
// 3-3. Pairのリストを作成
pairs := tally.FilterWinningPairs(pairWins)

候補者の全組み合わせの勝利数を格納するマップ(map[string]map[string]int)を作成し、投票を反映
- 例：pairWins[dora][anpan]は2となる
その後、勝利ペアのみのリストを作成する
- 例：pairWins[dora][anpan]は2、pairWins[anpan][dora]は1なので[dora][anpan]のみをフィルタリング

ペアのソート

// 4. ペアのソート
strengths := map[string][]int{} // ソート時、勝者判定時の処理に使用
for _, pair := range pairs {
	strengths[pair.Winner] = append(strengths[pair.Winner], pair.Strength)
}
maxStrengths := util.GenerateTotalValues(strengths)
pairs = sort.SortPairs(pairs, maxStrengths)

internal/sort/sort.go

func SortPairs(pairs []tally.Pair, maxStrengths map[string]int) []tally.Pair {
	// pairsを段階的にソートする
	sort.SliceStable(pairs, func(i, j int) bool {
		// 勝利数で降順ソート
		if pairs[i].Strength != pairs[j].Strength {
			return pairs[i].Strength > pairs[j].Strength
		}

		// 勝利数が同じ場合、ペアの総勝利数で降順ソート
		totalStrengthI := maxStrengths[pairs[i].Winner] + maxStrengths[pairs[i].Loser]
		totalStrengthJ := maxStrengths[pairs[j].Winner] + maxStrengths[pairs[j].Loser]
		if totalStrengthI != totalStrengthJ {
			return totalStrengthI > totalStrengthJ
		}

		// 勝利数・総勝利数共に同じ場合、ランダム性を導入
		return rand.Intn(2) == 0
	})

	return pairs
}

候補者の勝利数リストを作成し、総勝利数を計算する(勝利数リストの合計値)
- 例：strengths[kureshin]は[2, 2]。maxStrengths[kureshin]は4
ペアを段階的にソートする。このソート結果がそのままロック試行に進むので重要
- ペアの強さで並び替え
- 同じ場合は、ペアを構成する各候補者の総勝利数で並び替え
- さらに同じ場合は、ランダムに並び替え
- ↑ についてペアの強さは全て2だが、ペアを構成する各候補者の総勝利数(上から6, 4, 2)順にソートされている

グラフのロック

Ranked Pairsでは通常、探索アルゴリズムに深さ優先探索(DFS)(参考)を使用するのが一般的みたいです

今回は他に適切な方法がないかなー(興味)と調べてみたところ、「Union-Find」というものが目につき、計算量(O(n^2)みたいなの)も全然違うようなので使ってみることにしました
(内容についての説明はここでは省略します🙏 詳しく知りたい方はAtCoder問題の説明スライドがとてもわかりやすかったのでそちらを参照ください！)

ただ、詳しく調べていて学んだのですがDFSは有向グラフのサイクル検出に向いているのに対し、Union-Findは無向グラフのサイクル検出に向いているアルゴリズムのようです

例えば、候補者A, B, Cに対し、3人の投票があったとします

Voter1: A > B > C
Voter2: A > B > C
Voter3: B > A > C

この場合 A → C と B → C は問題なく追加できますが、A → B については、無向グラフの場合(図右側)サイクル検出とみなされ追加することができません

しかし、せっかくなのでUnion-Findベースは変更せずに、図のような、この違いにより本来の想定と異なるロック処理結果となってしまうケースを防ぐためにごちゃごちゃやってみました
そのため、私が気付けていない穴がありそうな予感しかしませんが、まぁ楽しく実装できれば一旦ヨシ！としてます()

// 5. グラフのロック
incomingEdges := map[int]int{} // 始点は自身に向くエッジの数が0
for i := 0; i < candidateCount; i++ {
	incomingEdges[i] = 0
}
nameToIndex, indexToName := util.NewStringIndexBiMap(candidates)

ufc := lock.NewUnionFindConfig(candidateCount)
for _, pair := range pairs {
	winnerIndex, loserIndex := nameToIndex[pair.Winner], nameToIndex[pair.Loser]
	winnerRoot := ufc.Find(winnerIndex)
	loserRoot := ufc.Find(loserIndex)

	// サイクル(無向グラフ)が発生しない かつ 始点が無くならない場合のみエッジをロック
	if ufc.Union(winnerRoot, loserRoot, loserIndex, incomingEdges) {
		incomingEdges[loserIndex]++
	}
}

internal/lock/lock.go

// Find: ノードの親を探す
func (uf *UnionFindConfig) Find(x int) int {
    if uf.Parent[x] != x {
        uf.Parent[x] = uf.Find(uf.Parent[x]) // 経路圧縮で木を平坦化
    }
    return uf.Parent[x]
}

// Union: 2つのノードを結合する
func (uf *UnionFindConfig) Union(rootX, rootY, y int, incomingEdges map[int]int) bool {
    if rootX == rootY {
        // Ranked pairsアルゴリズムにおけるサイクル検出となるよう、仮にロックした場合の判定
        return canAddEdge(y, incomingEdges)
    }

    // ランクに基づいて木を結合
    if uf.Rank[rootX] > uf.Rank[rootY] {
        uf.Parent[rootY] = rootX
    } else if uf.Rank[rootX] < uf.Rank[rootY] {
        uf.Parent[rootX] = rootY
    } else {
        uf.Parent[rootY] = rootX
        uf.Rank[rootX]++
    }
    return true
}

// 仮にロックした場合始点がなくなることがないかをシミュレート
func canAddEdge(y int, incomingEdges map[int]int) bool {
    incomingEdges[y]++
    hasZeroIncoming := false

    for _, count := range incomingEdges {
        if count == 0 {
            hasZeroIncoming = true
            break
        }
    }
    incomingEdges[y]-- // シミュレーションを元に戻す

    return hasZeroIncoming
}

自身に向くエッジの数を管理するマップを作成し、初期化する
ソートされたペア順にサイクル検出し、問題ない場合はエッジを追加(incomingEdgesで敗者側の数値をインクリメント)する
- ざっくり、Union-Findに必要な実装
  - ペアの勝者・敗者の各親ノードを取得する
  - 取得した2つの親ノードが一緒のグループに属しているか(無向グラフのサイクル検出)判断する。判断結果を返却するとともに、違うグループに属していた場合はまとめる
  - 処理効率が上がる工夫として「経路圧縮」「ランク」を導入する
- 有向グラフのサイクル検出アルゴリズムと同様の処理結果となるよう、親ノードが一緒のグループに属していても、エッジを追加しても始点が無くならない場合は追加OKとする
  - incomingEdgesを使用し、自身に向くエッジの数が0の候補者がいるかチェックする

勝者判定・出力

// 6. 勝者を出力
maxStrengthScore := util.FindMaxSum(strengths)
for candidateIndex, count := range incomingEdges {
	candidate := indexToName[candidateIndex]
	// 自身に向いているエッジがなく、強さの合計値が最大の候補者
	if count == 0 && maxStrengths[candidate] == maxStrengthScore {
		fmt.Printf("🏆 The winner: %s 🎉🎉🎉\n", candidate)
		fmt.Println()
		break
	}
}

「自身に向いているエッジがない(グラフの始点) かつ個人の強さが最大の候補者」を勝者として出力する
- 条件に該当する候補が複数いるケースもあり、その場合最初に該当した候補を当選とする

完成っ！🎉

実際に使ってみた

楽しくなってきていろいろ凝ってしまい想定より時間がかかってしまいましたが、本来やりたかったことはプレゼント選びです(途中完全に忘れてた)

candidate = 欲しいもの、voter = 観点、 winner = 購入するものと再定義します

欲しいものは、うーん……キーボード、Switch 、ダウンジャケット、スニーカー、骨伝導イヤホンあたりでしょうか
観点は、「欲しい！」「必要度」「ちょうどいい価格」に加えて、「クリスマスぽい」の4つとし、ちょうどいい価格は15,000くらいを想定します！

それっぽくなるよう文言を変更して、実行！！！

ということで、ADRERのダウンジャケット買いました、嬉しい😊
普段あまり買い物しないので、せっかく作ったし、が免罪符となりいい買い物ができました(笑)

おわりに

今年ももう残すところ1週間ほどですね。みなさんも理由をこじつけて、1年頑張った自分へのご褒美を買ってみてはいかがでしょうか！

ちなみに、ディップ Advent Calendar 2024 の前日の記事はこちらです！
FlutterやGoを触ってみて楽しかったことなどを書かれていて、個人的にはFlutter学んでみたくなりました😆

最後まで読んでいただいてありがとうございました！！

参考