### 2015 in review

The WordPress.com stats helper monkeys prepared a 2015 annual report for this blog.

Here’s an excerpt:

Matrices with gapless partial sums of permuted integer rows

The WordPress.com stats helper monkeys prepared a 2015 annual report for this blog.

Here’s an excerpt:

The WordPress.com stats helper monkeys prepared a 2014 annual report for this blog.

Here’s an excerpt:

A San Francisco cable car holds 60 people. This blog was viewed about

590times in 2014. If it were a cable car, it would take about 10 trips to carry that many people.

The previous post described the restriction given by partial sums – depicted by red points – which appear on exactly one row. Looking at these pictures, one sees, that there must be done more: Because of the type of the matrix also the partial sums of one row have to avoid the mandatory (green) points of all other rows. For the time being this has been implemented for the upper – right hand side – mandatory points. This is visible by the fact, that no longer any cyan colored point is in the same vertical with a green point on the right hand side.

The former example for Z = 10 looks now as follows

whereas the former example for Z = 22 looks now so:

Interestingly, a red point on row 18 remains without cyan filling, which means that this point cannot be reached if the restrictions from green points on the right hand side are respected. By the way, the restriction implementation is for the sake of simplicity currently a bit too prohibitive.

Finally let’s also look at the Z = 30 example

What remains to do? On the left hand side there are still cyan points in the same vertical with green points. These restrictions must be implemented too.

So, progress is slow, but not zero.

Let’s still muse a bit about the labyrinth the algorithm faces. In this post’s illustrations, green points are as before mandatory, given by the current state of affairs. Black points are possible partial sums without respect to permutations. Cyan point fillings are partial sums appearing to pass the enforced restrictions. As red circles as before point to partial sums which must be reached on that particular row, it is good, that there is no red point without cyan filling. The next good thing is: Only on rows with red circles there are black points without cyan filling left – the restrictions do work, but there are still too few restrictions to be efficient.

Of course one has to balance between the costs of uneducated searches vs. the costs of strict restriction computations …

The search algorithm takes that continuation which has no obvious flaw and the most continuation possibilities for the next step. If no continuation can be found, it stores the constellation in order to never take it again and steps back to take there another continuation which has not yet failed. This works fine for lower numbers of rows (Z < 20) but fails to be operative for higher numbers of rows (Z > 20).

Why?

The point lies in the decision about a flaw of a continuation: On each row one has the remaining, not yet used numbers and can build all possible partial sums on top of the already distributed numbers. The union of all partial sums from all rows must contain all still missing partial sums in the Z x 2 (Z – 1) matrix. But on each row only one permutation of unused numbers can be realized in the end. How to determine it? One looks for partial sums which appear on exactly one row, they constrain the variety of possible permutations. In the pictures the red points mark a partial sum which appears on exactly one row. The green points mark the maximal partial sum on a row. The black points are all possible partial sums without the need to be consistent with a single permutation. The ordinate shows the row number, the abscissa shows the partial sums. For Z = 10 one sees a picture like

showing 6 constraints on 10 rows, enough to complete the search rather fast, in a few thousand steps. For Z = 22 it looks a bit worse

there are only 3 constraints on 22 rows and in the case of 30 rows one has for example

only 5 constraints which let the algorithm run for millions of steps without finding the right way.

So one has to find more constraints in order to find examples of matrices with row numbers bigger than 20.

Hi over there, this blog muses about an exercise (May, 2012) at the *Ponder This* site of IBM Research.

The pages show examples for different row numbers Z, starting with the minimum Z = 2 but aiming for preferably big row numbers, whereas the posts consider issues with the example generation.

Take time and step in a matrix from one partial sum to the next. For small matrices this is obvious and rather trivial, for the bigger ones it needs quite an amount of memory, even if the partial sums are indicated.

*Enjoy!*