Как рекурсивно создать список перестановок в Python? - PullRequest
Новая
       17

Как рекурсивно создать список перестановок в Python?

0 голосов
/ 09 октября 2019

У меня есть словарь под названием possibilities, где ключ - это индекс, а значения для этого ключа - это значения, которые могут находиться в этом индексе в списке. Смотрите ниже: 

possibilities = {0: [None, 'KLAX_1', 'KDEN_1'],
 1: [None, 'KLAX_1', 'KDEN_1'],
 2: [None, 'KLAX_1', 'KLAS_1', 'KDEN_1'],
 3: [None, 'KLAX_1', 'KLAS_1', 'KPHX_1', 'KDEN_1', 'KDFW_1'],
 4: [None, 'KPHX_1', 'KDEN_2', 'KDFW_2'],
 5: [None, 'KDEN_2', 'KDFW_2'],
 6: [None, 'KDEN_2']}

Я хочу сохранить каждую перестановку этого списка в другом списке под названием permutations_list. Моя цель состоит в том, чтобы создать этот список перестановок из возможных вариантов. В настоящее время у меня есть огромный вложенный цикл, который строит это (см. Ниже). Но я хочу иметь функцию, которая принимает possibilities_dict и автоматически генерирует мой список . Я думаю, что рекурсивная функция позволит мне не указывать нужное мне количество индексов. 

for index_0 in possibilities[0]:
    for index_1 in possibilities[1]:
        for index_2 in possibilities[2]:
            for index_3 in possibilities[3]:
                for index_4 in possibilities[4]:
                    for index_5 in possibilities[5]:
                        for index_6 in possibilities[6]:
                            lst = [index_0,index_1,index_2,index_3,index_4,index_5,
                                  index_6]
                            permutations_list.append(lst)

Результатом из приведенного выше кода является список permutations_list длины 5184. Каждый элемент в этом списке является списком, который содержит определенную перестановку всех значений. Это не так просто, как использование itertools.permutations, поскольку только определенные значения могут находиться по определенным индексам в списке. Может кто-нибудь помочь обеспечить рекурсивную функцию для этого? Спасибо.

1 Ответ

1 голос
/ 09 октября 2019

После некоторого кодирования я нашел рекурсивное решение. Вы можете использовать itertools.product или функции ниже. 

def rec_permutations(possibilities):
    counter = 0
    permutations_list=[]
    lst=[]
    return rec_permutations_helper(possibilities, permutations_list, counter, lst)

def rec_permutations_helper(possibilities, permutations_list, counter, lst):
    # Base case
    if counter == len(possibilities):
        permutations_list.append(lst)
        return
    # Recursive case
    else:
        locations = possibilities[counter]
        for location in locations:
            new_lst = lst + [location]      
            rec_permutations_helper(possibilities, permutations_list, counter+1, new_lst)

    return permutations_list
...