以前、クラシックな「名前のリストを貼り付けて N 個の均等グループを作成する」ツールを作りたくなりました——先生やイベント主催者が一度は必要とする類のものです。想定では、Fisher-Yates シャッフルと Array.slice をループで組み合わせた程度で、1 時間程度の作業で済むと思っていました。

しかし実際に「クラスをランダムにグループ分けしてほしい」と言われたときに、ユーザーが本当に求めているものを考えてみました。彼らは「真のランダム」を望んでいるわけではなく、「喧嘩する 2 人が同じグループにならないように」「インターンを各テーブルに均等に配置」「3 人のチームリーダーをすべて異なるグループに入れる」といった制約を求めているのです。一度でも制約を追加すると、真のランダム性はむしろ敵になります。そこで最終的にリリースしたツールには、グループ分けロジックに Math.random() が一切含まれていません。これは「賢い」シャッフルを装った、決定論的でルール対応の配置アルゴリズムです。

貼り付けたリストのパースは思ったより厄介

グループ分けを行う前に、元のテキストエリアの内容を重複のない名前のクリーンなリストに変換する必要があります。ユーザーは Excel、Google ドキュメント、グループチャットなどから貼り付けるため、区切り文字は改行、カンマ、全角中国語のカンマ、セミコロン、または単なる空白文字になり得ます。

function parseInput() {
  const tokens = rawInput.value
    .split(/[\n,，;\s]+/g)
    .map((s) => s.trim())
    .filter(Boolean);

  // 同一入力セッション内の重複を除去
  const uniqueTokens = [...new Set(tokens)];

  for (const name of uniqueTokens) {
    if (peopleIndex.has(name)) continue; // 既に存在する場合はスキップ
    const id = newId();
    peopleIndex.set(name, id);
    peopleList.push({ id, name, tags: new Set() });
  }
}

Enter fullscreen mode Exit fullscreen mode

ここでは 2 回の重複除去が行われます。new Set(tokens) は現在の貼り付け内の重複をまとめ、peopleIndex（name -> id のマップ）は以前の貼り付けで既に解析済みの人物を再追加しないようにします。これにより、リストを段階的に追加しても人物が重複しません。注意点として、重複除去は完全一致で行われるため、偶然同じ名前「John」の 2 人が 1 つのエントリに統合されてしまいます。このツールでは、名前がそのまま人物の識別子となります。

シャッフルではなく、スコア付き配置ループ

順序をランダム化して分割する代わりに、アルゴリズムは「制約の強さ」で人物をソートし、最も制約の強い人から貪欲に配置します。

const peopleOrder = [...peopleList].sort((a, b) => {
  // 1. 優先タグを優先
  const pa = Array.from(a.tags).filter((id) => priorityTagIds.has(id)).length;
  const pb = Array.from(b.tags).filter((id) => priorityTagIds.has(id)).length;
  if (pb !== pa) return pb - pa;

  // 2. ルール数（ハード + ソフト）が多い人を先に配置
  const ta = totalRuleDegree(a.id);
  const tb = totalRuleDegree(b.id);
  if (tb !== ta) return tb - ta;

  // 3. 希少タグを先に（後で配置しにくい）
  const ra = a.tags.size === 0 ? Infinity : [...a.tags].reduce((s, id) => s + (tagFreq.get(id) || 0), 0);
  const rb = b.tags.size === 0 ? Infinity : [...b.tags].reduce((s, id) => s + (tagFreq.get(id) || 0), 0);
  return ra - rb;
});

Enter fullscreen mode Exit fullscreen mode

直感は、スーツケースに荷物を詰め込むときと同じです。扱いにくい形のものを先に配置し、残りのスペースを埋めやすいものを後回しにします。優先ルールのタグが付いている人や、3 つの「分離必須」ルールに縛られている人は、制約のない人より先に配置されます。

各人物について、pickBestGroupFor はすべてのグループをスコアリングし、最良のグループを選択します。仮配置を評価する方法は、実際に配置を行い、全ルールの違反を再計算して損害を読み取り、その後元に戻すというものです。

function deltaScoreIfPlace(pid, gid) {
  const g = groups.find((x) => x.id === gid);
  const snapshot = takeLightSnapshot();

  g.members.push(pid); // テスト用に一時配置

  const vlist = computeViolationsInternal();
  const hardViolations = vlist.filter((v) => v.type === "HARD");
  const softViolations = vlist.filter((v) => v.type === "SOFT");

  const score = hardViolations.length > 0 ? -Infinity : -softViolations.length * 10;

  applyLightSnapshot(snapshot); // 次のグループを試す前に復元
  return score;
}

Enter fullscreen mode Exit fullscreen mode

特定の配置が競合を引き起こすかどうかを段階的にチェックするのではなく、実際の状態を変更し、全ルールと全グループにわたる完全な違反スキャンを再実行して数を読み取り、スナップショット/復元ペアで元に戻します。この方法は理解しやすく、微妙な誤りを防ぎやすい一方で、候補グループ×人物ごとにルールセット全体を再スキャンする必要があります。30 人のクラス程度なら問題ありませんが、5,000 人のリストを貼り付ける用途には向きません。

人数が均等に割り切れない場合

n 人を k グループに分ける場合、基本サイズは Math.floor(n / k) で、余剰は n % k 人となります。この余剰の扱いはチェックボックス次第で、最初に想定していた動作とは異なる結果になります。

const baseCap = Math.floor(n / k);
const remainder = n % k;
const capacities = groups.map((_, i) =>
  allowPlusMinusOne.value ? baseCap : baseCap + (i < remainder ? 1 : 0),
);

Enter fullscreen mode Exit fullscreen mode

「±1 を許可」がオフの場合、余剰は決定論的に分配され、最初の remainder グループが 1 席余分に割り当てられ、それ以外は baseCap が厳密な上限となります。一方、「±1 を許可」がオンの場合、capacities 配列は計算されますが実質的に無視され、配置ループ内の容量チェックは capacities[gIndex] を参照せず、すべてのグループに対して avgCap + 1 のフラット上限が適用されます。

if (!allowPlusMinusOne.value) {
  if (g.members.length >= capacities[gIndex]) continue;
} else {
  if (g.members.length >= avgCap + 1) continue;
}

Enter fullscreen mode Exit fullscreen mode

したがって ±1 モードでは、誰が余剰席を得るかの事前計画はなく、人物の配置順が来た時点でまだ avgCap + 1 に達していないグループが自動的に選ばれます。通常はソート順のおかげでほぼ均等になりますが、それはループ順序の副作用であり、意図的に設計された分配ではありません。

知っておくべき制限事項

  • 同名衝突は実際に発生します。2 人の「Alex」を貼り付けると、2 人目は 2 人目の人物として扱われず、最初の人物のタグセットに統合されます。
  • ハード違反の「自動修正」は最適化処理ではなく、人物を各グループへ順に移動し、他の人物とのスワップを順に試み、すべてのハード違反が解消される最初の組み合わせで停止します。最善の修正ではなく、動作する修正を探します。
  • すべてはクライアントサイドで実行されるため（サーバーとの往復は一切ありません）、プライバシーには優れていますが、上記の違反再スキャン方式はサーバーではなくブラウザのシングルスレッド性能に依存します。
  • ソフトルールは文字通りソフトです。3 つの「分離推奨」ルールを破る配置でも、ゼロ違反が不可能であれば受け入れられ、どのソフトルールの組み合わせを犠牲にしたかは、違反リストを後から読まない限り表示されません。

このロジックを整理して、誰でも使える小さな無料ツールにしました。自分で制約スコアリングループを構築したくない場合はこちらをご利用ください：Smart Grouping Tool。登録不要、すべてブラウザ内で動作します。

他の言語でも利用可能