Réécrire le rendu glouton sans supposer les pièces triées

def rendu_general(somme, pieces):
    """Glouton ecrit SANS trier : a chaque tour, la plus grosse piece qui tient.

    Precondition : 1 in pieces. Aucune hypothese d'ordre sur pieces.
    Variant      : reste, qui decroit strictement (toute piece vaut >= 1).
    """
    assert somme >= 0 and 1 in pieces
    rendu, reste = [], somme
    while reste > 0:
        p = max(x for x in pieces if x <= reste)
        rendu.append(p)
        reste -= p
    assert sum(rendu) == somme
    return rendu

assert rendu_general(67, [1, 2, 5, 10, 20, 50, 100, 200]) == [50, 10, 5, 2]
assert rendu_general(8, [1, 4, 6]) == [6, 1, 1]

for _ in range(500):
    s = random.randint(0, 300)
    melangees = random.sample(EURO, len(EURO))       # ordre quelconque
    assert sorted(rendu_general(s, melangees), reverse=True) == rendu_monnaie(s, EURO)

La précondition d'ordre a disparu, remplacée par un calcul. Le max recherché à chaque tour fait le travail que le tri faisait une fois pour toutes. C'est plus robuste et plus coûteux : le tri paie une fois, le max paie à chaque pièce rendue. Sur une somme de $999$ centimes rendue en pièces de $1$, la différence devient sensible.

La précondition 1 in pieces reste indispensable, et pour une raison nouvelle : sans elle, le max pourrait ne trouver aucune pièce $\le$ reste, et lèverait ValueError: max() arg is an empty sequence. La boucle ne terminerait pas non plus — le variant reste cesserait de décroître.

Le test aléatoire mélange les pièces à chaque tour : c'est la seule façon de vérifier que l'ordre n'a réellement plus d'importance. Comparer à la version triée exige de retrier le résultat, puisque les pièces ne sortent pas dans le même ordre.