モンテカルロ法で次元の呪い

概要

モンテカルロ法で次元の呪いを体験するを読んで，自分も最近似たような体験をしたことを思い出したので，メモしておく．

問題

$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$個積み重ねることで，重複をチェックする方向を一方向だけにする方法をとった．

#! /usr/bin/env python
# -*- coding: utf-8 -*-
import numpy as np
import math 

def shuffle_array(args):
	for i in range(len(args)):
		np.random.shuffle(args[i,:])

def check_overlap(args):
	for i in range(len(args)):
		if len(set(args[:,i])) < len(args[:,i]):
			return False
	return True

if __name__ == '__main__':
	N=6
	M=100000000
	count=0
	array = np.zeros([N,N])
	for i in range(N):
		array[i,:] = np.arange(N)+1
	for i in range(M):
		if i%10000==0:
			print(M-i,count)
		shuffle_array(array)
		if check_overlap(array)==True:
			count = count+1
	print( math.factorial(N)**N * count / M )

こちらの方法では，$N=6$あたりまでであれば，時間をかければそれらしい解が得られるようになった．
しかし，依然として次元の呪いを回避出来たわけではない．

結論

誰かもっといい方法を教えて下さい．