Cut along the lines

Question

In this challenge you will take as input a non-empty list of binary values (these can be booleans or integers on the range 0-1), you should output all the ways to partition the list into non-empty sections such that no two adjacent equal values in the initial list are separated into different sections.

For example if the input is [1,1,0,0,1] then [1,1],[0,0,1] is a valid partition but [1,1,0],[0,1] is not since the adjacent 0s are divided.

This is code-golf so the goal is to minimize the size of your source code as measured in bytes.

Test cases

[1,0] ->
  [ [[1,0]]
  , [[1],[0]]
  ]
[1,1,1,1] ->
  [ [[1,1,1,1]]
  ]
[1,1,0,0,1] ->
  [ [[1,1,0,0,1]]
  , [[1,1],[0,0,1]]
  , [[1,1,0,0],[1]]
  , [[1,1],[0,0],[1]]
  ]

Answer 1

K (ngn/k), 22 bytes

{(&'+1,!2-1_=':x)_\:x}

Try it online!

1_=':x For pairs of adjacent values: are they equal?
2- 2 minus that. Gives 2s for the lines between sections and 1s in sections.
! odometer. Returns a matrix with all binary patterns bounded by the vector.
+1, prepend a 1 and transpose to have the binary patterns with leading 1s in the rows.
&' Get indices of 1s for each row.
(...)_\:x For each of those integer vectors, split the input at those indices.

Answer 2

Factor + math.combinatorics math.unicode, 81 bytes

[ dup 2 clump [ Σ 1 = ] arg-where 1 v+n all-subsets [ split-indices ] with map ]

Attempt This Online!

• dup 2 clump [ Σ 1 = ] arg-where 1 v+n get the indices of rising and falling edges
• all-subsets take all the subsets of that
• [ split-indices ] with map split the input according to each of these

Answer 3

Jelly, 8 bytes

ITŒP‘œṖ€

A monadic Link that accepts a list of ones and zeros and yields a list of the valid partitions.

Try it online!

How?

ITŒP‘œṖ€ - Link: list, B  e.g. [0, 0, 1, 1, 0, 1]
I        - deltas (of B)       [  0, 1, 0,-1, 1]
 T       - truthy indices      [     2,    4, 5]
  ŒP     - powerset            [[],[2],[4],[5],[2,4],[2,5],[4,5],[2,4,5]]
    ‘    - increment           [[],[3],[5],[6],[3,5],[3,6],[5,6],[3,5,6]]
       € - for each:
     œṖ  -   partition (B) at  [[[0,0,1,1,0,1]],[[0,0],[1,1,0,1]],[[0,0,1,1],[0,1]],[[0,0,1,1,0],[1]],[[0,0],[1,1],[0,1]],[[0,0],[1,1,0],[1]],[[0,0,1,1],[0],[1]],[[0,0],[1,1],[0],[1]]]

Answer 4

Curry (PAKCS), 40 bytes

f(a++b:c:d)|b/=c=(a++[b]):f(c:d)
f a=[a]

Try it online!

Answer 5

Vyxal, 6 bytes

ĠøṖvvf

Try it Online!

Port of @UnrelatedString's Brachylog answer.

Answer 6

05AB1E, 6 (or 4?) bytes

γ.œ€€˜

Try it online or verify all test cases.

If we can use strings as I/O, this could be 4 bytes instead by replacing €€˜ with J:
Try it online or verify all test cases.

Explanation:

γ       # Split the (implicit) input-list into groups of equal adjacent values
 .œ     # Get all partitions of these groups
   €    # For each partition:
    €   #  For each part of groups within a partition:
     ˜  #   Flatten the part of groups to a single list
        # (or alternatively:)
   J    # Join each list/part of groups within each partition together
        # (after which the result is output implicitly)

Answer 7

Brachylog, 5 bytes

ḅ~ccᵐ

Try it online!

Takes a list through the input variable and generates a list of lists of lists through the output variable.

ḅ        Partition into runs of consecutive equal elements.
 ~c      Take an arbitrary partition of the list of runs,
   cᵐ    and concatenate each slice.

Answer 8

Brachylog, 20 bytes

Ė!|ḅa₀cPl;?b₍↰;Pgᵗ↔c

A predicate that takes a list of 0's and 1's as input and outputs each possible partition one after another.

Try it online!

Explanation

This seems way too long.

Ė!|ḅa₀cPl;?b₍↰;Pgᵗ↔c
Ė!                    Either the input is an empty list (in which case return empty list)
  |                   Or, take the input and...
   ḅ                  Partition into blocks of equal elements
    a₀                Get a prefix of that list of blocks
      c               Flatten it
       P              Call that list P
        l             Take its length
         ;?b₍         The original input with that many elements removed from the front
             ↰        Recurse (returns a list of lists)
              ;P      Pair with P
                gᵗ    wrapped in a list
                  ↔   Reverse the order of the pair
                   c  Flatten once

Answer 9

Prolog (SWI), 65 bytes

Q+[E|F]:-append(A,[B,C|D],Q),B\=C,append(A,[B],E),[C|D]+F.
Q+[Q].

Try it online!

Similar to @alephalpha's Curry answer. Outputs as a list of choicepoints.

Answer 10

J, 27 bytes

<;.1~1,.[:(#:[:i.*/)2-2=/\]

Try it online!

-1 bytes thanks to the "2 minus" trick stolen from ovs's answer

Say we have, eg, 1,1,0,0,1 -- then we have 2 "change points" and 4 possible combos. This is essentially just the problem of listing:

0 0 
0 1
1 0
1 1

except we want that that list to be embedded in the Xs of this list:

0 X 0 X

The key insight is that this is 0..3 converted using the mixed base number 1 2 1 2. After that we just cut the original input using our 4 lists, with a 1 prepended to each.

Answer 11

Jelly, 7 bytes

Ir0Œpk€

Try it online!

Inspired by Jonathan Allan's solution.

I          Get the forward differences of the list.
     k     Partition the list after each truthy position
      €    of each element of
   Œp      the Cartesian product of
 r0        the ranges from each difference to 0 inclusive.

Jelly, 7 bytes

ŒgŒṖẎ€€

Try it online!

Port of my Brachylog solution.

Œg         Partition into runs of consecutive equal elements.
  ŒṖ       Generate every partition of the runs,
    Ẏ€€    and concatenate the runs in each slice.

Answer 12

Retina 0.8.2, 28 bytes

(.),(?!\1)
$1#
+%1`#
;$'¶$`,

Try it online! Link includes test cases. Outputs semicolon-delimited lists. Explanation:

(.),(?!\1)
$1#

Find all acceptable cutting points.

+

Loop until each cutting point has been processed.

%

Loop over each partially cut list.

1`

Only process the first remaining cutting point on each pass.

#
;$'¶$`,

Create two lists, one cut at that point, one not cut at that point.

Answer 13

Perl 5, 80 bytes

sub{@p=pop=~/0+|1+/g;$s="@p";map$s=~s, ,$r=$_%2?$&:'';$_/=2;$r,ger,0..2**@p/2-1}

Try it online!

Answer 14

Knight (v2), 125 bytes

;=lL=p+=a@P;W=l-lT|?Gp lT Gp-lT1=a+a,l;=n^2LaW+1=n-nT;=x!=b+=o@p;=kLa;W+=k-kT1&%/n^2k 2;=o+o,GbF=d+~x=x[Ga kT=bSbFd@;D+o,bO''

Try it online!

Input as a binary string. Outputs each partition on a separate line.

This probably is not even the golfiest strategy lol, but whatever. The general strategy is to construct a list a that contains the possible indexes that can be cut at (the easy part), then enumerate over all possible combinations of cuts using a (the annoying as f*** part).

Answer 15

Haskell, 94 bytes

import Data.List
f l=nub[w|w<-subsequences[id=<<x|x<-tails=<<(inits.group)l,x>[]],(w>>=id)==l]

Try it online!

Corrected as x specifications.

Thanks to @Wheat Wizard for saving some bytes using id=<<x instead of concat.

Answer 16

Charcoal, 45 bytes

⊞υ⟦Ａ⟧ＦυＦ…ι¹Ｆ²Ｆ⁺¹⌕Ａ⪫κω⁺Ｉλ¬λ⊞υ⁺⟦…κμ✂κμ⟧ΦιξＥυ⭆¹ι

Try it online! Link is to verbose version of code. Explanation:

⊞υ⟦Ａ⟧

Start with the original list, which is always a valid partition.

Ｆυ

Loop over the partitions found so far.

Ｆ…ι¹

Loop over the lists in the current partition, but stop after the first. (This is a sneaky way of getting the first list into a variable.)

Ｆ²

Loop over the possible first bits of a cutting point.

Ｆ⁺¹⌕Ａ⪫κω⁺Ｉλ¬λ

Loop over all of the possible cutting points that start with that bit. The cutting point is in between the bits, thus the extra 1 added to the positions. (Incremented works on empty lists in the newer version of Charcoal on ATO which would save a byte.)

⊞υ⁺⟦…κμ✂κμ⟧Φιξ

Cut the first list of the partition at that point and push the resulting partition to the list of partitions where it will be reevaluated for cutting.

Ｅυ⭆¹ι

Pretty-print all of the found partitions.

Answer 17

Pyth, 11 10 bytes

mmrk9d./r8

Try it online!

Explanation

        r8    length encode the implicitly evaluated input
      ./      get all partitions
mmrk9d        map length decoding to each partition element

Answer 18

Python, 230 bytes

from itertools import*
import re
def f(M):L=re.split(r'((.)\2*)',''.join(map(str,M)))[1::3];l=len(L);I=[*range(1,l)];return[[M]]+[[[int(c)for c in''.join(L[i:j])]for i,j in pairwise([0,*P,l])]for s in I for P in combinations(I,s)]

Attempt This Online!

Python 3.10+ required for pairwise.

for [1,1,0,0,1] returns:

[[[1, 1, 0, 0, 1]],
 [[1, 1], [0, 0, 1]],
 [[1, 1, 0, 0], [1]],
 [[1, 1], [0, 0], [1]]]

ungolfed:

from itertools import *
import re
def f(M):
  # produce ['11', '00', '1'] by splitting on regex which checks 2 consecutive duplicates
  L = re.split(r'((.)\2*)',''.join(map(str,M)))[1::3]
  l = len(L)
  indexes = [*range(1,l)]
  return [[M]]+[
    # wrap list for each consequtive pair of index combos and convert back from string
    [[int(c) for c in ''.join(L[i:j])]
      for i,j in pairwise([0,*partition_indexes,l])]
    for partition_size in indexes
    for partition_indexes in combinations(indexes,partition_size)
  ]

Answer 19

Nekomata, 4 bytes

ĉJᵐj

Attempt This Online!

A port of @Unrelated String's Brachylog answer.

ĉ       Partition into runs of consecutive equal elements.
 J      Take an arbitrary partition of the list of runs,
  ᵐj    and concatenate each slice.

Answer 20

JavaScript (V8), 71 bytes

f=([x,...y],z='')=>x?f(y,z+x)|f(y,[z,x]):/^,|1,1|0,0/.test(z)||print(z)

Try it online!

Seems they look same

JavaScript (V8), 72 bytes

f=([x,...y],z='')=>x?f(y,z+x)|f(y,z+[,x]):/^,|1,1|0,0/.test(z)||print(z)

Try it online!