C#で順列をすべて表示する

はじめに

Atcoderで順列のすべてのパターンを洗い出す必要のある問題があったので調べた．C++にはnext_permutationがありそれを使えば順列を全列挙できるがC#にはないらしい．．．ので作ります．

C#で順列の列挙

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        List<int> a = Console.ReadLine().Split().Select(int.Parse).ToList();
        a.Sort();

        //全列挙
        do
        {
            Console.WriteLine(string.Join(" ", a));
        }while (NextPermutation(a));
        
    }

    // C#には next_permutation がないので、自前で実装
    static bool NextPermutation(List<int> a)
    {
        int i = a.Count - 2;
        while (i >= 0 && a[i] >= a[i + 1]) i--;

        if (i < 0) return false;

        int j = a.Count - 1;
        while (a[j] <= a[i]) j--;

        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;

        a.Reverse(i + 1, a.Count - i - 1);
        return true;
    }
}

入力例1

1 2 3

出力例1

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

入力例2

1 1 2

出力例2

1 1 2
1 2 1
2 1 1

なんでこれでいけるのかはなんとなくはわかったけど説明難しいです