Zenn
📝

【C#アルゴリズム】全探索_順列列挙とは

2024/11/19に公開
C#
順列
tech

はじめに

競技プログラミングで順列列挙を使用する問題が出てきたのでまとめました。
C#で順列を列挙する方法には、再帰を使用したバックトラッキングが一般的です。この手法をまとめました。

順列列挙とは

順列列挙では、与えられた要素のすべての並べ替え（順列）を生成します。
例えば、入力が {1, 2, 3} であれば、生成される順列は以下の6通りです。

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

C#での実装 

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 元のリスト
        List<int> input = new List<int> { 1, 2, 3 };

        // 結果を保存するリスト
        List<int[]> permutations = new List<int[]>();

        // 順列を生成
        Permute(permutations, input, 0);

        // 結果を出力
        Console.WriteLine("Generated Permutations:");
        foreach (var perm in permutations)
        {
            Console.WriteLine(string.Join(", ", perm));
        }
    }

    private static void Permute(List<int[]> permute, List<int> tempPermute, int start)
    {
        for (int i = start; i < tempPermute.Count; i++)
        {
            Swap(tempPermute, i, start); // 要素を入れ替える。
            Permute(permute, tempPermute, start + 1);
            Swap(tempPermute, start, i); // 入れ替えた要素を元に戻す。
        }

        if (start == tempPermute.Count - 1)
        {
            permute.Add(tempPermute.ToArray());
        }
    }

    private static void Swap(List<int> list, int i, int j)
    {
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }
}

解説

順列生成の再帰メソッド 

Permute(permutations, input, 0);
  • Permute メソッドを呼び出して順列を生成する。
  • 引数:
    • permutations: 結果を保存するリスト。
    • input: 元のリスト（tempPermute として扱われる）。
    • 0: 現在の操作位置（スタート位置）。

Permute メソッド 

private static void Permute(List<int[]> permute, List<int> tempPermute, int start)

このメソッドは再帰を用いて、リストの順列を生成します。

  • 引数:

    • permute: 結果を保存するリスト。
    • tempPermute: 現在処理中のリスト（順列生成用）。
    • start: 処理対象の開始位置。

  • ロジック:

    • ループでリストの現在の要素を操作する。
    • 要素をスワップして次の順列を生成する。
    • 再帰終了時（start == tempPermute.Count - 1）に現在の順列を保存する。

再帰の動き

  • start 位置の要素をスワップして固定し、次の要素の順列を生成。
  • 再帰から戻った際に、スワップを元に戻す（バックトラッキング）。
  • 最終的に全ての順列が生成される。

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5

Discussion