本履歴

購入した古本の履歴と時々プログラミング

Identifies mirrored and rotated one

したがって面白くするため、回転・鏡像を含めて同一視した場合にどのくらいになるか手で数えてみた。なんとなく偶数になると思っていたが、N=4の場合は7という数字が出てきて不思議な感じ。これは配置によって回転・鏡像変換8通り全てが異なる順列になる場合や1234=4321のように2つしか同一視できないなど結構複雑だ。そこで早速プログラムを組んでカウントしてみた。1,1,2,7,23,115まで求めて後はOEISに突っ込めばやはり誰かが既に求めていた(https://oeis.org/A000903
この数列に関する面白い結果は特になさそうでちょっと残念。

#飛車を相互にアタックしないように配置するパズル
#回転鏡像含め同一視した中でいくつの場合があるか数える
#0-indexed
#O(N!)

def rotate(a)
	a.each_with_index.sort_by(&:first).reverse.map(&:last)
end

def mirror(a)
	table=[*0...a.size].reverse.each_with_index.to_a
	a.map{|v|table[v]}
end

N=6
count=0
h={}
[*0...N].permutation(N).each{|perm|
	next if h[perm]
	count+=1
	until h[perm]
		h[perm]=true
		perm=rotate(perm)
	end
	perm=mirror(perm)
	until h[perm]
		h[perm]=true
		perm=rotate(perm)
	end	
}

p count