Неожиданное поведение список на Append в питона

Question

Я решить этот вопрос на Interviewbit:

Учитывая множество различных целых чисел, S, возвращает все возможные subsets.Elements в подгруппе должно быть в не-нисходящем Order.The набор решений не должен содержать дубликатов подмножеств.

А вот мой просто, сам объяснительное код:

ans_list=[] 

def solve(i,a,tmp,l,k): 
    global ans_list 
    if i==l : 
     print "List to append:  " ,tmp 
     ans_list.append(tmp) 
     print "ans_list currently: ", ans_list 
     return 

    j=k 
    while j < len(a): 
     tmp.append(a[j]) 
     solve(i+1,a,tmp,l,j+1) 
     tmp.pop() 
     j+=1 


class Solution: 
    # @param a : list of integers 
    # @return a list of list of integers 
    def subsets(self, a): 
     a=sorted(a) 
     global ans_list 
     tmp=[] 
     i=0 
     for l in range(len(a)+1): 
     solve(0,a,tmp,l,0) 
     return ans_list 

def main(): 
    a=[1,2,3] 
    ob=Solution() 
    li=ob.subsets(a) 
    print "Ans:" ,li 

if __name__ == '__main__': 
    main() 

А вот выход:

List to append: [] 
Current ans_list: [[]] 
List to append: [1] 
Current ans_list: [[1], [1]] 
List to append: [2] 
Current ans_list: [[2], [2], [2]] 
List to append: [3] 
Current ans_list: [[3], [3], [3], [3]] 
List to append: [1, 2] 
Current ans_list: [[1, 2], [1, 2], [1, 2], [1, 2], [1, 2]] 
List to append: [1, 3] 
Current ans_list: [[1, 3], [1, 3], [1, 3], [1, 3], [1, 3], [1, 3]] 
List to append: [2, 3] 
Current ans_list: [[2, 3], [2, 3], [2, 3], [2, 3], [2, 3], [2, 3], [2, 3]] 
List to append: [1, 2, 3] 
Current ans_list: [[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]] 

Ans: [[], [], [], [], [], [], [], []] 

Я даже попытался прохождения ans_list в качестве параметра, а не глобальная переменная, но результат такой же. Даже попытался использовать словарь, чем список списков, но он приводит к такому же поведению. Однако одна интересная вещь, я отметил, когда я изменить ans_list.append(tmp) к ans_list.extend(tmp) в solve функции, то выход будет:

List to extend: [] 
Current ans_list: [] 
List to extend: [1] 
Current ans_list: [1] 
List to extend: [2] 
Current ans_list: [1, 2] 
List to extend: [3] 
Current ans_list: [1, 2, 3] 
List to extend: [1, 2] 
Current ans_list: [1, 2, 3, 1, 2] 
List to extend: [1, 3] 
Current ans_list: [1, 2, 3, 1, 2, 1, 3] 
List to extend: [2, 3] 
Current ans_list: [1, 2, 3, 1, 2, 1, 3, 2, 3] 
List to extend: [1, 2, 3] 
Current ans_list: [1, 2, 3, 1, 2, 1, 3, 2, 3, 1, 2, 3] 

Ans: [1, 2, 3, 1, 2, 1, 3, 2, 3, 1, 2, 3] 

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

Я новичок в Python и с помощью Python 2.7.10

Answer 1

Проблема заключается в том, что вы создаете TMP за пределами цикла в подмножеств(). Теперь каждое использование tmp в solve() будет указывать на тот же список, и каждое действие будет выполняться для каждого элемента в ans_list, включая pop().

Есть много способов, чтобы исправить это, но если вы хотите минимальное изменение кода просто импортировать копию модуля и изменения:

ans_list.append(tmp) 

к:

ans_list.append(copy.deepcopy(tmp)) 

редактировать (мое решение):

ans = set() 
for i in range(len(a)+1): 
    for j in range(len(a)+1): 
     ans.add(tuple(a[i:j]))