Смешанный рекурсивный список append в Python

Question

Я пытаюсь создать пару функций, которые, учитывая список «стартовых» чисел, будут рекурсивно добавлять к каждой позиции индекса до определенного максимального значения (почти так же, как одометр работает в автомобиле - каждый счетчик колеблется до 9 перед сбросом на 1 и переносом на следующее колесо).

код выглядит следующим образом:

number_list = [] 

def counter(start, i, max_count): 
    if start[len(start)-1-i] < max_count: 
     start[len(start)-1-i] += 1 
     return(start, i, max_count) 
    else: 
     for j in range (len(start)): 
      if start[len(start)-1-i-j] == max_count: 
       start[len(start)-1-i-j] = 1 
      else: 
       start[len(start)-1-i-j] += 1 
       return(start, i, max_count) 

def all_values(fresh_start, i, max_count): 
    number_list.append(fresh_start) 
    new_values = counter(fresh_start,i,max_count) 
    if new_values != None: 
     all_values(*new_values) 

Когда я бегу all_values ​​([1,1,1], 0,3) и печати number_list, хотя, я получаю:

[[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1],  
[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], 
[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], 
[1, 1, 1], [1, 1, 1], [1, 1, 1]] 

Это, к сожалению. Вдвойне так, зная, что, если я заменю первую строку all_values ​​ с

print(fresh_start) 

я получаю именно то, что я после:

[1, 1, 1] 
[1, 1, 2] 
[1, 1, 3] 
[1, 2, 1] 
[1, 2, 2] 
[1, 2, 3] 
[1, 3, 1] 
[1, 3, 2] 
[1, 3, 3] 
[2, 1, 1] 
[2, 1, 2] 
[2, 1, 3] 
[2, 2, 1] 
[2, 2, 2] 
[2, 2, 3] 
[2, 3, 1] 
[2, 3, 2] 
[2, 3, 3] 
[3, 1, 1] 
[3, 1, 2] 
[3, 1, 3] 
[3, 2, 1] 
[3, 2, 2] 
[3, 2, 3] 
[3, 3, 1] 
[3, 3, 2] 
[3, 3, 3] 

Я уже пытался сделать копию fresh_start (путем temp = fresh_start) и добавление этого вместо этого, но без изменения вывода.

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

Большое спасибо!

Answer 1

Попробуйте следующее в интерпретаторе:

>>> a = [1,1,1] 
>>> b = [] 
>>> b.append(a) 
>>> b.append(a) 
>>> b.append(a) 
>>> b 
[[1, 1, 1], [1, 1, 1], [1, 1, 1]] 
>>> b[2][2] = 2 
>>> b 
[[1, 1, 2], [1, 1, 2], [1, 1, 2]] 

Это упрощенная версия того, что происходит в вашем коде. Но почему это происходит?

b.append(a) на самом деле не делает копию a и набивает ее в массив по адресу b. Он делает ссылка на a. Это похоже на закладку в веб-браузере: когда вы открываете веб-страницу с помощью закладки, вы ожидаете увидеть веб-страницу, как сейчас, а не так, как это было при ее закладке. Но это также означает, что если у вас есть несколько закладок на одной странице, и эта страница меняется, вы увидите измененную версию независимо от того, какую закладку вы следуете.

Это же история с temp = a, и в этом отношении, a = [1,1,1]. temp и a являются «закладками» для определенного массива, который содержит три. И b в приведенном выше примере представляет собой закладку в массив ..., который содержит три закладки для того же массива, который содержит три.

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

>>> a = [1,1,1] 
>>> b = [] 
>>> b.append(a[:]) 
>>> b.append(a[:]) 
>>> b.append(a[:]) 
>>> b 
[[1, 1, 1], [1, 1, 1], [1, 1, 1]] 
>>> b[2][2] = 2 
>>> b 
[[1, 1, 1], [1, 1, 1], [1, 1, 2]] 

Намного лучше.

Answer 2

temp = fresh_start 

не делает копию. Добавление не делает копии, присваивание не делает копии, и почти все, что не говорит, что делает копию, не делает копию. Если вы хотите получить копию, нарежьте ее:

fresh_start[:] 

это копия.

Answer 3

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

import numpy 
first_column, second_column, third_column = numpy.mgrid[1:4,1:4,1:4] 
numpy.dstack((first_column.flatten(),second_column.flatten(),third_column.flatten())) 
Out[23]: 
array([[[1, 1, 1], 
    [1, 1, 2], 
    [1, 1, 3], 
    [1, 2, 1], 
    [1, 2, 2], 
    [1, 2, 3], 
    [1, 3, 1], 
    [1, 3, 2], 
    [1, 3, 3], 
    [2, 1, 1], 
    [2, 1, 2], 
    [2, 1, 3], 
    [2, 2, 1], 
    [2, 2, 2], 
    [2, 2, 3], 
    [2, 3, 1], 
    [2, 3, 2], 
    [2, 3, 3], 
    [3, 1, 1], 
    [3, 1, 2], 
    [3, 1, 3], 
    [3, 2, 1], 
    [3, 2, 2], 
    [3, 2, 3], 
    [3, 3, 1], 
    [3, 3, 2], 
    [3, 3, 3]]]) 

Конечно, полезность данного конкретного подхода может зависеть от различных входных данных вам нужно иметь дело, но я подозреваю, что это может быть интересным способом для создания данных и NumPy довольно быстро для такого рода вещи. Предположительно, если в вашем списке ввода больше элементов, у вас может быть больше min: max аргументов, поданных в mgrid [], а затем распаковать/скрыть аналогичным образом.

Answer 4

Вот упрощенная версия вашей программы, которая работает. Комментарии будут следовать.

number_list = [] 

def _adjust_counter_value(counter, n, max_count): 
    """ 
    We want the counter to go from 1 to max_count, then start over at 1. 
    This function adds n to the counter and then returns a tuple: 
    (new_counter_value, carry_to_next_counter) 
    """ 
    assert max_count >= 1 
    assert 1 <= counter <= max_count 

    # Counter is in closed range: [1, max_count] 
    # Subtract 1 so expected value is in closed range [0, max_count - 1] 
    x = counter - 1 + n 
    carry, x = divmod(x, max_count) 

    # Add 1 so expected value is in closed range [1, max_count] 
    counter = x + 1 
    return (counter, carry) 

def increment_counter(start, i, max_count): 
    last = len(start) - 1 - i 
    copy = start[:] # make a copy of the start 

    add = 1 # start by adding 1 to index 
    for i_cur in range(last, -1, -1): 
     copy[i_cur], add = _adjust_counter_value(copy[i_cur], add, max_count) 
     if 0 == add: 
      return (copy, i, max_count) 
    else: 
     # if we have a carry out of the 0th position, we are done with the sequence 
     return None 

def all_values(fresh_start, i, max_count): 
    number_list.append(fresh_start) 
    new_values = increment_counter(fresh_start,i,max_count) 
    if new_values != None: 
     all_values(*new_values) 

all_values([1,1,1],0,3) 

import itertools as it 
correct = [list(tup) for tup in it.product(range(1,4), range(1,4), range(1,4))] 
assert number_list == correct 

Так как вы хотите, счетчики, чтобы перейти от 1 до max_count включительно, это немного сложнее обновлять каждый счетчик. Ваше первоначальное решение состояло в том, чтобы использовать несколько операторов if, но здесь я сделал вспомогательную функцию, которая использует divmod() для вычисления каждой новой цифры. Это позволяет нам добавить любое приращение к любой цифре и найти правильное выполнение цифры.

Ваша первоначальная программа никогда не меняла значение i, поэтому мой пересмотренный вариант тоже не изменился. Вы могли бы упростить программу, избавившись от i и просто имея increment_counter(), всегда переходите к последней позиции.

Если запустить for петлю до конца без вызова break или return, то else: случае будет работать, если есть один присутствует. Здесь я добавил случай else: для обработки выполнения 0-го места в списке. Если выполняется 0-е место, это означает, что мы достигли конца счетной последовательности. В этом случае мы возвращаем None.

Ваша оригинальная программа является довольно сложной. Он имеет два явных выражения return в counter() и неявный возврат в конце последовательности. Он возвращает None, чтобы сигнализировать о том, что рекурсия может остановиться, но способ, которым он это делает, слишком сложный для моего вкуса. Я рекомендую использовать явный return None, как я показал.

Обратите внимание, что Python имеет модуль itertools, который включает в себя способ генерации счетной серии, подобной этой. Я использовал его для проверки правильности результата.

Я уверен, что вы пишете это, чтобы узнать о рекурсии, но имейте в виду, что Python не лучший язык для рекурсивных решений, подобных этому. Python имеет относительно неглубокий стек рекурсии и не автоматически превращает хвостовую рекурсию в итеративный цикл, поэтому это может привести к переполнению стека внутри Python, если ваши рекурсивные вызовы достаточно долгое время. Лучшим решением в Python было бы использовать itertools.product(), как я сделал, чтобы просто генерировать желаемую последовательность счетчиков.

Поскольку ваша сгенерированную последовательность представляет собой список из списков, и itertools.product() производят кортежи, я использовал список понимание, чтобы преобразовать каждый кортеж в список, так что конечный результат является списком списков, и мы можем просто использовать Python == оператора для их сравнения.