モンテカルロ法で次元の呪い
概要 モンテカルロ法で次元の呪いを体験するを読んで,自分も最近似たような体験をしたことを思い出したので,メモしておく. 問題 $N$行$N$列の行列の各要素に$1$から$N$までの数字が入っているものとする. 各列,各行に数字の重複を許さない行列は全部で何通りあるかを推定せよ. はじめ,ランダムに$1$から$N$までの数字を格納した2次元配列を用意して,各行と列に重複がないかチェックし,重複がない試行の確率を求める方法をとった.以下,作成したPythonのコード(クソコードなのはご愛嬌). #! /usr/bin/env python # -*- coding: utf-8 -*- from numpy.random import * def check_overlap(args): for i in range(len(args)): if len(set(args[:,i])) < len(args[:,i]) or len(set(args[i,:])) < len(args[ i,:]): return False return True if __name__ == '__main__': N=4 #size of matrix M=100000000 #number of trial randarray = randint(1,N+1,(N,N,M)) count=0 for i in range(M): if check_overlap(randarray[:,:,i])==True: count = count+1 if i%100000==0: print(M-i,count) print( N**(N*N) * count / M ) この方法では,$N=4$あたりで現実的な解が得られなくなってしまった. より計算時間を減らすために,$1$から$N$までが格納された1次元配列の要素をランダムにシャッフルし,それを$N$個積み重ねることで,重複をチェックする方向を一方向だけにする方法をとった. ...