ランダムテスト知見
本格的に開発開始したために移行しました。
シェルスクリプトで回す
code:randomTest.sh
# 総当たり
for d in $(seq 1 100)
do
echo ${d}
for n in $(seq 1 1000)
do
# echo ${d} ${n}
echo ${d} ${n} | ./a.out > /dev/null
done
done
# ランダムテスト
for i in $(seq 1 100000)
do
d=$((RANDOM % 100 + 1))
n=$((RANDOM + 1))
echo ${d} ${n}
echo ${d} ${n} | ./a.out > /dev/null
done
簡易チェックとしては楽。C++側は普通のコードで愚直解を比較するだけ(異なる値なら入力ケースを標準エラー出力)
RANDOMが0 〜 32767までしか生成できないなど、少し凝ったことをしようとすると頑張る必要があるので、あまり嬉しくはない。
次数上限ありN頂点M辺グラフ
prufer列生成して木に辺を足す。
code:randomGraph.cpp
/* input */
int N = 60;
int M = 65;
const int MAX_DEGREE = 3;
vector<vector<int>> G(N);
random_device rng;
// ランダムに制限列を作る
vector<int> visitables(N);
while (true) {
rep(i, N) visitablesi = rng() % MAX_DEGREE + 1; // rep(i, N) visitablesi = MAX_DEGREE; int sumDegree = reduce(all(visitables));
// visitable * 2が最大次数で、次数の和 * 2 = 辺なので係数が相殺
if (sumDegree >= M) break;
}
// ランダムに次数制限付きのprufer列を作る
vector<int> countDegrees(N);
vector<int> prufer;
rep(i, N - 2) {
while (true) {
int v = rng() % N;
if (countDegreesv == MAX_DEGREE) continue; prufer.push_back(v);
break;
}
}
return prufer;
};
auto prufer2tree = &(vector<int>& prufer) { vector<int> degrees(N, 1);
for (auto v : prufer) degreesv++; // 次数1で最小のiについて、辺(i, j)を追加する
rep(i, N - 2) {
rep(j, N) {
break;
}
}
}
// 次数1の残った2頂点に辺を追加する
vector<int> vec;
rep(i, N) if (degreesi == 1) vec.push_back(i); assert(vec.size() == 2);
};
// 辺を適当に足す
vector<int> countDegrees(N);
set<pair<int, int>> edges;
rep(v, N) for (auto u : Gv) { edges.emplace(min(v, u), max(v, u));
}
int loopCnt = 0;
while (M > (int)edges.size() && loopCnt <= 100000) {
loopCnt++;
int i = rng() % N, j = rng() % N;
if (i == j) continue;
if (countDegreesi == visitablesi * 2) continue; if (countDegreesj == visitablesj * 2) continue; if (edges.count(make_pair(min(i, j), max(i, j)))) continue;
edges.emplace(i, j);
countDegreesi++, countDegreesj++; loopCnt = 0;
}
if (loopCnt >= 100000) assert(false);
};
printf("%d %d\n", N, M);
set<pair<int, int>> edges;
rep(v, N) for (auto u : Gv) edges.emplace(min(v, u), max(v, u)); for (auto v, u : edges) printf("%d %d\n", v + 1, u + 1); for (auto v : visitables) cout << v << " ";
cout << endl;
};
vector<int> prufer = randPrufer();
prufer2tree(prufer);
tree2graph();
printGraph();