More than 3 years have passed since last update.

置換(順列)の列挙

Posted at 2022-01-29

はじめに

数学の世界で「順列」は「n個のものからk個を選び出して並べる」ことを指し、「置換」は「n個のものを並べる」ことを意味するそうです.
この意味において、この記事は「置換」のみを扱います.
タイトルには「置換(順列)」と書いていますが、これは単に「置換」とだけ書いても正規表現などによる文字列の一括置き換えなどが連想されるためです.
置換の列挙は再帰を用いたものばかり出てきますが、ループだけで書く方法を知ったのでメモをかねて記事にしました.
記事中で示すコードは C# で書いています.

また、個別のコード例には含めませんが、以下の関数の存在を仮定しています:

すべてのコード例で共通する関数

// a[i] と a[j] の値を交換する
private static void Swap(int[] a, int i, int j) {
  int t = a[i];
  a[i] = a[j];
  a[j] = t;
}

置換の全列挙

要素数 n = 3 の場合、{ 1, 2, 3 }, { 1, 3, 2 }, { 2, 1, 3 }, { 2, 3, 1 }, { 3, 1, 2 }, { 3, 2, 1 } の6通りの置換を生成する.
一般に、n 個の要素を並べ替える方法は n! = n * (n-1) * ... * 1 通りである.

ヒープのアルゴリズム

ヒープと言えば優先度付きキューの方が浮かんでしまうがそれとは違い、ヒープさんが考え出したのでヒープのアルゴリズムと呼ばれているそうだ.
Wikipediaに擬似コードがあるため、それを C# で書き換えたものを示す.

コード例

// ループ版の実装のみ示すが、再帰版は簡潔
public static List<int[]> Heap(int n) {
  // Initialise variables:
  int[] a = new int[n];// permutation array
  int[] c = new int[n];// これは再帰版でのループカウンターに相当する
  for (int j = 0; j < n; ++j) {
    a[j] = j + 1;// a[] = { 1, 2, ..., n } であるようにしている. しかしこのアルゴリズムはどんな配列を渡されても機能する.
    c[j] = 0;
  }
  List<int[]> result = new List<int[]>();// 結果を格納するリスト
  // Generate permutations:
  result.Add((int[]) a.Clone());
  int i = 0;// i は再帰版におけるスタックの深さに相当する
  while (i < n) {
    if (c[i] < i) {
      if ((i & 1) == 0) Swap(a, 0, i);
      else              Swap(a, c[i], i);
      result.Add((int[]) a.Clone());
      ++c[i];
      i = 0;
    } else {
      c[i] = 0;
      ++i;
    }
  }
  return result;
}

Steinhaus–Johnson–Trotter algorithm

Wikipedia のタイトルは Steinhaus–Johnson–Trotter algorithm なので章題にはこちらを採用した.
しかし、Steinhaus さんの名前を省いて Johnson–Trotter algorithm と呼んでいるサイトも度々見かけたので何が一般的なのかは不明.
YouTubeにある動画で n = 4 の場合の処理を完全にトレースしているものがあったため、それに従って実装した.
mobile の探し方(あるいは保持の仕方)については工夫の余地がありそうだが、思いつかないため単に線形探索で実装している.

簡単な説明

私の知識は前述の動画がすべてだが、ここに日本語の説明を示す:

前提:

すべての値は向きを持つ.
自分より小さい値を向いている(指している)ものを mobile component と呼ぶ. (長いので記事中では単に mobile とする)

手順:

値を昇順で並べる
すべての値は左(小さい方)を向いているものとする
mobile の内、最大のものを探す(見つからない場合は終了)
mobile とそれが指しているものを交換する
mobile より大きい値の向きを mobile の方に変更する

n = 4 の手順のすべてを以下に示す. (思ったよりも長いテーブルになってしまった)
「配列の状態と向き」の1行目は現時点における値の順序であり、2行目はそれぞれの値の向きを示す('<' は左向き、'>' は右向き).
「出力」の列が得られた置換であり、n! 個の結果が得られる.

配列の状態と向き	説明	出力
1 2 3 4 < < < <	初期状態	1 2 3 4
1 2 4 3 < < < <	mobile は 2, 3, 4. 最大の mobile は 4 であったからそれとそれが指している値(3)とを交換した.	1 2 4 3
1 2 4 3 < < < <	先ほどの mobile は配列内で最大の値だったので何もしない
1 4 2 3 < < < <	mobile は 2, 4. 最大の mobile は 4 であったからそれとそれが指している値(2)とを交換した.	1 4 2 3
1 4 2 3 < < < <	先ほどの mobile は配列内で最大の値だったので何もしない
4 1 2 3 < < < <	mobile は 4, 3. 最大の mobile は 4 であったからそれとそれが指している値(1)とを交換した.	4 1 2 3
4 1 2 3 < < < <	先ほどの mobile は配列内で最大の値だったので何もしない
4 1 3 2 < < < <	mobile は 2, 3. 最大の mobile は 3 であったからそれとそれが指している値(2)とを交換した.	4 1 3 2
4 1 3 2 > < < <	先ほどの mobile より大きいものが mobile の方を向くように書き換える
1 4 3 2 < > < <	mobile は 4, 3. 最大の mobile は 4 であったからそれとそれが指している値(1)とを交換した.	1 4 3 2
1 4 3 2 < > < <	先ほどの mobile は配列内で最大の値だったので何もしない
1 3 4 2 < < > <	mobile は 4. 最大の mobile は 4 であったからそれとそれが指している値(3)とを交換した.	1 3 4 2
1 3 4 2 < < > <	先ほどの mobile は配列内で最大の値だったので何もしない
1 3 2 4 < < < >	mobile は 3, 4. 最大の mobile は 4 であったからそれとそれが指している値(2)とを交換した.	1 3 2 4
1 3 2 4 < < < >	先ほどの mobile は配列内で最大の値だったので何もしない
3 1 2 4 < < < >	mobile は 3. 最大の mobile は 3 であったからそれとそれが指している値(1)とを交換した.	3 1 2 4
3 1 2 4 < < < <	先ほどの mobile より大きいものが mobile の方を向くように書き換える
3 1 4 2 < < < <	mobile は 2, 4. 最大の mobile は 4 であったからそれとそれが指している値(2)とを交換した.	3 1 4 2
3 1 4 2 < < < <	先ほどの mobile は配列内で最大の値だったので何もしない
3 4 1 2 < < < <	mobile は 4. 最大の mobile は 4 であったからそれとそれが指している値(1)とを交換した.	3 4 1 2
3 4 1 2 < < < <	先ほどの mobile は配列内で最大の値だったので何もしない
4 3 1 2 < < < <	mobile は 4, 2. 最大の mobile は 4 であったからそれとそれが指している値(3)とを交換した.	4 3 1 2
4 3 1 2 < < < <	先ほどの mobile は配列内で最大の値だったので何もしない
4 3 2 1 < < < <	mobile は 2. 最大の mobile は 2 であったからそれとそれが指している値(1)とを交換した.	4 3 2 1
4 3 2 1 > > < <	先ほどの mobile より大きいものが mobile の方を向くように書き換える
3 4 2 1 > > < <	mobile は 4, 3. 最大の mobile は 4 であったからそれとそれが指している値(3)とを交換した.	3 4 2 1
3 4 2 1 > > < <	先ほどの mobile は配列内で最大の値だったので何もしない
3 2 4 1 > < > <	mobile は 4. 最大の mobile は 4 であったからそれとそれが指している値(2)とを交換した.	3 2 4 1
3 2 4 1 > < > <	先ほどの mobile は配列内で最大の値だったので何もしない
3 2 1 4 > < < >	mobile は 3, 4. 最大の mobile は 4 であったからそれとそれが指している値(1)とを交換した.	3 2 1 4
3 2 1 4 > < < >	先ほどの mobile は配列内で最大の値だったので何もしない
2 3 1 4 < > < >	mobile は 3. 最大の mobile は 3 であったからそれとそれが指している値(2)とを交換した.	2 3 1 4
2 3 1 4 < > < <	先ほどの mobile より大きいものが mobile の方を向くように書き換える
2 3 4 1 < > < <	mobile は 3, 4. 最大の mobile は 4 であったからそれとそれが指している値(1)とを交換した.	2 3 4 1
2 3 4 1 < > < <	先ほどの mobile は配列内で最大の値だったので何もしない
2 4 3 1 < < > <	mobile は 4. 最大の mobile は 4 であったからそれとそれが指している値(3)とを交換した.	2 4 3 1
2 4 3 1 < < > <	先ほどの mobile は配列内で最大の値だったので何もしない
4 2 3 1 < < > <	mobile は 4, 3. 最大の mobile は 4 であったからそれとそれが指している値(2)とを交換した.	4 2 3 1
4 2 3 1 < < > <	先ほどの mobile は配列内で最大の値だったので何もしない
4 2 1 3 < < < >	mobile は 3. 最大の mobile は 3 であったからそれとそれが指している値(1)とを交換した.	4 2 1 3
4 2 1 3 > < < >	先ほどの mobile より大きいものが mobile の方を向くように書き換える
2 4 1 3 < > < >	mobile は 4. 最大の mobile は 4 であったからそれとそれが指している値(2)とを交換した.	2 4 1 3
2 4 1 3 < > < >	先ほどの mobile は配列内で最大の値だったので何もしない
2 1 4 3 < < > >	mobile は 4. 最大の mobile は 4 であったからそれとそれが指している値(1)とを交換した.	2 1 4 3
2 1 4 3 < < > >	先ほどの mobile は配列内で最大の値だったので何もしない
2 1 3 4 < < > >	mobile は 4. 最大の mobile は 4 であったからそれとそれが指している値(3)とを交換した.	2 1 3 4
2 1 3 4 < < > >	先ほどの mobile は配列内で最大の値だったので何もしない
2 1 3 4 < < > >	mobile が存在しないため終了

コード例

public static List<int[]> SteinhausJohnsonTrotter(int n) {
  // Initialise variables:
  int[] a = new int[n];// permutation array
  bool[] d = new bool[n];// 値の向き(右向きであるか？)
  for (int i = 0; i < n; ++i) {
    // a[] が { 1, 2, ..., n } であるように初期化しているが、
    // 昇順でさえあれば int[] である必要すらない.
    a[i] = i + 1;
    d[i] = false;// すべて左向き
  }
  List<int[]> result = new List<int[]>();// 結果を格納するリスト
  // Generate permutations
  result.Add((int[]) a.Clone());// Output
  int mobilePos;
  // FindGreatestMobile は最大の mobile が存在する位置を返す. mobile が存在しない場合は -1.
  while ((mobilePos = FindGreatestMobile(a, d)) != -1) {
    // newPos := mobile が指している値の位置
    int newPos = mobilePos + (d[mobilePos] ? 1 : -1);
    // mobile とそれが指している値を入れ替える
    Swap(a, mobilePos, newPos);
    Swap(d, mobilePos, newPos);

    // result.Add と Orient は順不同
    result.Add((int[]) a.Clone());// Output

    // mobile より大きいものが mobile の方を向くように d を書き換える
    // 上で mobilePos の値と newPos の値を入れ替えたので、mobile は現在 newPos の位置にある
    Orient(newPos, a, d);
  }
  return result;
}// SteinhausJohnsonTrotter(int n)

private static void Orient(int m, int[] a, bool[] d) {
  // a[] の中身は { 1, 2, ..., n } としているため、a[m] == a.Length としている.
  // a[] として重複のない任意の集合を使う場合は最大値を引数でもらうべきかも.
  if (a[m] == a.Length) return;// There is no number that is greater than a[m].
  // [0 .. m) の範囲で a[m] より大きいものがあれば、それを右向きにする.
  for (int i = 0; i < m; ++i) {
    if (a[m] < a[i]) d[i] = true;
  }
  // (m .. n) の範囲で a[m] より大きいものがあれば、それを左向きにする.
  for (int i = m; i < a.Length; ++i) {
    if (a[m] < a[i]) d[i] = false;
  }
}

private static int FindGreatestMobile(int[] a, bool[] d) {
  // mobile の内最も大きいものを探し、そのインデックスを返す. mobile が存在しない場合は -1 を返す.
  int mobilePos = -1;
  int mobile = int.MinValue;
  for (int i = 0; i < a.Length; ++i) {
    if (IsMobile(i, a, d) && mobile < a[i]) {
      // a[i] が mobile であり、かつ最大であればこちらを採用する
      mobilePos = i;
      mobile = a[i];
    }
  }
  return mobilePos;
}

private static bool IsMobile(int i, int[] a, bool[] d) {
  int k = d[i] ? 1 : -1;// d[i] := 右向きか？
  int j = i + k;// j := a[i] が指し示している値のインデックス
  if (j < 0 || a.Length <= j) return false;// j が配列の範囲外であれば mobile ではない
  return a[i] > a[j];// a[i] の方が大きければ mobile
}

重複置換の全列挙

上に示したふたつとは異なり、要素に同じものを含む場合の置換を「重複置換」とか「同じものを含む順列」などと呼ぶ.
例えば、"SUCCESS" の文字を並び替えて "SSSECUC" や "CSCESUS" などを作るような問題である.
英語では multiset permutation と言うらしい.

Takaoka multiset permutations algorithm

StackOverflowの回答で見かけた Python のコードを C# に書き換えたものを示す:

コード例

// Takaoka(new List<int> { 2, 1, 2, 1, 2 }) は次の結果を生成する:
// [ 2 2 2 1 1 ]
// [ 1 2 2 2 1 ]
// [ 2 1 2 2 1 ]
// [ 2 2 1 2 1 ]
// [ 1 2 2 1 2 ]
// [ 2 1 2 1 2 ]
// [ 1 2 1 2 2 ]
// [ 1 1 2 2 2 ]
// [ 2 1 1 2 2 ]
// [ 2 2 1 1 2 ]
// 1が2つ、2が3つあるため、全体としては (2+3)! / (2! * 3!) = 10 通りの結果となる
public static List<int[]> Takaoka(List<int> nums) {
  int N = nums.Count;

  // 与えられたものを降順にソートする. 引数を書き換えるのは気が引けるため配列にしてからソートしている.
  int[] values = nums.ToArray();
  Array.Sort<int>(values, (a, b) => b - a);

  // 値の並びは連結リストとして管理する. head := 0番目の要素. nexts[i] := values[i] に対する次のノード, 存在しない場合は -1.
  int head = 0;
  int[] nexts = new int[N];
  for(int n = 0; n < N-1; ++n) {
    nexts[n] = n + 1;
  }
  nexts[N-1] = -1;

  // i := 最後から2番目の要素として処理を始める
  // afteri := その次のノード
  int afteri = N - 1;
  int i = afteri - 1;

  List<int[]> result = new List<int[]>();// 結果を格納するリスト

  result.Add(ListToArray(head, values, nexts));// 連結リストをひとつの配列に変換したものを出力とする
  while (nexts[afteri] != -1 || values[afteri] < values[head]) {
    int j = nexts[afteri];
    int beforek;
    // i, afteri, j の順序で並んでいる.
    if (j != -1 && values[i] >= values[j]) {
      beforek = afteri;
    } else {
      beforek = i;
    }
    // beforek は { i, afteri } のどちらかであり、k は beforek の次の要素(afteri, または j)である.
    int k = nexts[beforek];
    // k を先頭に持っていく
    nexts[beforek] = nexts[k];
    nexts[k] = head;
    // head を書き換える前に i, afteri の値を更新する
    if (values[k] < values[head]) {
      i = k;
    }
    afteri = nexts[i];
    // 先頭は k になった
    head = k;

    result.Add(ListToArray(head, values, nexts));// 連結リストをひとつの配列に変換したものを出力とする
  }
  return result;
}

private static int[] ListToArray(int head, int[] values, int[] nexts) {
  // values, nexts は連結リスト
  // values[i] に <次のノード> が存在しない場合、nexts[i] には -1 が入っている.
  int[] result = new int[values.Length];
  int cur = head;
  int idx = 0;
  while (cur != -1) {
    result[idx++] = values[cur];
    cur = nexts[cur];
  }
  return result;
}

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up