パーマネントを計算する

• 昨日までの記事で「すべての順列」について合算したかった
• 行列のパーマネントの計算であることがわかった(こちら)
• Wikiには小さい行列用の計算アルゴリズムRyserの方法が出ている
• Nはサイズ、P.Setは{1,2,...,N}のべき集合

• Rで実装しよう

# Ryser
PermanentRyser<-function(A){
	n<-length(A[,1])
	p<-0
	s<-as.set(1:n)
	for(i in 1:n){
		scomb<-set_combn(s,i)
		#print(length(scomb))
		c<-(-1)^i	
		sumSameLen<-0
		for(j in scomb){
			#print(j)
			tmpprod<-1
			for(k in 1:n){
				tmpsum<-0
				#print(k)
				for(l in j){
					#print(l)
					tmpsum<-tmpsum+A[k,l]
				}
				tmpprod<-tmpprod*tmpsum
			}
			sumSameLen<-sumSameLen+tmpprod
		}
		p<-p+c*sumSameLen
	}
	p*(-1)^n
}
# 検算用、「地道な計算」
PermanentBeta<-function(A){
	n<-length(A[,1])
	perms<-permutations(n,n)
	p<-0
	for(i in 1:length(perms[,1])){
		t<-1
		for(j in 1:n){
			t<-t*A[j,perms[i,j]]
		}
		p<-p+t
	}
	p
}
# Ryserの方法はN=16くらいまで計算できそう
# 地道な計算はN=9くらいまで、かな
N<-10
M<-matrix(runif(N^2),N,N)

PermanentRyser(M)
if(N<10){
	PermanentBeta(M)

}
print(M)