ひでぼ～blog

C#ときどきゲーム

GAKKOU並び替え問題をC#で解いてみる

C#

少し前にTwitterでバズってたこの問題をプログラムで解いてみます。 Pythonとかで解いている方がいたのでC#で解いてみます。

並び替えの方針

良い感じに並び替えてくれる便利ライブラリが探せば何かありそうですが、ここは自前で実装してみることにしました。 ただ、そもそも文字列の並び替えってどうするんだっけ…？そんな便利メソッドあったっけ…？ってなったので次のような作戦でやってみました。

  1. 文字列から1文字取り出す "ABC" => ["A", "BC"]
  2. 残りの文字列を並び替える "BC" => ["BC", "CB"]
  3. 並び替えた文字列と最初に取り出した1文字を結合する "A" + ["BC, "CB"] => ["ABC", "ACB"]

まず文字列のアタマからお尻まで文字を1文字ずつ取り出し、残りの文字列と結合してみます。

var source = "GAKKOU";

for (var index = 0; index < source.Length; index++)
{
    var preWord = source[index];
    var postWords = source.Remove(index, 1);

    Console.WriteLine($"{preWord}{postWords}");
}

GAKKOU
AGKKOU
KGAKOU
KGAKOU
OGAKKU
UGAKKO

とりあえず6パターンできました。1文字取り出した後の残りの文字列についても同じように並び替えていけば上手くいきそうな気がする…。 つまり並べ替え部分をメソッド化して再帰的に実行していけば設問通り360パターンの文字列が出来るはず。

全パターン並び替える

先ほどのプログラムをメソッド化して再帰的に呼び出すようにしました。 並び替えた結果の重複と辞書順の並び替えは少しズルいですがLINQのメソッド(Distinct、OrderBy)でやってしまいました。

static void Main(string[] args)
{
    var source = "GAKKOU";

    var results = GetAllSorts(source)
        .Distinct()
        .OrderBy(text => text);

    var count = 0;
    foreach (var result in results)
    {
        count++;
        Console.WriteLine($"{count}: {result}");
    }
}

static IEnumerable<string> GetAllSorts(string source)
{
    if (source.Length == 1)
    {
        yield return source;
        yield break;
    }

    for (var index = 0; index < source.Length; index++)
    {
        // 1文字取り出す
        var preWord = source[index];
        var postWords = source.Remove(index, 1);

        // 残りの文字列を並び変える
        var postWordsAllSorts = GetAllSorts(postWords);

        // 取り出した1文字と並び変えた文字列を結合
        foreach (var sorted in postWordsAllSorts)
        {
            yield return $"{preWord}{sorted}";
        }
    }
}

実行結果を確認すると、

1: AGKKOU
2: AGKKUO
3: AGKOKU
4: AGKOUK
5: AGKUKO
6: AGKUOK
省略
97: GOAKKU
98: GOAKUK
99: GOAUKK
100: GOKAKU
101: GOKAUK
102: GOKKAU
103: GOKKUA

100番目の文字列は"GOKAKU"でした。受験生へのメッセージが込められた素敵な問題ですね。