Maximal linear sublists

Question

In this challenge you will write code to take a list of positive integers and output all maximal linear sublists.

• A sublist is is a list which can be created by deleting values from the the input list. Sublists have more structure than just lists. They in a way "remember" which values are deleted.
• Similarly we say that sublist A is a sublist of sublist B if A can be formed by deleting elements of B.
• A linear list (or sublist) is one such that all consecutive values have the same difference.
• A maximal linear sublist is a sublist which is linear, and is not a sublist of any other linear sublist.

For example if we receive the input list [1,3,5,3] then the maximal linear sublists are:

[1,3,5,3]
 ^ ^ ^
[1,3,5,3]
 ^ ^
[1,3,5,3]
 ^ ^
[1,3,5,3]
 ^ ^

Note that the first sublist does have a sublist with the values [1,3], but there is another sublist of values [1,3] which is maximal.

Task

Given a list of positive integers you should output all the maximal linear sublists. Despite the previous emphasis, to simplify things you should output the sublists as lists, i.e. just output the values in a list form.

You give your outputs in any order, but there should not be duplicates, other than sublists who coincidentally have the same values.

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

Test cases

[] -> []
[19] -> [19]
[1,1,2] -> [1,2], [1,2], [1,1]
[1,3,5,3] -> [1,3], [3,3], [5,3], [1,3,5]
[1,2,3,4,3] -> [1,2,3], [3,3], [4,3] [1,2,3,4]
[1,2,3,3] -> [1,2,3], [3,3], [1,2,3]
[1,2,3,4] -> [1,2,3,4]

• Nick Kennedy: For the empty list, is it acceptable to return a list containing the empty list (I.e. [[]])? The way you’ve shown your examples it’s not clear, but it would seem that each of the other answers might syntactically need an outer pair of square brackets so adding them for rhe first example would therefore seem reasonable too.
• Wheat Wizard: @NickKennedy That's the intended output for that case. It's meets the rules outlined by the challenge and it fits the pattern given by the test cases. Outputting nothing would be incongruous with both.

Answer 1

Jelly, 18 bytes

JŒPịIEɗƇ8fƑⱮS\ÐṂ`ị

A monadic Link that accepts a list of integers and yields a list of the maximal linear sublists.

Try it online! Or see the test-suite.

How?

JŒPịIEɗƇ8fƑⱮS\ÐṂ`ị - Link: list of integers, A
J - indices of A
 ŒP - powerset
 ɗƇ8 - keep those for which:
 ị - index back into A
 I - forward differences
 E - all equal?
 \ÐṂ` - keep those minimal under:
 Ɱ - map with:
 Ƒ - is invariant under?:
 f - filter keep
 S - sum
 ị - index back into A

• Nick Kennedy: I came up with this independently, but it’s sufficiently similar to yours that you can have this for a two byte saving: JŒPịIEɗƇ8fƑⱮSỊɗƇị`
• Nick Kennedy: Actually have now realised why you had the Ḋ, so it’s only really a one byte saving (and you can achieve that by just dropping the 9 from your answer). However, I’ve also asked if [[]] is acceptable for the empty list.
• Nick Kennedy: Sounds like the Ḋ actually leads to the wrong output so it can/should be 18 bytes if I’ve understood correctly
• Jonathan Allan: Thanks @NickKennedy. I had meant to remove the 9 and should have noticed as I was writing the explanation! I interpreted the example incorrectly and hence included the dequeue.

Answer 2

Python3, 252 bytes

E=enumerate
def f(l):
 q,T=[([a],[],[i])for i,a in E(l)],[]
 while q:
 a,c,I=q.pop(0)
 T+=[(a,I)]
 for j,k in E(l):
 if j>max(I)and(c==[]or a[-1]-k==c):q+=[(a+[k],a[-1]-k,I+[j])]
 return[a for a,b in T if not any(not{*b}-{*B}for A,B in T if B!=b)]

Try it online!

• Mustafa Aydın: -1 byte via q+=..., instead of q+=[...]
• ceilingcat: 241 bytes

Answer 3

JavaScript (ES6), 149 bytes

a=>(o=[...Array(1<<a.length).keys(g=n=>[x,y]=a[F]((_,i)=>n>>i&1))][F='filter'](n=>!g(n).some(p=v=>p-(p=v)+y-x)))[F](p=>o.every(q=>p&q-p|q==p)).map(g)

Try it online!

Commented

Helper function

g = // g is a helper function (actually defined in the
n => // scope of the main function) taking an integer n
 // and returning a sublist of a[]
[x, y] = // save the first two entries in global variables
 a.filter((_, i) => // for each value at index i in a[]:
 n >> i & 1 // keep it only if the i-th bit of n is set
 ) // end of filter()

Main function

a => ( // a[] = input array
 o = [ // build the range going from 0 to 2**N - 1
 ...Array( // where N is the length of a[]
 1 << a.length // (i.e. all possible bit-masks of length N)
 ).keys() //
 ].filter(n => // for each value n in that range:
 !g(n) // build the sublist for the bit-mask n
 .some(p = v => // for each value v in this sublist:
 p - (p = v) + // discard the sublist if the difference
 y - x // between v and the previous value is not
 // equal to those of the first 2 entries
 ) // end of some()
 ) // end of filter(); save the result in o[]
).filter(p => // for each value p in o[]:
 o.every(q => // for each value q in o[]:
 p & q - p | // make sure that either at least one bit
 q == p // set in p is not set in q, or q = p
 ) // end of every()
) // end of filter()
.map(g) // translate the bit-masks back to sublists

Answer 4

Charcoal, (削除) 58 (削除ここまで) 53 bytes

F⮌EX2Lθ⌕A⮌⍘ι21F›⬤υ−ικ⊙ι∧›λ1↨E4§θ§ι−λ↔⊖μ±1⊞υιEυ⭆1Eι§θν

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

F⮌EX2Lθ⌕A⮌⍘ι21

Loop over the sublists of the indices of the list's elements from largest to smallest.

F›⬤υ−ικ⊙ι∧›λ1↨E4§θ§ι−λ↔⊖μ±1

If this isn't a sublist of an already found list but is linear, then...

⊞υι

... save this as a new maximal linear sublist.

Eυ⭆1Eι§θν

Convert the lists of indices to lists of elements and pretty-print them.

Linearity is determined by taking a sliding window of size 3 and computing x[1]-x[0]+x[1]-x[2] which should be 0 in all cases.

This answer could be written as a single statement instead of four but it would still be (削除) 58 (削除ここまで) 53 bytes.

Answer 5

05AB1E, (削除) 22 (削除ここまで) 20 bytes

ā<æʒè\Ë}©ʒ®€æ€`»sðý¢}è

Try it online or verify all test cases.

Explanation:

ā # Push a list in the range [1, input-length]
 < # Decrease each by 1 to make them 0-based indices: [0,length)
 æ # Get the powerset of this
 ʒ # Filter it by:
 è # Index each into the (implicit) input-list
 \ # Get their forward differences
 Ë # Check if all are the same
 }© # After the filter: store the list in variable `®`
 ʒ # Then filter once again:
 ® # Push list of lists `®`
 ۾ # Get the powerset of each inner list
 €` # Then flatten it one level down
 s # Swap so the current list we're filtering is at the top
 .¢ # Count how many times this sublist occurs in the larger list of lists
 # (only 1 is truthy in 05AB1E)
 }è # After the filter: index each value into the (implicit) input-list
 # (after which the resulting list of lists is output implicitly)

(削除) Unfortunately, almost all of 05AB1E builtins are vectorized, hence the need for the » and ðý. (削除ここまで) -2 bytes, because luckily with the count builtin ¢, there is a non-vectorized alternative .¢. :)