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

Question

У меня есть два списка целых чисел, a и b, которые не обязательно имеют одинаковую длину. Я хотел бы создать из них новые списки, удалив либо первый элемент a, либо первый элемент b, и добавив его в новый список, повторяя этот шаг до тех пор, пока оба элемента a и b не станут пустыми. На каждом этапе этого процесса количество возможных списков растет экспоненциально, и я хотел бы знать, как сгенерировать каждый список, который можно создать таким образом.

Пока что мне удалось только выяснить, что количество возможных списков равно sum((2**i for i in range(len(a) + len(b)))). Я не знаю, как поступить с этим, и был бы признателен за любые указатели.

Для информации, моя конечная цель - вычислить сумму различий между последовательными элементами для каждого списка и найти минимум из них .

Answer 1

Думаю, этого можно добиться с помощью рекурсии. Некоторый код.

permutation = [0]*10 # size of this list has to be equal to lenth of list1 + length of list2. (you can have 4 as the size of the list).
def task(list1,list2,index):
    if len(list1)==0 and len(list2)==0: # if length of both the list is 0, we print the 
        print(permutation)              # permutation list
        return

    if len(list1)>0:    
        permutation[index] = list1[0]
        modified_list1 = list1[:]       # Since lists in python are passed by reference, I am making a copy of the list
        modified_list1.pop(0)           # Removing the first element
        task(modified_list1,list2,index+1) #and calling the function again using the modified list.

    if len(list2)>0:
        permutation[index] = list2[0]
        modified_list2 = list2[:]
        modified_list2.pop(0)
        task(list1,modified_list2,index+1)

if __name__=="__main__":
    list1 = [1]
    list2 = [4,5,6]
    task(list1,list2,0)

Рекурсивные решения могут быть немного сложными для понимания, я рекомендую вам взять копию и перо и попробовать смоделировать его для небольшого ввода, вы поймете, как все работает.

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