qb2.rb

#!/usr/bin/ruby

def derange(p1, p2)
	
	(0...($p.size - 1)).each \
	{
		|i|
		next if (p1[i] != p2[i])
		
		l = ((i + 1)...$p.size).to_a.select { |x| p1[i] != p1[x] }
		return 0 if (l.empty?)

		j = l[rand(l.size)]
		p1[i], p1[j] = p1[j], p1[i]
	}
	return (p1[-1] != p2[-1]) ? 1 : 0
end

def derange2()
	c = 0
	c += 1 while derange(p1 = $p.dup, p2 = $p.shuffle) != 1
	return p1, p2
end

def dispersion(p)
	
	a = {}
	p.each_with_index { |k, i| a[k] = [] if (a[k].nil?); a[k] += [i] }
	m = nil
	a.each \
	{
		|k, v|
		next if (v.size == 1)
		m1 = (0...(v.size - 1)).to_a.map { |i| [v[i + 1] - v[i], v[i], v[i + 1]] }.min
		m = m.nil? ? m1 : [m1, m].min
	}
	return m + [p[m[1]]]
end

def dispersion2(p1, p2)
	
	d1 = dispersion(p1) + [p1]
	d2 = dispersion(p2) + [p2]
	return [d1, d2].min
	
end

def cut(a, x, y)
	return [] if (x > y)
	return a[x..y]
end

def swap(p, p0, j, x)
	p[x], p[j] = p[j], p[x]
	p0[x], p0[j] = p0[j], p0[x]
end

def disperse(pa, pb, w)

	d, x, y, v, pc = dispersion2(pa, pb)
	a = (0...pa.size).to_a
	
	loop \
	{
		m = (x + y) / 2.0
#		p([d, x, y, v])

		l = cut(a, 0, x - d - 1)
		r = cut(a, y + d + 1, a.size - 1)
		
		lr = (l + r).select { |t| pc[t] != (v) }.sort_by { |t| (t - m).abs }.reverse

		f = false
		lr.each \
		{
			|j|
			pa2 = pa.dup
			pb2 = pb.dup
			
			z = w ? ((j < m) ? x : y) : [x, y].min_by { |t| (m - t).abs }
			
			swap(pa2, pb2, j, z)
			
			d2, x2, y2, v2, pc2 = dispersion2(pa2, pb2)
			if (d2 > d || (d2 == d && x2 > x)) then
				f = true
				pa, pb, d, x, y, v, pc = pa2, pb2, d2, x2, y2, v2, pc2
				break
			end
		}
		return pa, pb, d if (!f)
	}


end

def derangesperse(w)
	

	t = 0
	c = 1000
	mx = nil
	mn = nil
	c.times \
	{
		p1, p2 = derange2()
		p1, p2, d = disperse(p1, p2, w)
		t += d
		mx = mx.nil? ? d : [d, mx].max
		mn = mn.nil? ? d : [d, mn].min
	}
	p([t.to_f / c, mn, mx])
	
end

def stat(m, p)

	t = 0
	c = 1000
	c.times { t += derange(p.dup, p.shuffle) }
	printf("%s\t%f\n", m, t.to_f / c)
end

$p = ['Li'] * 4 + ['Sc'] * 4 + ['Hi'] * 4 + ['Fi'] * 3 + ['RM'] * 2 + ['So', 'Ge', 'Cu']

stat('c', $p.reverse)
stat('b', $p.shuffle)
stat('a', $p)

derangesperse(false)
derangesperse(true)