Project Euler: solution au problème 24, en Python

On commence les deux mois d'été par le suivant des problèmes eulériens, à savoir le Problème 24. Sachant ce qu'est une permutation, on précise qu'on veut obtenir les permutations d'une suite de nombres dans l'ordre lexicographique (ce qui revient à la relation d'ordre du plus petit au plus grand), et on demande quelle est la 1000000ème permutation de la liste 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

L'algorithme est plutôt évident, et j'utilise ici le copain yield qui me permet d'avoir un générateur itérable plutôt de devoir générer toutes les permutations avant d'en prendre la millionnième.

#! /usr/bin/python

# 2009/07/03 - euler024.py
# Solution au Probleme 24 de Project Euler
# http://projecteuler.net/index.php?section=problems&id=24
# Jean Karim Bockstael - jkb@jkbockstael.be


def permutations_gen(string):
    if (len(string) == 1):
        yield string
    else:
        for i in range(len(string)):
            for subperm in permutations_gen(string[:i] + string[i+1:]):
                yield string[i] + subperm

def euler24(string, num):
    cnt = 0
    for perm in permutations_gen(string):
        cnt += 1
        if cnt == num:
            return perm

print euler24("0123456789", 1000000)