Función recursiva de Python para mostrar todos los subconjuntos de un conjunto dado

Tengo la siguiente función de python para imprimir todos los subconjuntos de una lista de números:

def subs(l): if len(l) == 1: return [l] res = [] for sub in subs(l[0:-1]): res.append(sub) res.append([l[-1]]) res.append(sub+[l[-1]]) return res li = [2, 3, 5, 8] print(subs(li)) 

Esto devuelve:

 [[2], [8], [2, 8], [5], [8], [5, 8], [2, 5], [8], [2, 5, 8], [3], [8], [3, 8], [5], [8], [5, 8], [3, 5], [8], [3, 5, 8], [2, 3], [8], [2, 3, 8], [5], [8], [5, 8], [2, 3, 5], [8], [2, 3, 5, 8]] 

Que no es la respuesta esperada. Parece que Python toma la lista l en la función por referencia. Entonces, cuando agrego l [-1], agrega el último elemento de la lista original, no la lista más pequeña enviada al método recursivo. ¿Hay alguna forma de resolver esto?

Esto podría resolverse usando tuplas, pero me pregunto si hay una solución utilizando listas.

 def subs(l): if l == []: return [[]] x = subs(l[1:]) return x + [[l[0]] + y for y in x] 

Resultados:

 >>> print (subs([1, 2, 3])) [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]] 

Hay un módulo de Python conveniente para ayudar:

 import itertools def subs(l): res = [] for i in range(1, len(l) + 1): for combo in itertools.combinations(l, i): res.append(list(combo)) return res 

Los resultados son:

 >>> subs([1,2,3]) [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]] 

En realidad, no hay ningún problema con la llamada de Python por referencia, como pensé originalmente. En ese caso, l [-1] sería 8 en todas las llamadas recursivas. Pero l [-1] es 3, 5, 8 respectivamente en las llamadas recursivas. Esta función modificada resuelve el problema:

 def subs(l): if len(l) == 1: return [l] res = [] subsets = subs(l[0:-1]) res = res+subsets res.append([l[-1]]) for sub in subsets: res.append(sub+[l[-1]]) return res 

devoluciones:

 [[2], [3], [2, 3], [5], [2, 5], [3, 5], [2, 3, 5], [8], [2, 8], [3, 8], [2, 3, 8], [5, 8], [2, 5, 8], [3, 5, 8], [2, 3, 5, 8]] 
 def rec_subsets(S, n): # S is set and n is length of set if n == 0: res = [[]] + [S] if len(S) > 2: res += [S[:n] + S[n+1:]] + [[S[n]]] return res else: return [S[:n] + S[n+1:]] + rec_subsets(S, n - 1) + [[S[n]]] lst = [1,2,3] rec_subsets(lst, len(lst) - 1) [[1, 2], [1, 3], [2, 3], [], [1, 2, 3], [1], [2], [3]] 

Esto parece funcionar.

Por favor, sugiera mejoras si las hubiera.

Mejorando en la respuesta de @Miguel Matos.

 def subsets(set_inp): if set_inp == []: return [[]] x = subsets(set_inp[1:]) return sorted( x + [[set_inp[0]] + y for y in x]) print(subsets([1,2,3]))