Facebook puzzle - SuperPatterns the solution

Here's my solution to the facebook superpatterns puzzle. The actual puzzle is available here. The solution will follow a pattern that I used to solve the GridFlip puzzle, again from facebook.

This solution is completely based on information on superpatterns available from this wikipaedia article

Identify characteristics of the problem space and define rules that will reduce it.
1. The relative weights of the numbers in the superpattern are important, the actual numbers dont matter. What I mean by that is, if [25314] is a superpattern, then adding one to all numbers we get [36425] which is also a super pattern. Based on this, we can safely assume that if n is the length of the super pattern, the possible numbers in the pattern can only be 1 to n.

2. If [25314] is a super pattern, then inverse [41352] is also a super pattern. This true because if 123 is present in a subpattern, 321 is also present in the subpattern ??

3. There can be no repetitions.

4. Minimum lenght of a super patterns with a k-subpattern is k+k -1 (The inclusion and exclusion principle in the wiki page).

Based on the above principles. The size of a problem space for a k-subpattern (subpattern of size k) will be ..
*Minimum lenght of the superpattern n = 2*k -1.
*Number of possible number we can generate for n = n! (Assuming numbers are unique).
*Since the inverse is equal problem size = n!/2;

so if we have a 3-subpattern (k=3), which has 3! permutations, we have to make sure that each of the n!/2 possible solutions satisfy the k! subpatterns.

=> Complexity of the algorithm = (2*k-1)!/2 * k!

Using the above rules, I constructed a base solution set, assuming k =3 -> n =5.
The solution set would look like this.
12345, 12354 ... 54321.

*We can further reduce the problem by adding more constraints on the possible values for each number in the superpattern. What I mean by that is ..
lets say x1, x2, x3 .. xn are the number in the superpattern and if y1, y2, y3 ..yk are the elements in the subpattern. Each subpattern must have k number => the first number in the subpattern y1 can be selected from numbers x1- xl (where l = (n-k) +1), similarly y2 can be selected from x2 - xl (where l = (n-k) +2).
Here's an example .. if [25314] is the superpattern the subpatterns of length 3 can be
214, 514, 314 => the first number in the subpatterns is selected from 253.
254, 234, 214 => the first number in the subpatterns is selected from 531.

Output Rule.
*If you look at the subsets you will notice that the first number in the subset will have all possible relative values. What I mean is that for a 3-subset, the first number must be 1,2,3 (Relative weights). The same with the remaining numbers.

We now have a possilbe solution set.
Rules that we can impose on the solution set ie, the set of possible values for the first number in the subpattern must contain the largest in the sequence, the second largest in the sequence .. the smallest in the sequence ..

The solution:
Generate possible solutions and validate against the output rules.

Solution and source code to this puzzle comming soon ..

Find something wrong with this solution, or want to add something .. please add a comment or email me at my gm@il acccount blogtamma.