C# で順列の全パターンを列挙する
順列とは
nPm で表現される、n 個の要素から m 個を選択して得られる重複のない有限列のこと。
例えば ₃P₂ の場合は以下のように列挙される。
1, 2 1, 3 2, 1 2, 3 3, 1 3, 2
C# ではこれを実現するためのライブラリがデフォルトでは用意されていないため、自前で実装する必要があります。
コード
C# には yield return
や LINQ があるため比較的簡潔に実装することができます。
以下、実装
using System.Collections.Generic; using System.Linq; namespace UniDotLog { public class Sample { public IEnumerable<int[]> GetPermutation(int n, int m) => GetPermutationInternal(Array.Empty<int>(), Enumerable.Range(1, n), m); private IEnumerable<int[]> GetPermutationInternal(IEnumerable<int> selected, IEnumerable<int> candidates, int rest) { if (rest == 0) { yield return selected.ToArray(); yield break; } foreach (var item in candidates) foreach (var result in GetPermutationInternal(selected.Append(item), candidates.Where(x => x != item), rest - 1)) yield return result; } } }
もしくはクエリ式を使って
using System.Collections.Generic; using System.Linq; namespace UniDotLog { public class Sample { public IEnumerable<int[]> GetPermutation(int n, int m) => GetPermutationInternal(Array.Empty<int>(), Enumerable.Range(1, n), m); private IEnumerable<int[]> GetPermutationInternal(IEnumerable<int> selected, IEnumerable<int> candidates, int rest) { if (rest == 0) return new [] { selected.ToArray() }; return from item in candidates from result in GetPermutationInternal(selected.Append(item), candidates.Where(x => x != item), rest - 1) select result; } } }
foreach
がネストするようなケースの場合、クエリ式の方が綺麗に書けることがあります。
return new [] { selected.ToArray() };
の箇所は以下のような拡張メソッドを噛ませて return selected.ToArray().Singleton();
としても良いかと思います。
public static class Ex { // Singleton はデザインパターン的な意味での Singleton ではなく数学的な意味での Singleton public static IEnumerable<T> Singleton<T>(this T x) => new [] { x }: }