C# Problème de factoriel qui vaut 0

bonjour,

J'ai écrit une méthode pour générer une liste de caractère sans répétition. Dans cette méthode (qui fonctionne) je calcule la taille de de ma boucle while pour avoir le nombre de combinaison possible avec une variable

Code:

---

1 2	long numberCombination = factorial(alpha.Count - 1) / factorial(NumberOfChar - 1) * factorial((alhpa.Count - 1) - (NumberOfChar - 1));

---

J'ai écrit la méthode factorial au dessus de la méthode pour calcule la taille de la liste de caractère comme ceci.

Code:

---

1 2 3 4 5 6 7

private long factorial(int x) { if (x == 0) return 1; if (x < 2) return 1; return x * factorial(x - 1); }

---

Quand ma liste est avec ces caractère "abcdefghijklmnopqrstuvwxyz" cela fonctionne.


Par contre quand je rajoute plus de caractère comme par exemple "abcdefghijklmnopqrstuvwxyz0123456789!@#$%^&*()-_+" ma variable numberCombination vaut 0 et ma boucle ne s’exécute pas et rien est générer. :(

As tu essayé de mettre un point d'arrêt ? et de prendre le temps de lire les variables mises dans les fonctions ? parfois ça aide ^^

Bonjour,

Merci de ta réponse. C'est avec un point d'arrêt que j'ai trouver le bug. Dans le code j'ai créé une vaviable test comme ceci :

Code:

---

1 2	long numberCombination = factorial(alpha.Count - 1) / factorial(NumberOfChar - 1) * factorial((alhpa.Count - 1) - (NumberOfChar - 1)); long test += numberCombination; // égal 0

---

Je comprend pas que je mets 26 lettre cela fonctionne (numberCombination == 240) est quand je met plus de lettre c'est égal à 0. C'est pas logique !

Peux tu mettre plus de code histoire de voir à quoi correspond les variables etc ^^ s'il te plait

EDIT :

Je voudrais revenir sur ta condition, un int peut être positif ou négatif. Or tu as mis :

Code:

---

1 2 3

if(a == 0) return 1; if(a < 2) return 1;

---

Donc s'il est inférieur à 2, il appartient à l'intervalle [-infini; 1] et 0 est compris dans cet intervalle, donc juste if(a < 2) return 1; (dans ton cas)

Je met pas le contenu du while qui fait 300 ligne mais en gros ma classe a ces deux méthodes.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

private long factorial(int x) { if (x == 0) return 1; if (x < 2) return 1; return x * factorial(x - 1); }   private List<string> Generate( int NumberOfChar ) { List<string> alpha = new List<string>(){"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};   List<string> resultat = new List <string>();   long numberCombination = factorial(alpha.Count - 1) / factorial(NumberOfChar - 1) * factorial((alhpa.Count - 1) - (NumberOfChar - 1));     While( i < numberCombination) { /*Boucle While qui génére les combinaison pour retourner resultat (en t'autre), mais qui ne s’exécute pas quand je met   plus de caractère dans la liste alpha*/. i++; }   return resultat }

---

Ce qui fonctionne pas c'est quand j'ai une liste plus grand comme ci-dessous et ma boucle while ne s’exécute pas.

Code:

---

1 2	List<string> alpha = new List<string>(){"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","0","1","2","3","4","5","6","7","8","9"}

---

J'ai tous tester et déboguer et mon code ne fonctionne qu'avec une liste de moins de 26 caractère.

A savoir qu'un factoriel de 6 = 6 * 5 * 4 * 3 * 2

Donc j'ai revu ta fonction factorielle. Par contre dans le paramètre de Generate j'ai mis au pif et je n'obtiens pas 0 je te laisse regarder.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

static void Main(string[] args) { Console.WriteLine(Generate(10).ToString()); Console.Read(); }   private static long factorial(int x) { long buffer = 1; while(x > 1) //tant que x est supérieur a 1 { buffer = buffer * x; // je multiple x--; // je decremente mon x } return buffer; }   private static long Generate(int NumberOfChar) { List<string> alpha = new List<string>() { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" };   List<string> resultat = new List<string>();   return factorial(alpha.Count - 1) / factorial(NumberOfChar - 1) * factorial((alpha.Count - 1) - (NumberOfChar - 1));   }

---

et j'obtiens Pièce jointe 184960

Après pour ce qu'il s'agit de ta fonction sache qu'il y a aussi des propriétés mathématiques sur les langages de programmations car j'ai réussit à tomber sur des résultats négatifs !

EDIT : une boucle de 300 lignes !!! j'espère qu'elles sont bien organisées car elles peuvent être source d'erreur

Avec une liste de 36 caractères, tu te retrouves à calculer la factorielle de 36, qui est un nombre gigantesque : environ 1.0333147966386144929666651337523e+40, soit beaucoup plus que la capacité d'un entier de 64 bits... Du coup tu obtiens un dépassement de capacité.

Je vois au moins 2 options pour résoudre le problème :

- utiliser le type BigInteger, qui gère des entiers de longueur illimitée. Simple, mais pas très efficace
- utiliser une autre approche pour calculer le nombre de combinaisons, en évitant de passer par de très grands nombres. La méthode décrite sur Wikipedia semble appropriée: https://fr.wikipedia.org/wiki/Combin...e_combinaisons

Citation:

---

Envoyé par tomlev

Avec une liste de 36 caractères, tu te retrouves à calculer la factorielle de 36, qui est un nombre gigantesque : environ 1.0333147966386144929666651337523e+40, soit beaucoup plus que la capacité d'un entier de 64 bits... Du coup tu obtiens un dépassement de capacité.

Je vois au moins 2 options pour résoudre le problème :

- utiliser le type BigInteger, qui gère des entiers de longueur illimitée. Simple, mais pas très efficace
- utiliser une autre approche pour calculer le nombre de combinaisons, en évitant de passer par de très grands nombres. La méthode décrite sur Wikipedia semble appropriée: https://fr.wikipedia.org/wiki/Combin...e_combinaisons

---

Exact en y repensant je me suis dit mais oui il fait de très gros calcul, d'où les combinaisons négatives.
D'après moi l'utilisation d'une variable double (à la place du long) peut te permettre de factoriel jusqu'à 171.

EDIT : 36! = 3.719933267899012e+41 :)

Citation:

---

Envoyé par Kangourex

Exact en y repensant je me suis dit mais oui il fait de très gros calcul, d'où les combinaisons négatives.
D'après moi l'utilisation d'une variable double (à la place du long) peut te permettre de factoriel jusqu'à 171.

---

Oui, sauf que comme ce n'est plus un entier, tu n'as plus une valeur exacte

Citation:

---

Envoyé par Kangourex

EDIT : 36! = 3.719933267899012e+41 :)

---

Exact, ce que j'ai mis dans mon message c'est 35! en fait

Merci de vos réponse, j'ai testé cette après midi est ça fonctionne avec un double.
Ce qui me semble bizarre car je croyez le long plus grand. Par contre j'ai du limitée ma boucle while à 60 000 000 à cause de la liste qui est limité à 2 giga.

Citation:

---

Je vois au moins 2 options pour résoudre le problème :

---

Je suis null en math se qui me sauve c'est ma logique, je garde la premier solution dans un coin de ma tête au cas ou par contre pour la deuxième je vois pas comment coder la calcul.

Citation:

---

Exact, ce que j'ai mis dans mon message c'est 35! en fait.

---

Comment je peut limité le nombre pour pas que ça plante, avec nombre caractère maximum ? Ou je doit limité la taille de la liste à combien ?

Bah si chaque tour de boucle ajoute qu'un élément :

Pièce jointe 184988

Après faut savoir que c'est énorme ce que tu demandes faut travailler sur des algorithmes complexes aussi bien mathématiques mais informatiques, utilisé un autre langage aussi plus rapide par exemple en python j'avais eu les anagrammes quasiment 10 fois plus vite qu'avec le C# sur le même algo.

Peut-être trouvé une table arc-en-ciel et faire une requête serait plus simple la partie calcul serait déjà mâche en quelque sorte... Bien sûr je te donne une expérimentation je ne sais pas le résultat.

Citation:

---

Envoyé par juju742

Merci de vos réponse, j'ai testé cette après midi est ça fonctionne avec un double.
Ce qui me semble bizarre car je croyez le long plus grand.

---

Le type double a une plage de valeurs plus grande (de -1.79769313486232e308 à +1.79769313486232e308), mais c'est moins précis (+1.79769313486232, c'est équivalent à un entier avec plein de 0 derrière... donc tu perds tous les chiffres "de poids faible"). La valeur que tu obtiens n'est donc pas exacte.

Citation:

---

Envoyé par juju742

Je suis null en math se qui me sauve c'est ma logique, je garde la premier solution dans un coin de ma tête au cas ou par contre pour la deuxième je vois pas comment coder la calcul.

---

Et alors ? y a pas besoin d'être bon en maths, il suffit d'appliquer la formule. Y a même un exemple de déroulé du calcul pour que ce soit clair.

Allez, c'est cadeau ;)

Code:

---

1 2 3 4 5 6 7 8 9

long NbCombinaisons(int n, int k) { long product = 1; for (int i = 1; i <= k; i++) { product = product * (n - k + i) / i; } return product; }

---

(n étant le nombre de caractères possibles, et k le nombre de caractères à prendre)

Et hop, plus besoin de factorielle :)

Mon algo ne fait aucune répétition. K est le nombre de caractère répété ? Comme k - 1 comme mon algo ne répété pas de caractère ? Ou le nombre total de caractère moins k ?

n = alpha.Count
k = NumberOfChar

Merci à vous tous pour votre aide précieuse. Au plaisir de vous revoir.:D