power_list.py

def suffix_sequences(suffix, seq):
    result = []
    for l in seq:
        result.append(l+[suffix])
    return result
    

from math import log

def power_list(seq, result=[[]]):
    if 2**len(seq) == len(result):
        return result
    else:
        result += suffix_sequences(seq[int(log(len(result), 2))], result)
        return power_list(seq)

Oui, j'y arrive en m'inspirant de ce que tu as fait:

def power_list(sequence, result = [[]]):
    if sequence == []:
        return result
    return power_list(sequence[1:], result + suffix_sequences(sequence[0], result))

Joli. Je n'y avais pas pensé du tout. Bravo à toi!

Voici ma correction officielle (non terminale):

def power_list(sequence):
    if sequence == []:
        return [[]]
    parts = power_list(sequence[:-1])
    return parts + suffix_sequences(sequence[-1], parts)

C'est encore un recyclage de mon cours de programmation fonctionnelle. Pour ta culture, voici la version OCaml (l'ordre est changé pour être plus proche de l'ordre naturel des listes chaînées d'OCaml):

let prefix_lists x ll = List.map (fun l-> x::l) ll;;
let rec parts = function
    | [] -> [[]]
    | x::l -> let lpl = parts l in lpl @ prefix_lists x lpl;;

Pour comprendre ça, tu as besoin de savoir que:

• f a b c veut dire: fonction f appliquée aux arguments a, b et c (noté f(a,b,c) dans la plupart des langages);
• List.map f [a1; a2; ...; an] calcule [f a1; f a2; ...; f an];
• fun l -> x::l se lit: la fonction (anonyme) qui prend une liste l et renvoie x::l;
• :: est le constructeur des listes, par exemple 1::[2; 3] construit la liste [1; 2; 3];
• Le pipe | permet de faire un filtrage (pattern matching), un peu comme une série de tests, sauf que l'on teste non pas exactement la valeur, mais sa forme. Ça se lit: parts est une fonction qui, quand on lui envoie une liste vide, renvoie une liste réduite à la liste vide; et quand on lui envoie une liste de tête x et de queue l, renvoie tout le truc de droite;
• @ désigne la concaténation de listes.

Ouf!

Et pour finir les deux fonctions en une seule ligne:

def power_list(l, r = [[]]):
    return power_list(l[1:], r + [s + [l[0]] for s in r]) if l else r

C'est tout de suite plus clair ;)

Merci pour la version non terminale, j'ai pas réussi à la faire, surtout après avoir utiliser un "for" dans une version récursive
Et les programmes d'une ligne je trouve ça toujours impressionnant

PS: arrêtez de me faire des compliments je vais croire que je suis trop bon

Si tu n'es pas bon, en tout cas tu travailles et c'est le meilleur moyen de le devenir ;)