とりあえず解きたい

• 今、N個の要素からなる要素集合がある
• それぞれの要素はX個の要素からなっている。これを 、と表す
• 今、このN種類の要素のX個の要素をシャッフルしたい。完全にシャッフルするのでなく、一定の制約を入れてシャッフルすることを考える
• シャッフルに与える制約は次のような、内容からなるk個の制約である
  
  • 個々の条件は次の通り
    
    • の相互に共通要素を持たない空でないの部分集合が２つあり、それぞれ、とする
    • が与えられたときには、のX個の要素同士は固定し、のX個の要素同士も固定して、シャッフルする
• 与えられる条件は、k個のA、Bペアである。k通り別途、シャッフルするのは大変なので、相互に重なるシャッフル条件であったら、使いまわしたいとき、最も少ないシャッフル量にするには、どうしたらよいか、というのが問題である。
• 解はこう？
  
  • これは彩色問題(の変形)として解けそう
  • Aの要素とBの要素とは互いに隣接している
  • AとBとにくくられない(条件として登場しない)要素は隣接していないとみなしてよい
  • 条件はk個あって、隣接条件が累積していく
  • 全k条件が要素の隣接をすべて与えるので、その隣接要素同士を同じ色に塗らずに、なるべく少ない色で塗れたら、それが、解。と。
  • とすると、参考にするべきは
    
    • Cのソース(こちら)
    • 駆け足シリーズにもありそうこちら)
      
      • 駆け足で読む点彩色はこちら