## Tri-Partitions

### November 15, 2019

We first partition the input into three lists based on their congruence mod 3. Two items cannot appear in succession if one of them is congruent to 1 mod 3 and the other is congruent to 2 mod 3, or if both of them are congruent to 0 mod 3. Then, we construct the output with alternating 1s and 0s, followed by alternating 2s and 0s, with a 0 in between:

```(define (f xs)
(let loop ((xs xs) (zeroes (list)) (ones (list)) (twos (list)))
(if (pair? xs)
(cond ((= (modulo (car xs) 3) 0)
(loop (cdr xs) (cons (car xs) zeroes) ones twos))
((= (modulo (car xs) 3) 1)
(loop (cdr xs) zeroes (cons (car xs) ones) twos))
(else (loop (cdr xs) zeroes ones (cons (car xs) twos))))
(if (and (null? zeroes) (pair? ones) (pair? twos)) #f ; no zero separator
(if (null? zeroes) (append ones twos)
(let loop ((saved (car zeroes)) (zeroes (cdr zeroes))
(ones ones) (twos twos) (zs (list)))
(cond ((and (null? zeroes) (null? ones) (null? twos))
(if saved (cons saved zs) zs))
((and (pair? zeroes) (pair? ones))
(loop saved (cdr zeroes) (cdr ones) twos
(cons (car ones) (cons (car zeroes) zs))))
((pair? ones)
(loop saved zeroes (cdr ones) twos (cons (car ones) zs)))
(saved (loop #f zeroes ones twos (cons saved zs)))
((and (pair? twos) (pair? zeroes))
(loop saved (cdr zeroes) ones (cdr twos)
(cons (car zeroes) (cons (car twos) zs))))
((pair? twos)
(loop saved zeroes ones (cdr twos) (cons (car twos) zs)))
(else #f)))))))) ; leftover zeroes```

Here are some examples:

```> (f '(0 0 0))
#f
> (f '(0 0 1))
(0 1 0)
> (f '(0 0 2))
(0 2 0)
> (f '(0 1 1))
(0 1 1)
> (f '(0 2 2))
(2 2 0)
> (f '(1 1 1))
(1 1 1)
> (f '(2 2 2))
(2 2 2)
> (f '(1 1 2))
#f
> (f '(0 1 2))
(2 0 1)
> (define xs (map (lambda (x) (randint 100)) (range 20)))
> xs
(2 67 65 71 86 83 12 17 9 30 42 61 33 68 57 30 74 42 41 51)
> (f xs)
(2 65 71 12 86 9 83 30 17 42 68 33 74 57 41 51 67 30 61 42)
> (map (lambda (x) (modulo x 3)) (f xs))
(2 2 2 0 2 0 2 0 2 0 2 0 2 0 2 0 1 0 1 0)```

You can run the program at https://ideone.com/v6b63R.

Pages: 1 2

### 11 Responses to “Tri-Partitions”

1. matthew said

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:

```-- sequences with i 0's, j 1's, k 2's with:
-- 0 and 0 not adjacent
-- 1 and 2 not adjacent

-- f0 i j k - sequences beginning 0
-- f1 i j k - sequences beginning 1
-- f2 i j k - sequences beginning 2
-- f  i j k - all sequences

-- 0 is followed either by nothing or by 1 or by 2
f0 1 0 0 = []
f0 i j k | j + k + 1 < i = []
f0 i j k | i > 0 = map (0:) (f1 (i-1) j k ++ f2 (i-1) j k)
f0 i j k = []

-- 1 is followed by nothing or by 0 or by 1
f1 0 1 0 = []
f1 i j k | j + k < i = []
f1 i j k | j > 0 = map (1:) (f0 i (j-1) k ++ f1 i (j-1) k)
f1 i j k = []

-- 2 is followed by nothing or by 0 or by 2
f2 0 0 1 = []
f2 i j k | j + k < i = []
f2 i j k | k > 0 = map (2:) (f0 i j (k-1) ++ f2 i j (k-1))
f2 i j k = []

f i j k = f0 i j k ++ f1 i j k ++ f2 i j k

main = mapM_ putStrLn (map (map ("012"!!)) (f 4 2 2))
```
```\$ runghc tripartition.hs
01010202
01010220
01020102
01020201
01022010
01102020
02010102
02010201
02011020
02020101
02020110
02201010
10102020
10201020
10202010
20101020
20102010
20201010
```
2. matthew said

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).

3. Daniel said

Here’s a solution in Python.

```from collections import defaultdict, deque

def tripartition(l):
d = defaultdict(list)
for x in l: d[x % 3].append(x)
out = deque()
if d: out.append(d.pop())
while d:
out.appendleft(d.pop())
if d: out.appendleft(d.pop())
while d and (not out or out[-1] != 1):
out.append(d.pop())
if d: out.append(d.pop())
return list(out) if len(out) == len(l) else None

tests = [
[0, 0, 0],
[0, 0, 1],
[0, 0, 2],
[0, 1, 1],
[0, 2, 2],
[1, 1, 1],
[2, 2, 2],
[1, 1, 2],
[0, 1, 2],
[2, 67, 65, 71, 86, 83, 12, 17, 9, 30, 42, 61, 33, 68, 57, 30, 74, 42, 41, 51],
]

for test in tests:
print(f'in:  {test}')
print(f'out: {tripartition(test)}')
print()
```

Output:

```in:  [0, 0, 0]
out: None

in:  [0, 0, 1]
out: [0, 1, 0]

in:  [0, 0, 2]
out: [0, 2, 0]

in:  [0, 1, 1]
out: [1, 1, 0]

in:  [0, 2, 2]
out: [0, 2, 2]

in:  [1, 1, 1]
out: [1, 1, 1]

in:  [2, 2, 2]
out: [2, 2, 2]

in:  [1, 1, 2]
out: None

in:  [0, 1, 2]
out: [1, 0, 2]

in:  [2, 67, 65, 71, 86, 83, 12, 17, 9, 30, 42, 61, 33, 68, 57, 30, 74, 42, 41, 51]
out: [30, 67, 42, 61, 51, 41, 57, 74, 33, 68, 42, 17, 30, 83, 9, 86, 12, 71, 65, 2]
```
4. Daniel said

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

```def tripartition(l):
d = {0: [], 1: [], 2: []}
for x in l: d[x % 3].append(x)
out = []
if d: out.append(d.pop())
while d:
out.append(d.pop())
if d: out.append(d.pop())
out.reverse()
while d and (not out or out[-1] != 1):
out.append(d.pop())
if d: out.append(d.pop())
return out if len(out) == len(l) else None
```
5. matthew said

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:

```import numpy

def solve(I,J,K,atype=int):
a = numpy.zeros([3,I+1,J+1,K+1],atype)
a[0,1,0,0] = a[1,0,1,0] = a[2,0,0,1] = 1
for n in range(2,I*J*K+1):
for i in range(0,min(I+1,n+1)):
for j in range(max(0,n-i-K),min(J+1,n-i+1)):
k = n-i-j # k = n-i-j <= K so n-i-K <= j
if i > 0: a[0,i,j,k] = a[1,i-1,j,k] + a[2,i-1,j,k]
if j > 0: a[1,i,j,k] = a[0,i,j-1,k] + a[1,i,j-1,k]
if k > 0: a[2,i,j,k] = a[0,i,j,k-1] + a[2,i,j,k-1]
return a[0,I,J,K]+a[1,I,J,K]+a[2,I,J,K]

def solveseq(s):
a = [0,0,0]
for i in s: a[i%3] += 1
return solve(*a)

s = [2,67,65,71,86,83,12,17,9,30,42,61,33,68,57,30,74,42,41,51]
print(solveseq(s)) # 4432
print(solve(9,2,9)) # also 4432
print(solve(10,10,10)) # 41649556
print(solve(50,50,50,object)) # 11648269955901473622920989454259616785721696
print(solve(50,50,50,numpy.float64)) # 1.1648269955901474e+43
```
6. matthew said

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:

```import numpy
import random
import time

def maketable(I,J,K,atype=int):
a = numpy.zeros([3,I+1,J+1,K+1],atype)
a[0,1,0,0] = a[1,0,1,0] = a[2,0,0,1] = 1
for n in range(2,I+J+K+1):
# n = i+j+k <= i+J+K so n-J-K <= i
for i in range(max(0,n-J-K),min(I,n)+1):
# k = n-i-j <= K so n-i-K <= j
for j in range(max(0,n-i-K),min(J,n-i)+1):
k = n-i-j
if i > 0: a[0,i,j,k] = a[1,i-1,j,k] + a[2,i-1,j,k]
if j > 0: a[1,i,j,k] = a[0,i,j-1,k] + a[1,i,j-1,k]
if k > 0: a[2,i,j,k] = a[0,i,j,k-1] + a[2,i,j,k-1]
return a

def select(*s):
x,t,p = random.random(),sum(s),0
for i in range(len(s)-1):
p += s[i]
if x < p/t: return i
return len(s)-1

def randseq(I,J,K):
a = maketable(I,J,K,numpy.float64)
while True:
i,j,k = I,J,K
n = [0,1,2][select(a[0,i,j,k],a[1,i,j,k],a[2,i,j,k])]
s = [n]
for _ in range(i+j+k-1):
if n == 0:   i -= 1; n = [1,2][select(a[1,i,j,k],a[2,i,j,k])]
elif n == 1: j -= 1; n = [0,1][select(a[0,i,j,k],a[1,i,j,k])]
elif n == 2: k -= 1; n = [0,2][select(a[0,i,j,k],a[2,i,j,k])]
s += [n]
yield s

s = randseq(9,2,9)
for _ in range(10):
for n in next(s): print("🍎🍋🍊"[n],end="",flush=True); time.sleep(0.05)
print(); time.sleep(0.5)
```

Typical output:
🍎🍊🍎🍊🍎🍊🍊🍊🍎🍊🍎🍋🍎🍊🍊🍎🍋🍎🍊🍎
🍎🍊🍎🍋🍎🍊🍎🍋🍎🍊🍎🍊🍊🍊🍎🍊🍊🍎🍊🍎
🍊🍎🍊🍎🍊🍎🍊🍎🍋🍎🍊🍎🍊🍊🍊🍎🍋🍎🍊🍎
🍋🍎🍊🍎🍊🍎🍊🍎🍊🍎🍊🍎🍊🍊🍎🍋🍎🍊🍎🍊
🍎🍊🍊🍊🍎🍊🍎🍋🍎🍊🍎🍊🍎🍊🍊🍎🍋🍎🍊🍎
🍊🍎🍊🍎🍋🍎🍊🍎🍊🍎🍊🍎🍊🍎🍊🍊🍎🍋🍎🍊
🍎🍋🍎🍊🍊🍊🍎🍊🍎🍊🍊🍎🍊🍎🍊🍎🍋🍎🍊🍎
🍎🍊🍎🍊🍎🍊🍊🍎🍋🍎🍊🍎🍊🍎🍊🍎🍋🍎🍊🍊
🍎🍊🍎🍊🍎🍋🍎🍊🍎🍊🍊🍎🍊🍎🍊🍎🍋🍎🍊🍊
🍎🍊🍊🍎🍊🍊🍎🍋🍎🍊🍎🍋🍎🍊🍎🍊🍊🍎🍊🍎

7. matthew said

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

8. matthew said

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).

```def check(n,m,counts):
# return True iff m can follow n, given the item counts
if n == 0: return m != 0
if n == m: return counts+counts >= counts
if m == 0: return counts > 1 or counts == 0 or counts == 0
if n is None: return counts+counts >= counts
return False

def findnext(s,t,counts):
for i in range(len(s)):
n = t[-1] if t else None
if check(n,s[i],counts):
counts[s[i]] -= 1
t.append(s[i])
del s[i]
return True
return False

def isvalid(counts):
if counts == 0: return counts == 0 or counts == 0
else: return counts+counts >= counts-1

def f(s):
t,counts = [],*3
for i in s: counts[i] += 1
valid = isvalid(counts)
while findnext(s,t,counts):
pass
assert not valid or not s
if not s: return "".join("▮○□"[i] for i in t)

print(f([0,0,1]))
print(f([0,1,2]))
print(f([0,0,0,1]))
print(f([0,0,0,0,0,0,0,1,2,1,1,1,1]))
print(f([1,2,1,1,1,1,0,0,0,0,0,0,0]))
print(f([1,2,1,2,1,2,0]))
print(f([2,1,2,2,2,2,0,2,0,0,0,1,0,2,0,0,2,0,2,0]))
```

Output (hoping the Unicode chars come out):

```▮○▮
○▮□
None
▮○▮□▮○▮○▮○▮○▮
▮○▮□▮○▮○▮○▮○▮
○○○▮□□□
□□□▮○▮□▮□▮□▮○▮□▮□▮□▮
```
9. matthew said

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

```def check(n,m,counts):
n,m = n%3 if n else n,m%3
if n == 0: return m != 0
if n == m: return counts+counts >= counts
if m == 0: return counts > 1 or counts == 0 or counts == 0
if n is None: return counts+counts >= counts
return False

def findnext(s,t,counts):
for i in range(len(s)):
n = t[-1] if t else None
if check(n,s[i],counts):
counts[s[i]%3] -= 1
t.append(s[i])
del s[i]
return True

def f(s):
t,counts = [],*3
for i in s: counts[i%3] += 1
while findnext(s,t,counts): pass
if not s: return t

def show(s): return "".join("▮○□"[i%3] for i in s) if s else None

s = [2,67,65,71,86,83,12,17,9,30,42,61,33,68,57,30,74,42,41,51]
t = f(s[:]) # Duplicate s
print(s)
print(t)
print(show(s))
print(show(t))
```

Output:

```[2, 67, 65, 71, 86, 83, 12, 17, 9, 30, 42, 61, 33, 68, 57, 30, 74, 42, 41, 51]
[2, 65, 71, 12, 67, 9, 86, 30, 83, 42, 17, 33, 61, 57, 68, 30, 74, 42, 41, 51]
□○□□□□▮□▮▮▮○▮□▮▮□▮□▮
□□□▮○▮□▮□▮□▮○▮□▮□▮□▮
```
10. matthew said

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

```def check(n,m,counts):
n,m = n%3 if n else n,m%3
if n == 0: return m != 0
if n == m: return counts+counts >= counts
if m == 0: return counts > 1 or counts == 0 or counts == 0
if n is None: return counts+counts >= counts
return False

def g(s):
counts = *3
for n in s: counts[n%3] += 1
print([],s)
for i in range(len(s)):
for j in range(i,len(s)):
if check(None if i == 0 else s[i-1],s[j],counts):
s[i],s[i+1:j+1] = s[j],s[i:j]
counts[s[i]%3] -= 1
break
else: return None
print(s[:i+1],s[i+1:])
return s

g([2,67,65,71,86,83,12,17,9,30,42,61,33,68,57,30,74,42,41,51])
```

This time, we print a trace of the computation:

```[] [2, 67, 65, 71, 86, 83, 12, 17, 9, 30, 42, 61, 33, 68, 57, 30, 74, 42, 41, 51]
 [67, 65, 71, 86, 83, 12, 17, 9, 30, 42, 61, 33, 68, 57, 30, 74, 42, 41, 51]
[2, 65] [67, 71, 86, 83, 12, 17, 9, 30, 42, 61, 33, 68, 57, 30, 74, 42, 41, 51]
[2, 65, 71] [67, 86, 83, 12, 17, 9, 30, 42, 61, 33, 68, 57, 30, 74, 42, 41, 51]
[2, 65, 71, 12] [67, 86, 83, 17, 9, 30, 42, 61, 33, 68, 57, 30, 74, 42, 41, 51]
[2, 65, 71, 12, 67] [86, 83, 17, 9, 30, 42, 61, 33, 68, 57, 30, 74, 42, 41, 51]
[2, 65, 71, 12, 67, 9] [86, 83, 17, 30, 42, 61, 33, 68, 57, 30, 74, 42, 41, 51]
[2, 65, 71, 12, 67, 9, 86] [83, 17, 30, 42, 61, 33, 68, 57, 30, 74, 42, 41, 51]
[2, 65, 71, 12, 67, 9, 86, 30] [83, 17, 42, 61, 33, 68, 57, 30, 74, 42, 41, 51]
[2, 65, 71, 12, 67, 9, 86, 30, 83] [17, 42, 61, 33, 68, 57, 30, 74, 42, 41, 51]
[2, 65, 71, 12, 67, 9, 86, 30, 83, 42] [17, 61, 33, 68, 57, 30, 74, 42, 41, 51]
[2, 65, 71, 12, 67, 9, 86, 30, 83, 42, 17] [61, 33, 68, 57, 30, 74, 42, 41, 51]
[2, 65, 71, 12, 67, 9, 86, 30, 83, 42, 17, 33] [61, 68, 57, 30, 74, 42, 41, 51]
[2, 65, 71, 12, 67, 9, 86, 30, 83, 42, 17, 33, 61] [68, 57, 30, 74, 42, 41, 51]
[2, 65, 71, 12, 67, 9, 86, 30, 83, 42, 17, 33, 61, 57] [68, 30, 74, 42, 41, 51]
[2, 65, 71, 12, 67, 9, 86, 30, 83, 42, 17, 33, 61, 57, 68] [30, 74, 42, 41, 51]
[2, 65, 71, 12, 67, 9, 86, 30, 83, 42, 17, 33, 61, 57, 68, 30] [74, 42, 41, 51]
[2, 65, 71, 12, 67, 9, 86, 30, 83, 42, 17, 33, 61, 57, 68, 30, 74] [42, 41, 51]
[2, 65, 71, 12, 67, 9, 86, 30, 83, 42, 17, 33, 61, 57, 68, 30, 74, 42] [41, 51]
[2, 65, 71, 12, 67, 9, 86, 30, 83, 42, 17, 33, 61, 57, 68, 30, 74, 42, 41] 
[2, 65, 71, 12, 67, 9, 86, 30, 83, 42, 17, 33, 61, 57, 68, 30, 74, 42, 41, 51] []
```