Блог

Главная - Вопросы по программированию - Генерировать все подпоследовательности заданного списка с минимально возможной сложностью

Генерировать все подпоследовательности заданного списка с минимально возможной сложностью

#python-3.x #list

#python-3.x #Список

Вопрос:

У меня есть список целочисленных элементов, я хочу сгенерировать все подпоследовательности списка, я попробовал этот код —

 def sequences(arr, n):
    sheet = []
    opsize = (2**n) 
    for counter in range( 1, (int)(opsize)) : 
        t = []
        for j in range(0, n) : 
            if (counter amp; (1<<j)):
                t.append(arr[j]) 
        sheet.append(t)
    return sheet

Если входной список — [1,2,2]

Вывод — [ [1], [2], [1, 2], [2], [1, 2], [2, 2], [1, 2, 2] ]

Но для любого высокого значения n требуется много времени. Кто-нибудь может предложить мне какой-либо другой подход, чтобы минимизировать его сложность.

Спасибо.

Комментарии:

1. Посмотрите на itertools.combinations .

2. Он возвращает подпоследовательности элементов фиксированной длины из входного iterable. Но мне нужен весь размер подпоследовательностей.

3. Поэтому просто перебирайте range(1, len(sequence) 1) и вызывайте combinations для каждой длины.

4. Здесь я также беспокоюсь о временной сложности, поэтому, пожалуйста, дайте подход, который минимизирует временную сложность.

5. Это настолько мало, насколько это возможно; генерация всех возможных подмножеств по своей сути является 2^n операцией. Использование itertools для генерации объектов, по крайней мере, позволит вам делать это лениво, вместо того, чтобы хранить все в памяти, что может помочь с реальной скоростью.