ファレイ数列

ファレイ数列の定義に関しては C#のファレイ数列を参照。
C#で難しかったのは有理数クラスの作成であって、後はLINQの機能を使用すれば簡単にファレイ数列が構成できた。 今回作成するプログラムでは、自作有理数の構造体の列に関して、 重複要素の削除とソートをどのように行うかがポイントとなる。

コード例.

まず、最大分母を指定して、網羅的に数列を構成する。

\[ A = \left\{1,\frac{1}{2},\frac{2}{2},\frac{1}{3},\frac{2}{3},\frac{3}{3},...,\frac{N}{N} \right\} \]

このとき、Aの要素数は最大分母をNとするとき、 $\displaystyle \frac{N(N+1)}{2}$ 個存在する。

後はこの集合Aを昇順ソートして、重複要素を削除すればファレイ数列が得られる。

(自作)有理数の列のソートには、stdlib.hのqsortを使用する。これは

qsort(array,要素数,要素のサイズ,比較関数)

の形で利用するが、比較関数は有理数を比較するような定義にしなければならない。

あとは重複要素の削除だが、これは自作する。いきなり重複要素削除するのは大変そうなので、 ソートされたものに限定して重複要素を削除するUniqueRというものを作成する。 これを使用して、DistinctR という 「qsort + UniqueR」の機能を持った一般的な重複要素削除関数を作成する。

重複要素の削除とソート

// ファイレイ数例を構成し表示する。自作関数は先頭が大文字。
#include <stdio.h>
#include <stdlib.h>
// 有理数の分子N(numerator)と分母D(denominator)
typedef struct {
	int N;
	int D;
}Rational;
// 最大公約数
int GCD(int a, int b) {
	while (b != 0) {
		int tmp = a;
		a = b;
		b = tmp % b;
	}
	return a > 0 ? a : -a;
}
// 有理数を約分、また分母にマイナスが来ないように標準化。
void Normalize(Rational* r) {
	int gcd = GCD(r->N, r->D);
	r->N = r->N / gcd;
	r->D = r->D / gcd;
	if (r->D < 0) {
		r->N *= -1;
		r->D *= -1;
	}
}
// stdlib.hで用意されたqsort使用の際に利用する有理数の比較関数。
int CompareR(const void* x, const void* y) {
	Rational r1 = *(Rational*)x;
	Rational r2 = *(Rational*)y;
	Normalize(&r1);
	Normalize(&r2);
	int a = r1.N; int b = r1.D;
	int c = r2.N; int d = r2.D;
	// a/b - c/d = (ad-bc)/bd
	return a * d - b * c;
}
// 二つの有理数が等しいか判定する関数。等しければ1.等しくなければ0.
int EqualR(Rational r1, Rational r2) {
	int a = r1.N; int b = r1.D;
	int c = r2.N; int d = r2.D;
	// a/b - c/d = (ad-bc)/bd
	return a * d - b * c == 0 ? 1 : 0;
}
// ソートされた有理数列から重複要素を削除する関数。ソートされていないと使えない。
void UniqueR(Rational* seq, int seqCount, int* length) {
	int k = 0;
	int i;
	for (i = 0; i < seqCount; i++) {
		seq[i] = seq[k];
		int p = 1;
		while (k + p < seqCount && EqualR(seq[k], seq[k + p]) == 1) {
			p++;
		}
		k += p;
		if (k >= seqCount) {
			i++;
			break;
		}
	}
	*length = i;
}
// ソートしてからUniqueRを適用する関数。
void DistinctR(Rational* seq, int seqCount,int* len) {
	int i;
	for (i = 0; i < seqCount; i++) {
		Normalize(&seq[i]);
	}
	qsort(seq, seqCount, sizeof(Rational), CompareR);
	*len = 0; 
	UniqueR(seq, seqCount, len);
}

int main()
{
	Rational seq[] = { {3,1},{2,1},{1,1},{2,1},{2,1},{3,1} };
	int len = 0;
	DistinctR(seq, sizeof seq / sizeof(seq[0]), &len);
	for (int i = 0; i < len; i++) {
		if (seq[i].D == 1) {
			printf("%d,", seq[i].N);
		}
		else {
			printf("%d/%d,", seq[i].N, seq[i].D);
		}
	}
}

実行結果. 1,2,3,

ファレイ数列の構成

重複要素削除とソートができれば、ファレイ数列は簡単に構成できる。

// ファイレイ数例を構成し表示する。自作関数は先頭が大文字。
#include <stdio.h>
#include <stdlib.h>
// 有理数の分子N(numerator)と分母D(denominator)
typedef struct {
	int N;
	int D;
}Rational;
// 最大公約数
int GCD(int a, int b) {
	while (b != 0) {
		int tmp = a;
		a = b;
		b = tmp % b;
	}
	return a > 0 ? a : -a;
}
// 有理数を約分、また分母にマイナスが来ないように標準化。
void Normalize(Rational* r) {
	int gcd = GCD(r->N, r->D);
	r->N = r->N / gcd;
	r->D = r->D / gcd;
	if (r->D < 0) {
		r->N *= -1;
		r->D *= -1;
	}
}
// stdlib.hで用意されたqsort使用の際に利用する有理数の比較関数。
int CompareR(const void* x, const void* y) {
	Rational r1 = *(Rational*)x;
	Rational r2 = *(Rational*)y;
	Normalize(&r1);
	Normalize(&r2);
	int a = r1.N; int b = r1.D;
	int c = r2.N; int d = r2.D;
	// a/b - c/d = (ad-bc)/bd
	return a * d - b * c;
}
// 二つの有理数が等しいか判定する関数。等しければ1.等しくなければ0.
int EqualR(Rational r1, Rational r2) {
	int a = r1.N; int b = r1.D;
	int c = r2.N; int d = r2.D;
	// a/b - c/d = (ad-bc)/bd
	return a * d - b * c == 0 ? 1 : 0;
}
// ソートされた有理数列から重複要素を削除する関数。ソートされていないと使えない。
void UniqueR(Rational* seq, int seqCount, int* length) {
	int k = 0;
	int i;
	for (i = 0; i < seqCount; i++) {
		seq[i] = seq[k];
		int p = 1;
		while (k + p < seqCount && EqualR(seq[k], seq[k + p]) == 1) {
			p++;
		}
		k += p;
		if (k >= seqCount) {
			i++;
			break;
		}
	}
	*length = i;
}
// ソートしてからUniqueRを適用する関数。
void DistinctR(Rational* seq, int seqCount,int* len) {
	int i;
	for (i = 0; i < seqCount; i++) {
		Normalize(&seq[i]);
	}
	qsort(seq, seqCount, sizeof(Rational), CompareR);
	*len = 0; 
	UniqueR(seq, seqCount, len);
}

int main()
{
	int maxDenom = 50; //分母の最大
	int lengthSeq = maxDenom * (maxDenom + 1) / 2;
	Rational * seq = (Rational*)malloc(sizeof(Rational) * lengthSeq);
	if (seq == NULL) {
		exit(1);
	}
	// 分母がmaxDenomまで網羅的に要素を追加する。
	int i, k;
	int u = 0;
	for (i = 1; i <= maxDenom; i++) {
		for (k = 1; k <= i; k++) {
			seq[u].N = k;
			seq[u].D = i;
			u++;
		}
	}
	// 重複要素の削除
	int len = 0;
	DistinctR(seq, lengthSeq,&len);
	// 要素の表示
	for (i = 0; i < len; i++) {
		printf("%d/%d,", seq[i].N, seq[i].D);
	}
	free(seq);
}

実行結果.

1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,1/1,