組み合わせをやったなら順列もやらんとならんのでやった。
順列の結果だけ見てアルゴリズム自体は自分で考えるので作るのに4日かかった。
コード
using System.Numerics; public partial class MathPlus { /// <summary> /// 順列クラス /// </summary> public class Permutation { /// <summary> /// 要素の数 /// </summary> private int _n; /// <summary> /// 選択する個数 /// </summary> private int _k; private int[] _elements; /// <summary> /// 順列の数 /// </summary> public BigInteger Count { get { return this.Permutaton_Count(); } } /// <summary> /// コンストラクタ /// P(n, n) /// </summary> /// <param name="n">要素の数</param> public Permutation(int n) { this._n = n; this._k = n; this._elements = Enumerable.Range(1, this._n).ToArray(); } /// <summary> /// コンストラクタ /// P(n, k) /// </summary> /// <param name="n">要素の数</param> /// <param name="k">選択する個数</param> public Permutation(int n, int k) { this._n = n; this._k = k; this._elements = Enumerable.Range(1, this._n).ToArray(); } /// <summary> /// P(n, k)を計算する /// </summary> /// <returns>順列 P(n, k) の数</returns> private BigInteger Permutaton_Count() { var numerator = new BigInteger(1); var denominator = new BigInteger(1); for (int i = 2; i <= this._n; i++) { numerator *= i; } for (int i = 2; i <= this._n - this._k; i++) { denominator *= i; } return numerator / denominator; } /// <summary> /// 順列の反復子を得る /// </summary> /// <returns>P(n, k)の反復子</returns> public IEnumerable<int[]> GetEnumerable() { while (true) { yield return this.Result(); if (this.IsMaximum()) break; this.Update(); } yield break; } /// <summary> /// 順列の配列を更新する /// </summary> private void Update() { for (int i = this._k - 1; i >= 0; i--) { if (this._elements[i] != this._n) { var idx = this.SearchNumberIndex(i); if (idx >= 0) { this.Swap(i, idx); this.Sort(i); break; } } } } /// <summary> /// elements の ihead より後から /// elements[ihead] より大きくて最も小さい値をもつインデックスを探す /// </summary> /// <param name="ihead">arrを参照するインデックス</param> /// <returns>インデックス</returns> private int SearchNumberIndex(int ihead) { var n = this._elements[ihead]; var v = int.MaxValue; var idx = -1; for (int i = ihead + 1; i < this._elements.Length; i++) { if (n < this._elements[i] & v > this._elements[i]) { v = this._elements[i]; idx = i; } } return idx; } /// <summary> /// 値のスワップ /// </summary> /// <param name="idx1">交換するインデックス1</param> /// <param name="idx2">交換するインデックス2</param> private void Swap(int idx1, int idx2) { var tmp = 0; tmp = this._elements[idx1]; this._elements[idx1] = this._elements[idx2]; this._elements[idx2] = tmp; } /// <summary> /// arr配列のidxインデックスより後を小さい順にソートする /// </summary> /// <param name="idx">インデックス</param> private void Sort(int idx) { var elcopy = new int[this._elements.Length - (idx + 1)]; if(elcopy.Length == 0) return; for (int i = 0; i < elcopy.Length; i++) elcopy[i] = this._elements[idx + 1 + i]; Array.Sort(elcopy); for (int i = 0; i < elcopy.Length; i++) this._elements[idx + 1 + i] = elcopy[i]; } /// <summary> /// 順列配列が最大値になっているか判定する /// </summary> /// <returns>true:最大値, false:非最大値</returns> private bool IsMaximum() { for (int i = 0; i < this._k; i++) { if (this._elements[i] != (this._n - i)) return false; } return true; } /// <summary> /// 順列配列からkサイズ切り出す /// </summary> /// <returns>kサイズ順列配列</returns> private int[] Result() { var r = new int[this._k]; for (int i = 0; i < r.Length; i++) r[i] = this._elements[i]; return r; } } }
使い方
こんなふうに書くと
var permutation = new MathPlus.Permutation(3, 3); foreach (var item in permutation.GetEnumerable()) { Console.WriteLine($"[{string.Join(",", item)}]"); Thread.Sleep(10); } Console.WriteLine(($"個数:{permutation.Count}"));
こうなる
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] 個数:6
