#!/usr/bin/ruby
#
# All interval problem in Gecode/R
#
# CSPLib problem number 7
# http://www.cs.st-andrews.ac.uk/~ianm/CSPLib/prob/prob007/index.html
# """
# Given the twelve standard pitch-classes (c, c#, d, ...), represented by
# numbers 0,1,...,11, find a series in which each pitch-class occurs exactly
# once and in which the musical intervals between neighbouring notes cover
# the full set of intervals from the minor second (1 semitone) to the major
# seventh (11 semitones). That is, for each of the intervals, there is a
# pair of neigbhouring pitch-classes in the series, between which this
# interval appears. The problem of finding such a series can be easily
# formulated as an instance of a more general arithmetic problem on Z_n,
# the set of integer residues modulo n. Given n in N, find a vector
# s = (s_1, ..., s_n), such that (i) s is a permutation of
# Z_n = {0,1,...,n-1}; and (ii) the interval vector
# v = (|s_2-s_1|, |s_3-s_2|, ... |s_n-s_{n-1}|) is a permutation of
# Z_n-{0} = {1,2,...,n-1}. A vector v satisfying these conditions is
# called an all-interval series of size n; the problem of finding such
# a series is the all-interval series problem of size n. We may also be
# interested in finding all possible series of a given size.
# """
#
# Also see the MiniZinc model http://www.hakank.org/minzinc/all_interval.mzn
#
#
# This Gecode/R model below is a quite simple and direct approach to
# the problem.
#
# For n = 12, all 1328 solutions (no symmetry breaking) takes about 40 seconds.
# With symmetry breaking: 332 solutions in 12 seconds
#
# ....
#
# Model created by Hakan Kjellerstrand, hakank@bonetmail.com
# See also my Gecode/R page: http://www.hakank.org/gecode_r
#
require 'rubygems'
require 'gecoder'
STDOUT.sync = true
class AllInterval
include Gecode::Mixin
def initialize(n = 12)
x_is_an int_var_array(n, 1..n)
diffs_is_an int_var_array(n-1, 1..n-1)
x.must_be.distinct(:strength => :bounds)
diffs.must_be.distinct(:strength => :bounds)
(0..n-2).each{|k|
diffs[k].must.equal((x[k+1] - x[k]).abs, :strength => :bounds)
}
# symmetry breaking: for n=12 -> 332 solutions in 12 seconds
x[0].must < x[1]
diffs[0].must > diffs[n-2]
# another symmetry breaking: for n=12 -> 463 solutions in 16 seconds
# x[0].must < x[n-1]
# diffs[0].must < diffs[1]
branch_on x , :variable => :smallest_size, :value => :min
branch_on diffs, :variable => :smallest_size, :value => :min
end # end initialize
end # end class
n = (ARGV[0] || 12).to_i
n_sols = (ARGV[1] || 0).to_i
puts "n: #{n}"
all_interval = AllInterval.new(n)
num_solutions = 0
all_interval.each_solution{|s|
num_solutions += 1
# puts "\nSolution ##{num_solutions}\n";
puts "x: [#{s.x.values.join(',')}] diffs: [#{s.diffs.values.join(',')}]"
# s.search_stats.each{|w,v| puts "#{w}: #{v}"}
break if n_sols > 0 and num_solutions >= n_sols
}
puts "\nNumber of solutions: #{num_solutions}"