プレゼント交換に適したシンプルなカードベース置換生成

摘要

n 人のプレーヤーがいて，プレゼント交換を行いたい場面を考える．すなわち，不動点を持たない置換をランダムに生成したいとする．物理的なカード組を用いると，そのような置換生成ができることが知られている．例えば，2016 年にIbaraki とManabe は，巡回シャッフル等を用いる置換生成プロトコルを提案している．本稿では，Ibaraki とManabe のプロトコルは不動点を持たない置換を一様ランダムに生成するわけではなく，不動点を持たない長さn のサイクルを一様ランダムに出力すること，及びプレゼント交換の実用上はこの置換生成で問題がないことを指摘するとともに，彼らのプロトコルを改良し，より少ないシャッフル回数で同じ機能をシンプルに実現できることを示す．