18

次のリストがあるとしましょう

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

特定の数字を含まず、数字の順序を失うことなく、特定の長さのすべての可能なサブリストを見つけたいです。

たとえば、12 を除いた長さ 6 のすべての可能なサブリストは次のとおりです。

[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]

問題は、非常に大きなリストでそれを行いたいことであり、最も迅速な方法が必要です。

私の方法で更新してください：

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)

それが最善の方法ではないことはわかっているので、より良い方法が必要です。

4

6 に答える 6

8

直接的で最適化されていないソリューションは次のようになります。

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

最適化されたバージョン:

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
于 2013-06-12T09:19:36.700 に答える
8

使用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))]

版画:

[(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)]
于 2013-06-12T09:13:25.730 に答える
1

リストのすべての可能なリストを再帰的に作成する私の試み。depth パラメーターは、各リストから削除するアイテムの数だけを受け取ります。これはスライディング ウィンドウではありません。

コード：

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

例 (インタラクティブに 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] ]

いくつかのエッジケース:

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)

[]

注: リストの出力リストには重複が含まれます。

于 2014-04-24T18:20:38.443 に答える
0

答えはありますが、それは最善ではないと思います：

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

結果は得られますが、同じサブリストが多くなるため、多くのメモリと時間が必要になります。良くない方法だと思います。

于 2016-06-08T08:43:12.827 に答える