public class Combination
{
private long n = 0;
private long k = 0;
private long[] data = null;
public Combination(long n, long k)
{
if (n < 0 || k < 0) // 通常は n >= k
throw new Exception("コンストラクタのパラメータが負の数です");
this.n = n;
this.k = k;
this.data = new long[k];
for (long i = 0; i < k; ++i)
this.data[i] = i;
} // Combination(n,k)
public Combination(long n, long k, long[] a) // a[] の組み合わせ
{
if (k != a.Length)
throw new Exception("配列の長さが k に等しくありません");
this.n = n;
this.k = k;
this.data = new long[k];
for (long i = 0; i < a.Length; ++i)
this.data[i] = a[i];
if (!this.IsValid())
throw new Exception("配列の値が正しくありません");
} // (n,k,a) の組み合わせ
public bool IsValid()
{
if (this.data.Length != this.k)
return false; // 破損
for (long i = 0; i < this.k; ++i)
{
if (this.data[i] < 0 || this.data[i] > this.n - 1)
return false; // 範囲外の値
for (long j = i + 1; j < this.k; ++j)
if (this.data[i] >= this.data[j])
return false; // 重複しているか、辞書式でない
}
return true;
} // IsValid()
public override string ToString()
{
string s = "{ ";
for (long i = 0; i < this.k; ++i)
s += this.data[i].ToString() + " ";
s += "}";
return s;
} // ToString()
public Combination Successor()
{
if (this.data[0] == this.n - this.k)
return null;
Combination ans = new Combination(this.n, this.k);
long i;
for (i = 0; i < this.k; ++i)
ans.data[i] = this.data[i];
for (i = this.k - 1; i > 0 && ans.data[i] == this.n - this.k + i; --i)
;
++ans.data[i];
for (long j = i; j < this.k - 1; ++j)
ans.data[j + 1] = ans.data[j] + 1;
return ans;
} // Successor()
public static long Choose(long n, long k)
{
if (n < 0 || k < 0)
throw new Exception("Choose() の負のパラメータは無効です");
if (n < k)
return 0; // 特殊なケース
if (n == k)
return 1;
long delta, iMax;
if (k < n - k) // 例: Choose(100,3)
{
delta = n - k;
iMax = k;
}
else // 例: Choose(100,97)
{
delta = k;
iMax = n - k;
}
long ans = delta + 1;
for (long i = 2; i <= iMax; ++i)
{
checked { ans = (ans * (delta + i)) / i; }
}
return ans;
} // Choose()
// 組み合わせ C(n,k) の辞書式順序で m 番目の要素を返します
public Combination Element(long m)
{
long[] ans = new long[this.k];
long a = this.n;
long b = this.k;
long x = (Choose(this.n, this.k) - 1) - m; // x は m の "デュアル"
for (long i = 0; i < this.k; ++i)
{
ans[i] = LargestV(a, b, x); // 最大値は v です。ここで、v < a および vCb < x
x = x - Choose(ans[i], b);
a = ans[i];
b = b - 1;
}
for (long i = 0; i < this.k; ++i)
{
ans[i] = (n - 1) - ans[i];
}
return new Combination(this.n, this.k, ans);
} // Element()
// 最大値 v を返します。ここで、v < a および Choose(v,b) <= x
private static long LargestV(long a, long b, long x)
{
long v = a - 1;
while (Choose(v, b) > x)
--v;
return v;
} // LargestV()
} // Combination クラス
class Program
{
static void Main(string[] args)
{
Combination c = new Combination(5, 2);
Console.WriteLine("\nWith n=5 and k=3 there are " + Combination.Choose(5, 3) + " combination elements.");
// 全組み合わせを表示する
Console.WriteLine("\nThe elements are:");
for (int i = 0; i < 10; ++i)
{
Console.WriteLine(i + ": " + c.ToString());
c = c.Successor();
}
// コンソールが入力されたインデックスの要素を表示
c = new Combination(5, 2);
Console.Write("\nEnter an index: ");
int m = int.Parse(Console.ReadLine());
Console.WriteLine("That combination element is: " + c.Element(m).ToString());
}
}
[出力結果]
With n=5 and k=3 there are 10 combination elements.
The elements are:
0: { 0 1 }
1: { 0 2 }
2: { 0 3 }
3: { 0 4 }
4: { 1 2 }
5: { 1 3 }
6: { 1 4 }
7: { 2 3 }
8: { 2 4 }
9: { 3 4 }
Enter an index: 3
That combination element is: { 0 4 }
最終更新：2009年02月13日 15:18
