Python - déterminer le nombre d'applications surjectives

thosmansk
thosmansk
Modifié (July 2022) dans Informatique théorique
Titre initial "Déterminer le nombre d'application surjective d'un ensemble fini En ver 1 ensemble fini Fp en Python".
Le titre doit être informatif mais court. Le corps du message est là pour les détails. AD]

Bonjour,
2 ensembles finis E à n éléments  et F à p éléments tels que 0 < p <= n.
Je voudrais créer une fonction en python "surjective (n, p)" avec en entrée "n" et "p" (ex. 3 et 2 c'est-à-dire un ensemble E = {e1, e2, e3} de 3 éléments au départ et F = {c1, c2} un ensemble de 2 éléments à l'arrivée) qui me permet de dénombrer le nombre d'applications surjectives possibles qui pourraient exister et les énumérer si possible.  Quelqu'un saurait m'aider comment le faire en python ? Ou bien exite-t-il une fonction native dans le module maths de python ?
Merci par avance de votre aide et réactivité.
Bien à vous.
Mots clés:

Réponses

  • Rescassol
    Rescassol
    Bonsoir,

    Tu n'as qu'à taper "surjection" dans google et programmer la formule sur les nombres de Stirling de deuxième espèce que tu trouveras dans Wikipédia.

    Cordialement,
    Rescassol

  • lourrran
    lourrran
    Il y a des tas de fonctions déjà écrites, et donc 1000 fois plus performantes que ce que tu pourrais faire.
    Je pense en particulier à la librairie itertools, mais mon expertise s'arrête là.

    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • Heuristique
    Heuristique
    Modifié (July 2022)
    Bonjour
    Je dirais que cela dépend du contexte : veux-tu juste les nombres et basta, ou veux-tu comprendre ce qui se passe et t'entraîner à programmer/dénombrer ?
    Dans le premier cas, prends un truc tout fait sur Internet, ça fera le boulot.
    Dans le second, n'aie pas peur de coder un truc pas du tout optimisé en premier jet : tu peux commencer par l'algo naïf, il n'a pas une complexité si horrible que ça quand on compare à l'optimum. Si tu veux les compter, tu peux essayer de trouver des relations sur les nombres $\sigma(n,p)$ que tu cherches et les calculer numériquement ensuite pour améliorer la complexité de ton algo.
    Bon courage !
  • thosmansk
    thosmansk
    Modifié (July 2022)
    Bonjour Réseau,
    Merci à tous pour vos réponses.
    J'ai déjà cherché sur Google un similaire de programme en python, mais sans succès hélas mon cher Rescassol. C'est pourquoi je me suis tourné vers vous. Alors si quelqu'un trouve quelque chose sur le Net, merci de me la faire partager. Aussi je n'ai pas encore trouvé mon bonheur dans la  librairie itertools.
    Par ailleurs, pour répondre à Heuristique, j'ai besoin juste du résultat pour faire avancer mes travaux de recherche. Peu importe l'optimisation de l'algo.
    Je sais dénombrer le nombre de relation d'application bijective; mais pas pour la surjectivité. Mais bon, je continue toujours mes recherches algorithmiques pour la surjectivité (lol) et sur le net en espérant trouver mon bonheur.
    Merci encore pour vos réactivités.
    Bien à vous mon cher réseau en restant à l'écoute.
  • thosmansk
    thosmansk
    Re-Bonjour Réseau.
    Je vais utiliser le tableau de valeurs des nombres de Stirling de seconde espèce que m'a indiqué mon cher Rescassol dans Wikipédia que je n'avais pas vu lors de mes première recherche, pour avancer dans mes travaux d'étude en attendant de trouver un programme qui donnent les mêmes résultats. Ce qui donnerait de la consistance à mes travaux de recherche. 
    Merci encore mon cher Rescassol et je reviendrai vers vous quand j'aurai trouvé quelque chose.
  • Rescassol
    Rescassol
    Modifié (July 2022)
    Bonjour,

    Pourtant, il suffit de transformer la formule suivante en Python, formule trouvée sur Wikipédia dans l'article Surjection: $\displaystyle\sum_{i=0}^p{(-1)^{p-i}\binom{p}{i}}i^n$
    A moins que ton problème soit une méconnaissance de Python ?

    Cordialement,
    Rescassol
    PS: binom se trouve dans scipy.special.

  • nicolas.patrois
    nicolas.patrois
    Peut-être qu’il cherche une méthode qui donne la liste des surjections ?
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • thosmansk
    thosmansk
    Modifié (July 2022)
    Voici la formule que j'ai utilisé :  S_(n,p)=∑_(k=0)^p▒〖〖(-1)〗^(p-k) (p¦k) 〗 k^n mais je n'arrive pas à trouver les résultats escompté. Sinon je connais bien la formule de dénombrement des applications surjectives: mais pas les subtilités du langage Python. Je voudrais avoir les résultats et la même présentation que celle de de Stirling.
  • thosmansk
    thosmansk
    Merci Nicolas pour ton aide. Mais j'ai trouvé comment énumérer la liste des surjections avec difficulté. (Lol).
    C'est plus un problème de programmation en Python comme l'a dit Rescassol.
  • Rescassol
    Rescassol
    Bonjour,

    Par exemple, sans optimisation:
    def Surjection(n,p):
    S = 0
    for k in range(p+1):
        S += (-1)**(p-k)*binom(p,k)*k**n
    return S
    Cordialement,
    Rescassol

  • thosmansk
    thosmansk
    Modifié (July 2022)
    Merci pour ta proposition Rescassol. Cependant la fonction binom() ne semble pas être connu les installation de "pip install cartopy"
    j'ai remplacé binom() par math.comb() sans succès. C'est pourquoi j'ai moi même crée les fonctions suivantes:
    def combX(ln,lp):
      l_Cb = 0
      if ln < lp:
        l_Cb = 0
      else:
        l_Cb = math.factorial(ln)/(math.factorial(lp)*math.factorial(ln-lp))
        return l_Cb
    Il fonctionne bien quand ln > lp sinon il me retourne "None" au lieu de 0 (zéro)
    Ce qui fait que je n'arrive pas à tester ma fonction "surjectiveX()":
    def surjectiveX(xn,xp):
      if xn < xp :
        x_NbSurj = 0
      else:
        x_NbSurj = 0
        for k in range(xp):
          l_Comb = 0
          l_Comb = combX(k,xp)
          print("combinaison de: (", k,",", xp,")= ",l_Comb)
          x_NbSurj = x_NbSurj + combX(k,xp)
          #x_NbSurj = x_NbSurj + (-1)**((xp+1)-k)*combX(k,(xp+1))*k**xn
      return x_NbSurj
    x_nbsj = surjectiveX(7,4)
    print("Nombre d'application surjectiveX(7,4): ", x_nbsj)
  • Rescassol
    Rescassol
    Modifié (July 2022)
    Bonsoir
    install scipy, puis from scipy.special import binom.
    Cordialement,
    Rescassol
  • thosmansk
    thosmansk
    Grand merci mon cher Rescassol pour ton assistance. Car nous trouvons les mêmes réponses, avec mes fonctions spécifiques que j'ai créées.
    Cependant, on ne trouve pas les mêmes résultats que nous proposent les nombres de James Stirling de seconde espèce.
    Qu'en penses-tu? Sais-tu comment élaborer le tableau de valeur des nombres de James Stirling de seconde espèce?

    Merci encore pour ton aide et ton temps.
  • thosmansk
    thosmansk
    Bonjour Réseau.
    J'ai le plaisir de vous dire que j'ai réussi à résoudre tous mes problèmes de programmation en python en essayant d'optimiser le mieux que j'ai pu. Ce qui me permet d'avancer considérablement  dans mes travaux de recherche.
    Mon cher Rescassol, j'ai trouvé comment élaborer le tableau de valeur des nombres de James Stirling de seconde espèce.
    Grand merci encore à vous tous.
    Bien à vous.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 9

Foysamafhh +7 Invités