次の順列を求める関数 2020/02/20

NextPermutation.cs

using System;

namespace Scratch
{
    public class Program
    {
        public static void Main()
        {
            int[] array = new int[] { 0, 1, 2, 3 };
            for (int i = 0; i < 24; i++)
            {
                Console.WriteLine(string.Join(" ", array));
                NextPermutation(array);
            }

            // output
            // 0 1 2 3
            // 0 1 3 2
            // 0 2 1 3
            // 0 2 3 1
            // 0 3 1 2
            // 0 3 2 1
            // 1 0 2 3
            // ...
        }

        public static void NextPermutation(int[] array)
        {
            // a[left] < a[left+1] を満たす最大のleftを探す
            int left = array.Length - 2;
            while (array[left] > array[left + 1])
            {
                left--;
                if (left < 0) return;
            }

            // a[left] < a[right] を満たす最大のrightを探す
            int leftVal = array[left];
            int right = array.Length - 1;
            while (leftVal > array[right])
            {
                right--;
            }

            // 入れ替える
            Swap(ref array[left], ref array[right]);

            // 後ろを全部入れ替える。入れ替え後は a[left] > a[left+1] < a[left+2] < ... < a[length-1] という不等式が成り立つ。
            left++;
            right = array.Length - 1;
            while (left < right)
            {
                Swap(ref array[left], ref array[right]);
                left++;
                right--;
            }
        }

        public static void Swap<T>(ref T a, ref T b)
        {
            T tmp = a;
            a = b;
            b = tmp;
        }
    }
}