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.

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 = [[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 = [[1]]
    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 = [[2]]
    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[0]: out.append(d[0].pop())
        while d[1]:
            out.appendleft(d[1].pop())
            if d[0]: out.appendleft(d[0].pop())
        while d[2] and (not out or out[-1] != 1):
            out.append(d[2].pop())
            if d[0]: out.append(d[0].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[0]: out.append(d[0].pop())
        while d[1]:
            out.append(d[1].pop())
            if d[0]: out.append(d[0].pop())
        out.reverse()
        while d[2] and (not out or out[-1] != 1):
            out.append(d[2].pop())
            if d[0]: out.append(d[0].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[1]+counts[2] >= counts[0]
        if m == 0: return counts[0] > 1 or counts[1] == 0 or counts[2] == 0
        if n is None: return counts[1]+counts[2] >= counts[0]
        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] == 0: return counts[1] == 0 or counts[2] == 0
        else: return counts[1]+counts[2] >= counts[0]-1
    
    def f(s):
        t,counts = [],[0]*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[1]+counts[2] >= counts[0]
        if m == 0: return counts[0] > 1 or counts[1] == 0 or counts[2] == 0
        if n is None: return counts[1]+counts[2] >= counts[0]
        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 = [],[0]*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[1]+counts[2] >= counts[0]
        if m == 0: return counts[0] > 1 or counts[1] == 0 or counts[2] == 0
        if n is None: return counts[1]+counts[2] >= counts[0]
        return False
    
    def g(s):
        counts = [0]*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]
    [2] [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] [51]
    [2, 65, 71, 12, 67, 9, 86, 30, 83, 42, 17, 33, 61, 57, 68, 30, 74, 42, 41, 51] []
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: