03/07/2009
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)