循環参照の検証
重み
重みとは 循環参照かどうかを調べたい対象が持つ, 参照先の種類の数のことを指す.
例えば a は b を参照、b は c を参照、c は何も参照しない場合.
a の重みは 2.
b の重みは 1.
c の重みは 0.
循環参照が発生している場合 重みは無限となる.
重みの上限値は nC2
循環参照が発生しない範囲での重みには上限がある.
a, の 要素数が1つの場合の 重みの上限値は 0 である(1C2という計算はできない. 一回でも参照があれば a は a を参照することになるので それは循環参照である.)
a, b, の 要素数が2つの場合の 重みの上限値は 2C2で 1 である
a, b, c, の 要素数が3つの場合の 重みの上限値は 3C2で 3 である
a, b, c, d, の 要素数が4つの場合の 重みの上限値は 4C2で 6 である
a, b, c, d, e, の 要素数が5つの場合の 重みの上限値は 5C2で 10 である
ある対象が循環参照をしていないかどうかを調べたい場合, 重みが無限になるかどうかではなく, 重みが上限値を超えるかどうかを調べればよい.
その他
重みが 0 の要素が存在しない場合 循環参照 が発生している
すべての 要素が いずれかの要素を参照している場合 循環参照が必ず発生する.
参照tree
調べたい対象を root とする 参照関係を表した tree として考える場合.
derivation node(root 以外の node) の数が重みとなる.
対象である要素 a は b と c を参照し, b は c を参照している.
a - b - c
- c
この時 a の重みは 3.
また a-b-c, a-c, をそれぞれ route と呼ぶとする.
1つの route 内に 同様の 要素が再び現れた場合 その対象は 循環参照が発生している
a - b - a, など.
code example
// 階乗
int factorial(int n) {
int result = 1;
int index = 0;
while (index < n) {
result = result * (n - index);
index = index + 1;
}
return result;
}
// 順列
int permutation(int n, int r) {
int result = 1;
int index = 0;
while (index < r) {
result = result * (n - index);
index = index + 1;
}
return result;
}
// 組み合わせ
int combination(int n, int r) {
final permutationResult = permutation(n, r);
final factorialResult = factorial(r);
final result = permutationResult / factorialResult;
return result.toInt();
}
// 重みの上限値の算出.
// n が 1 の時 重みは 0.
// n が 2 の時 重みは 1.
// nC2. r が2で固定 の 組み合わせ.
weightUpperLimit(int n) {
if (n == 1) return 0;
// nP2
int permutationResult = 1;
int index = 0;
while (index < 2) {
permutationResult = permutationResult * (n - index);
index = index + 1;
}
// 2の階乗は2.
final factorialResult = 2;
final result = permutationResult / factorialResult;
return result.toInt();
}