Рекурсивно определяя список в python, все в списке заменяются на последний элемент - PullRequest
Новая
       28

Рекурсивно определяя список в python, все в списке заменяются на последний элемент

1 голос
/ 10 марта 2020

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

Я (кажется, я) пытаюсь рекурсивно определить список, но вместо того, чтобы неоднократно добавлять новый элемент в список, все элементы в списке заменяются этим новым элементом. Смотрите фрагмент ниже. Код должен генерировать список I, содержащий все (упорядоченные) подсписки [0,...,n] длины d. 

n = 5
d = 2

def next(S):
    m = S.index(min([s for s in S if s+1 not in S]))
    for i in range(m):
        S[i] = i
    S[m] += 1
    return S

I = [[i for i in range(d)]]
while I[-1][0] <= n-d:
    I += [next(I[-1])]
print(I)

Я ожидал, что это вернет следующий список: 

[[0,1],[0,2],[1,2],[0,3],[1,3],[2,3],[0,4],[1,4],[2,4],[3,4],[0,5],[1,5],[2,5],[3,5],[4,5]]

Но вместо этого он возвращает следующий список: 

[[4,5],[4,5],[4,5],[4,5],[4,5],[4,5],[4,5],[4,5],[4,5],[4,5],[4,5],[4,5],[4,5],[4,5],[4,5]]

Может кто-нибудь указать мне объяснение, почему этот код не выполняет то, что я ожидаю? Заранее спасибо.

Ответы [ 3 ]

4 голосов
/ 10 марта 2020

Каждый вызов next должен получить собственную копию списка; например 

I += [next(I[-1][:])]

Ваш код создавал список с несколькими ссылками на тот же список . Посылая каждому вызову next свою собственную копию, все элементы в результате различаются.

Этого также можно было бы достичь, изменив next для создания нового списка с нуля вместо изменения список пропущен.

1 голос
/ 10 марта 2020

Ваша функция next() изменяет список, заданный на месте, вместо создания новой копии. Вот почему все элементы в I фактически являются одним и тем же списком.

Выражение типа S = list(S) в next() было бы достаточно, чтобы заменить S (мелкой) копией и убедиться, что изменения к нему не применяются исходные списки.

0 голосов
/ 10 марта 2020

Вы передаете ссылку на существующий список, а не на копию списка, поэтому список изменяется по мере итерации. Следующее может помочь объяснить это поведение: 

def modify(li, i=3):
    print(li)
    li += [i]  # This adds to the passed list
    if i > 0:
        modify(li, i-1)

def modify_copy(li, i=3):
    print(li)
    li = li + [i]  # This overwrites "li" on every call
    if i > 0:
        modify_copy(li, i-1)

one = [4]
modify(one)
print("Result:", one)

two = [4]
modify_copy(two)
print("Result:", two)

Вывод 

[4]
[4, 3]
[4, 3, 2]
[4, 3, 2, 1]
Result: [4, 3, 2, 1, 0]
[4]
[4, 3]
[4, 3, 2]
[4, 3, 2, 1]
Result: [4]
...