## Tri-Partitions

### November 15, 2019

We have a fun little task for your Friday lunch hour:

Given an array of integers, rearrange the integers so no two consecutive integers have a sum that is divisible by 3, or indicate that such an arrangement is not possible.

Your task is to write a program to rearrange an array of integers as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

As you say, it comes down to taking the integers mod 3, then ensuring that 0 is never next to 0 and 1 is never next to 2. It’s a nice exercise to find all the ways this can be done, given the number of integers with each modulus. Here’s some Haskell, it would benefit from memoization or dynamic programming:

Incidentally, for your example with 9 0’s and 2’s and just 2 1’s, there are 4322 different possible orderings, from 01010202020202020222 to 22202020202020201010 (your ordering and the mirror image of the first).

Here’s a solution in Python.

Output:

Here’s a similar solution to the one I posted earlier, but without the dependence on the collections module.

Here’s a dynamic programming solution in Python that just computes the number of possible sequences. It’s not to difficult to adapt to compute the sequences themselves. solveseq(s) gives the number of rearrangements (that preserve the ordering for each modulus class) for s. Use numpy for convenient multidimensional arrays – we can also specify the array type, type ‘object’ gives us bignums, or we can use a floats to avoid overflow in bigger problems:

We can also use the dynamic programming array to generate uniformly random sample sequences (also fixing a bug with the range for n on line 6 – should be I+J+K+1, and tightening up the bounds on i). Also make the output fruitier:

Typical output:

๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐

๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐

๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐

๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐

๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐

๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐

๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐

๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐

๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐

๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐

Once again, screwed by WordPress code formatting: that should be just ‘print(“๐๐๐”[n],end=””,flush=True)’

A couple of solutions in Racket.

Another Python solution: this one attempts to rearrange the input list (of 0,1,2) to satisfy the ordering requirements, but making a fairly minimal set of changes. Strategy is to build up result list t, taking first item from s that can be appended to t, also ensuring that a solution is still possible with the remaining items – specifically, that there are enough 1’s and 2’s to keep the 0’s separated (and that if there is only one 0 remaining, it doesn’t get appended when both 1’s and 2’s remain).

Output (hoping the Unicode chars come out):

A variation, that takes doesn’t require the mod 3 to already be done:

Output:

And here is an in-place version of the above – nice opportunity to use python range assignments & for-else:

This time, we print a trace of the computation: