複数個の対象についてランク付けをしてもらいたいことがあります。例えば、6種類のソーダ水をおいしさ順に並べてもらい、ソーダ水どうしのおいしさの差を見るなどが考えられます。今回は、そのデータをとるときに「順位の重複を許さないように判定する方法」を考えたいと思います。6種類を「5位・2位・2位・3位・6位・1位」などと評価してしまうと、2位が重複するとともに4位がなくなってしまいます。順序はさておき1位から6位までが一回ずつ含まれていると確認するにはどうすればよいでしょうか。
いちばん簡単な方法は集合の関数を使うことです。setdiff
は二つの集合の差をとってくれるので、numbers
に入っていてhoge
に入っていない数が返ってきます。
numbers <- c(1, 2, 3, 4, 5, 6)
hoge <- c(5, 2, 2, 3, 6, 1)
setdiff(numbers, hoge)
集合が使いにくいプログラミング言語で同様のことをしたいときに、「総和と総積が一致すればよいのでは」と考えてみました(この後、この方法ではうまくいかないことが分かります)。前述の例だと、総和は1+2+3+4+5+6=21、総積は1×2×3×4×5×6=720です。一方でsum(hoge)
は19、prod(hoge)
は360と、さっきの値と一致しないので評価値の重複や不足が推測できます。
この方法を実用するためには、本当にすべての場合でそうなるかを確かめなければなりません。すべての場合を調べるのは大変なので、以下のように「総和と総積の一致」が差集合と同じようにチェック法として使えるのかをモンテカルロ的に調べてみました。N
は対象の個数とします。総和と総積が想定したものと一致しているのに差集合が空集合でないときには、その数列を表示するというプログラムです。
N <- 8
numbers <- seq(from=1, to=N)
p <- prod(numbers)
s <- sum(numbers)
for (k in 1:1000000) {
hoge <- sample(numbers, replace=TRUE)
if (prod(hoge)==p && sum(hoge)==s) {
if (length(setdiff(numbers, hoge)) != 0) {
print(hoge)
}
}
}
数列をランダムに生成して100万回の確認をしますが、何度実行してもNが8以下の場合は何も表示されないので、おそらく「総和と総積が一致すれば、1~Nは一度ずつ登場している」といえそうです。
ところが、Nが9以上になると話が変わってきます。たとえばN=10のときの「2 7 10 5 4 9 4 4 1 9」という数列は
> sum(c(2, 7, 10, 5, 4, 9, 4, 4, 1, 9))
[1] 55
> prod(c(2, 7, 10, 5, 4, 9, 4, 4, 1, 9))
[1] 3628800
のように1~10が一回ずつ出てくる時と同じ値になります。N=20までは確認し、いずれも何かしらの数列が表示されましたので、少なくともNが9~20のときには「総和と総積の一致」は重複・不足の確認には使用できないことがわかりました。21以上のNについても同様だと予想したのですが、これ、どこかで証明されてるんですかね。