Bonjour,

Je suis récemment tomber sur un problème qui me pose ... problème !

Soit une grille de dimension d1xd2x...dn et un point de départ x1,x2,...,xn

De combien de manière peut on faire M pas (un pas correspond ajouter + ou - 1 à l'une des coordonnées de la positon courante) sans sortir de la grille (on sort de la grille si un des xi est <= 0 ou > di.

J'ai écris un petit algorithme récursif en python qui fonctionne mais qui est à la fois lent et très coûteux en mémoire (voir dans la suite). Je me dis qu'il doit exister une solution plus directe mais après plusieurs jours de réflexion (et de recherche sur internet :p ) je n'ai rien trouver de satisfaisant. Quelqu'un a t'il une idée ?

Voila mon programme (je n'ai pas trouver de balise de formatage de code) (le résultat est afficher modulo un gros nombre premier (10000000007) :


#! /usr/bin/python
import sys
from collections import defaultdict

ddp = defaultdict(lambda : 0)

bp = 1000000007

def genmoves(point,dim) :
    moves = []
    count = 0
    for x,d in zip(point,dim) :
        if x>1 :
            t = point[:]
            t[count]-=1
            moves.append(t)
        if x<d :
            t = point[:]
            t[count]+=1
            moves.append(t)
        count+=1
    return moves
def gennmoves(point,dim) :
    nmoves = 0
    for x,d in zip(point,dim) :
        if x>1 :
            nmoves+=1
        if x<d :
            nmoves+=1
    return nmoves


def numberofways(point,dim,steps) :
    global ddp
    tup = tuple(point+[steps])
    t = tup[:-1]
    if ddp[t] == 0 :
        ddp[t] = genmoves(point,dim)
    if ddp[tup] > 0 :
        return ddp[tup]
    elif steps == 1 :
        nmove = gennmoves(point,dim)
        ddp[tup] = nmove
        return nmove
    else :
        moves= ddp[t]
        res = sum([numberofways(move,dim,steps-1) for move in genmoves(point,dim)])
        res%=bp
        ddp[tup] = res
        return res

et on lance le problème de la manière suivante :


x = [1,2,3]
d = [10,10,10]
m = 15

print numberofways(x,d,m)

Je me rends bien compte que ce n'est pas un forum d'informatique mais je pense qu'il existe une solution combinatoire que je ne n'arrive pas trouver

Je vous remercie d'avance

Cordialement

Ortholle