19

Let's say I have the following list

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]

I want to find all possible sublists of a certain lenght where they don't contain one certain number and without losing the order of the numbers.

For example all possible sublists with length 6 without the 12 are:

[1,2,3,4,5,6]
[2,3,4,5,6,7]
[3,4,5,6,7,8]
[4,5,6,7,8,9]
[5,6,7,8,9,10]
[6,7,8,9,10,11]
[13,14,15,16,17,18]

The problem is that I want to do it in a very big list and I want the most quick way.

Update with my method:

oldlist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
newlist = []
length = 6
exclude = 12
for i in oldlist:
   if length+i>len(oldlist):
       break
   else:
       mylist.append(oldlist[i:(i+length)]
for i in newlist:
    if exclude in i:
       newlist.remove(i)

I know it's not the best method, that's why I need a better one.

TerryA
  • 58,805
  • 11
  • 114
  • 143
Tasos
  • 7,325
  • 18
  • 83
  • 176
  • 1
    http://docs.python.org/2/library/itertools.html#itertools.combinations – zch Jun 12 '13 at 09:13
  • Rather than trying to figure out which combinations include or exclude the `12`, why not just **remove it from the input first**? – Karl Knechtel Feb 28 '23 at 21:48

6 Answers6

8

Use itertools.combinations:

import itertools
mylist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
def contains_sublist(lst, sublst):
    n = len(sublst)
    return any((sublst == lst[i:i+n]) for i in xrange(len(lst)-n+1))
print [i for i in itertools.combinations(mylist,6) if 12 not in i and contains_sublist(mylist, list(i))]

Prints:

[(1, 2, 3, 4, 5, 6), (2, 3, 4, 5, 6, 7), (3, 4, 5, 6, 7, 8), (4, 5, 6, 7, 8, 9), (5, 6, 7, 8, 9, 10), (6, 7, 8, 9, 10, 11), (13, 14, 15, 16, 17, 18)]
TerryA
  • 58,805
  • 11
  • 114
  • 143
  • It's a decent answer, but the conversion to a string makes it impossible to use any object in the list that doesn't have an `__str__` or `__repr__` method. – StoryTeller - Unslander Monica Jun 12 '13 at 09:18
  • I don't want to lose the order of my numbers. I want to be a continues sublist. For example the (1, 2, 13, 14, 15, 16) is not what I need. I add my method on the comments, but I think it isn't the best way – Tasos Jun 12 '13 at 09:18
  • I think it isn't the fastest way to generate a large amount of unused combinations (all with 12 in it) and filter them out. Instead there should be either a copy of the list without the 12 be processed or some kind of mapping from a list with one element less to the desired one (e.g. by adding 1 to all resulting numbers >= 12) – Michael Butscher Jun 12 '13 at 09:19
  • @StoryTeller My bad, I had just gotten it from [http://stackoverflow.com/questions/3313590/check-for-presence-of-a-sublist-in-python](here). The one I have now (also from the question) should work :). – TerryA Jun 12 '13 at 09:23
8

A straightforward, non-optimized solution would be

result = [sublist for sublist in 
        (lst[x:x+size] for x in range(len(lst) - size + 1))
        if item not in sublist
    ]

An optimized version:

result = []
start = 0
while start < len(lst):
    try:
        end = lst.index(item, start + 1)
    except ValueError:
        end = len(lst)
    result.extend(lst[x+start:x+start+size] for x in range(end - start - size + 1))
    start = end + 1
georg
  • 211,518
  • 52
  • 313
  • 390
3

The simplest way I can think of would be to remove the excluded number from the list and then use itertools.combinations() to generate the desired sublists, This has the added advantage that it will produce the sublists iteratively.

from  itertools import combinations

def combos_with_exclusion(lst, exclude, length):
    for combo in combinations((e for e in lst if e != exclude), length):
        yield list(combo)

mylist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]

for sublist in combos_with_exclusion(mylist, 12, 6):
    print sublist

Output:

[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 7]
[1, 2, 3, 4, 5, 8]
[1, 2, 3, 4, 5, 9]
[1, 2, 3, 4, 5, 10]
[1, 2, 3, 4, 5, 11]
[1, 2, 3, 4, 5, 13]
        ...
[11, 14, 15, 16, 17, 18]
[13, 14, 15, 16, 17, 18]
martineau
  • 119,623
  • 25
  • 170
  • 301
2

I like to build solutions out of small composable parts. A few years of writing Haskell does that to you. So I'd do it like this...

First, this will return an iterator over all sublists, in ascending order of length, starting with the empty list:

from itertools import chain, combinations

def all_sublists(l):
    return chain(*(combinations(l, i) for i in range(len(l) + 1)))

Generally we're discouraged from using single-letter variable names, but I think that in short bursts of highly abstract code it's a perfectly reasonable thing to do.

(BTW to omit the empty list, use range(1, len(l) + 1) instead.)

Then we can solve your problem in general by adding your criteria:

def filtered_sublists(input_list, length, exclude):
    return (
        l for l in all_sublists(input_list)
        if len(l) == length and exclude not in l
    )

So for example:

oldlist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
length = 6
exclude = 12
newlist = filtered_sublists(old_list, length, exclude)
gimboland
  • 1,926
  • 2
  • 19
  • 28
1

My attempt at recursively creating all possible list of lists. The depth parameter just takes the number of items to remove from each list. This is not a sliding window.

Code:

def sublists(input, depth):
    output= []
    if depth > 0:
        for i in range(0, len(input)):
            sub= input[0:i] + input[i+1:]
            output += [sub]
            output.extend(sublists(sub, depth-1))
    return output

Examples (typed interactively into python3):

sublists([1,2,3,4],1)

[[2, 3, 4], [1, 3, 4], [1, 2, 4], [1, 2, 3]]

sublists([1,2,3,4],2)

[[2, 3, 4], [3, 4], [2, 4], [2, 3], [1, 3, 4], [3, 4], [1, 4], [1, 3], [1, 2, 4], [2, 4], [1, 4], [1, 2], [1, 2, 3], [2, 3], [1, 3], [1, 2]]

sublists([1,2,3,4],3)

[[2, 3, 4], [3, 4], [4], [3], [2, 4], [4], [2], [2, 3], [3], [2], [1, 3, 4], [3, 4], [4], [3], [1, 4], [4], [1], [1, 3], [3], [1], [1, 2, 4], [2, 4], [4], [2], [1, 4], [4], [1], [1, 2], [2], [1], [1, 2, 3], [2, 3], [3], [2], [1, 3], [3], [1], [1, 2], [2], [1]]

Some edge cases:

sublists([1,2,3,4],100)

[[2, 3, 4], [3, 4], [4], [3], [2, 4], [4], [2], [2, 3], [3], [2], [1, 3, 4], [3, 4], [4], [3], [1, 4], [4], [1], [1, 3], [3], [1], [1, 2, 4], [2, 4], [4], [2], [1, 4], [4], [1], [1, 2], [2], [1], [1, 2, 3], [2, 3], [3], [2], [1, 3], [3], [1], [1, 2], [2], [1]]

sublists([], 1)

[]

NOTE: the output list of lists includes duplicates.

Nihal
  • 5,262
  • 7
  • 23
  • 41
Megatron
  • 15,909
  • 12
  • 89
  • 97
0

I have an answer but i think it is not the best:

oldlist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
result = []
def sub_list(lst):
    if len(lst) <= 1:
        result.append(tuple(lst))
        return
    else:
        result.append(tuple(lst))
    for i in lst:
        new_lst = lst[:]
        new_lst.remove(i)
        sub_list(new_lst)
sub_list(oldlist)
newlist = set(result)    # because it have very very very many the same
                         # sublist so we need use set to remove these also 
                         # use tuple above is also the reason 
print newlist

It will get the result but cause it will have much same sublist so it need a lot memory and a lot time. I think it is not a good way.

Laobe
  • 121
  • 1
  • 2