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)

Ta fonction suffix_sequences est juste. Pour power_list, tu as réussi à en écrire une version non seulement juste, mais terminale (ce n'était pas demandé). Le calcul de l'indice a l'air d'être le fruit d'une intense réflexion, je te croirai sur parole (ça continue à marcher sur des listes plus grandes). Ceci dit, je pense que le gain (théorique) apporté par la récursivité terminale doit être annulé par les calculs complexes (celui de la ligne 11 en tout cas pourrait être fait une fois pour toutes).

Je ne sais pas si, avant d'écrire cette version, tu en as aussi écrit une version non terminale. Dans ce cas je suis très très impressionné. Quant à moi je n'ai pas cherché plus loin. Mais du coup tu as piqué ma curiosité: je vais essayer de voir si j'y arrive sans faire tous ces calculs.

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 ;)