C#でSTLのnext_permutation的なものを

TopCoderでnext_permutationゲーな問題が出ると途端にC++が有利になって、C#だとコーディング時間的に厳しいので、C#で実装しておく。パフォーマンスなんて知りません。

2009/1/23 バグ修正＆TopCoder SRM 433 Div 1 Easy MagicWordsでVerified

using System;
using System.Collections.Generic;
using System.Text;

namespace TopCoderLib
{
    public static class Algorithm
    {
        /// <summary>
        /// シーケンスの次の順列を求めます
        /// </summary>
        /// <typeparam name="T">順列を構成する要素の型</typeparam>
        /// <param name="array">次の順列を求めたいシーケンス</param>
        /// <param name="start">次の順列を求めたい範囲の最初のインデックス</param>
        /// <param name="length">次の順列を求めたい範囲の長さ</param>
        /// <returns>引数arrayが最後の順列ならばfalse、そうでないならtrueを返します</returns>
        public static bool NextPermutation<T>(T[] array, int start, int length)
            where T : IComparable
        {
            int end = start + length - 1;

            // 範囲が狭すぎる
            if (end <= start) return false;

            int last = end;
            while (true)
            {
                int pos = last--;
                
                if (array[last].CompareTo(array[pos]) < 0)
                {
                    int i;
                    for (i = end + 1; array[last].CompareTo(array[--i]) >= 0; ) { }
                    T tmp = array[last]; array[last] = array[i]; array[i] = tmp;
                    Array.Reverse(array, pos, end - pos + 1);
                    return true;
                }
                if (last == start)  // 最後の順列
                {
                    Array.Reverse(array, start, end - start);
                    return false;
                }
            }

            // ここに来ることはない
            throw new Exception("NextPermutation: Fatal error");
        }
    }
}

とりあえず int[10], char[10] 等のスカラ型配列で測ったら 0.5sec 程度。11要素はムリポ。