CODEWITHSUNDEEP
pythonlistiterationsublist
Mose
Mose

Reputation: 79

Python: Get all the non-overlapping, consecutive sublists from a list

I'm trying to figure out an elegant/efficient solution for finding sublists in a list, with certain constraints.

For example, given this list:

values = ['a', 'b', 'c', 'd', 'e', 'f']

And a value for maxLength:

maxLength = 4

Find all sublists in the values list such that:

So in this example, these are acceptable solutions:

[['a'], ['b'], ['c'], ['d'], ['e'], ['f']]
[['a', 'b'], ['c'], ['d'], ['e'], ['f']]
...
[['a', 'b'], ['c', 'd', 'e'], ['f']]
...
[['a', 'b', 'c', 'd'], ['e', 'f']]
...
[['a', 'b'], ['c', 'd', 'e', 'f']]

These are not acceptable:

[['a', 'b'], ['d', 'e'], ['f']]           #Error: not consecutive, 'c' is missing
[['a', 'b', 'c'], ['c', 'd', 'e'], ['f']] #Error: overlapping, 'c' is in two subsets
[['a', 'b', 'c', 'd', 'e'], ['f']]        #Error: the first sublist has length > maxLength (4)

Upvotes: 3

Views: 945

Answers (1)

Ajax1234
Ajax1234

Reputation: 71451

You can use recursion:

values = ['a', 'b', 'c', 'd', 'e', 'f']
maxLength = 4

def groupings(d):
  if not d:
    yield []
  else:
    for i in range(1, maxLength+1):
      for c in groupings(d[i:]):
         yield [d[:i], *c]

_d = list(groupings(values))
new_d = [a for i, a in enumerate(_d) if a not in _d[:i]]

Output:

[[['a'], ['b'], ['c'], ['d'], ['e'], ['f']], [['a'], ['b'], ['c'], ['d'], ['e', 'f']], [['a'], ['b'], ['c'], ['d', 'e'], ['f']], [['a'], ['b'], ['c'], ['d', 'e', 'f']], [['a'], ['b'], ['c', 'd'], ['e'], ['f']], [['a'], ['b'], ['c', 'd'], ['e', 'f']], [['a'], ['b'], ['c', 'd', 'e'], ['f']], [['a'], ['b'], ['c', 'd', 'e', 'f']], [['a'], ['b', 'c'], ['d'], ['e'], ['f']], [['a'], ['b', 'c'], ['d'], ['e', 'f']], [['a'], ['b', 'c'], ['d', 'e'], ['f']], [['a'], ['b', 'c'], ['d', 'e', 'f']], [['a'], ['b', 'c', 'd'], ['e'], ['f']], [['a'], ['b', 'c', 'd'], ['e', 'f']], [['a'], ['b', 'c', 'd', 'e'], ['f']], [['a', 'b'], ['c'], ['d'], ['e'], ['f']], [['a', 'b'], ['c'], ['d'], ['e', 'f']], [['a', 'b'], ['c'], ['d', 'e'], ['f']], [['a', 'b'], ['c'], ['d', 'e', 'f']], [['a', 'b'], ['c', 'd'], ['e'], ['f']], [['a', 'b'], ['c', 'd'], ['e', 'f']], [['a', 'b'], ['c', 'd', 'e'], ['f']], [['a', 'b'], ['c', 'd', 'e', 'f']], [['a', 'b', 'c'], ['d'], ['e'], ['f']], [['a', 'b', 'c'], ['d'], ['e', 'f']], [['a', 'b', 'c'], ['d', 'e'], ['f']], [['a', 'b', 'c'], ['d', 'e', 'f']], [['a', 'b', 'c', 'd'], ['e'], ['f']], [['a', 'b', 'c', 'd'], ['e', 'f']]]

Upvotes: 5

Related Questions