# Magic Sequence

## Problem

A magic sequence of length n is a sequence of integers x0 . . xn-1 between 0 and n-1, such that for all i in 0 to n-1, the number i occurs exactly xi times in the sequence. For instance, 6,2,1,0,0,0,1,0,0,0 is a magic sequence since 0 occurs 6 times in it, 1 occurs twice, ... – CSPLib

## Code

``` 1 require 'rubygems'
2 require 'gecoder'
3
4 # Solves the magic sequence problem.
5 class MagicSequence
6   include Gecode::Mixin
7
8   # n is the length of the sequence.
9   def initialize(n)
10     # The i:th variable represents the value of the i:th element in the
11     # sequence.
12     sequence_is_an int_var_array(n, 0...n)
13
14     # The basic requirement to qualify as a magic sequence.
15     n.times{ |i| sequence.count(i).must == sequence[i] }
16
17     # The following are implied constraints. They do not affect which
18     # assignments are solutions, but they do help prune the search space
19     # quicker.
20
21     # The sum must be n. This follows from that there are exactly n elements and
22     # that the sum of all elements are the number of occurrences in total, i.e.
23     # the number of elements.
24     sequence.sum.must == n
25
26     # sum(seq[i] * (i-1)) must equal 0 because sum(seq[i]) = n as seen above
27     # and sum(i*seq[i]) is just another way to compute sum(seq[i]). So we get
28     # sum(seq[i] * (i-1)) = sum(seq[i]) - sum(i*seq[i]) = n - n = 0
29     sequence.zip((-1...n).to_a).map{ |element, c| element*c }.sum.must == 0
30
31     branch_on sequence, :variable => :smallest_degree, :value => :split_max
32   end
33
34   def to_s
35     sequence.values.join(', ')
36   end
37 end
38
39 class Array
40   # Sums all the elements in the array using #+ .
41   def sum
42     inject{ |sum, element| sum + element }
43   end
44 end
45
46 puts MagicSequence.new(500).solve!.to_s
```

## Output

```496, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0
```

## Notes

This might be a bit boring problem to use constraint programming on as the pattern for sequences is obvious for n >= 7, making it trivial to construct an efficient algorithm.