Comment calculer le nombre de permutations en combinatoire en base 3?

https://stackoverflow.com/questions/447783

22-07-2019
|

Question

Je n'ai jamais beaucoup travaillé en mathématiques et j'espère que quelqu'un pourra m'aider avec ce qui suit.

J'ai 5 cases:

 1   2   3   4   5
[ ] [ ] [ ] [ ] [ ]

Les cases peuvent être blanches, grises ou noires (ou les attribuer à 0, 1, 2)

Dans combien d'états le coffret peut-il être?

Quel est le pseudocode (ou dans n’importe quel langage) pour générer tous les résultats possibles?

c'est-à-dire ...

etc, etc ...

J'apprécie vraiment toute aide que n'importe qui peut me donner avec cela.

La solution

C’est un problème classique de génération de permutation. Vous avez 3 possibilités pour chaque position et 5 positions. Le nombre total de chaînes générées est 3 ^ 5 = 243. Vous avez besoin de récursion si vous souhaitez une solution générale (une simple boucle itérative ne fonctionne que pour une seule instance du problème).

Voici un exemple rapide:

public static void Main(string[] args){

    Generate("", 5);
}

private void Generate(string s, int limit)
{
    if (s.Length == limit)
        Console.WriteLine(s);
    else
    {
        Generate(s+"0", limit);
        Generate(s+"1", limit);
        Generate(s+"2", limit);
    }
}

Autres conseils

la réponse pour le nombre de combinaisons est: 3x3x3x3x3 (3 ^ 5) puisque chaque case peut avoir 3 couleurs possibles.

En ce qui concerne la génération des résultats, voyez si vous pouvez le comprendre en utilisant cette matrice avec 0, 1 ou 2 pour représenter la couleur de la zone. Sur une plus petite échelle (supposons 3 cases), cela ressemblerait à ceci:

Pour répondre à votre première question, quelle serait la réponse si les cases ne pouvaient contenir qu'une seule des deux valeurs? Alors, quelle est la réponse si les cases contiennent l’une des trois valeurs suivantes?

Pour répondre à votre deuxième question, quel pseudocode génère tous les résultats possibles d’une boîte? Maintenant, le pseudocode génère tous les résultats possibles de deux boîtes?

Je recommanderais d'abord de résoudre le problème sur papier. Essayez de le résoudre avec un plus petit nombre de cases (peut-être trois) et dressez la liste de toutes les possibilités. Ensuite, réfléchissez à votre raisonnement ou à la manière dont vous expliqueriez ce que vous avez fait à un petit enfant.

Merci à tous pour vos réponses, du moins à ceux d'entre vous qui m'en ont donné une.

Bien que je puisse comprendre que la question semblait provenir d’Informatique 101, ce n’était pas le cas. L’ironie de la chose, c’est que c’était vraiment pour une vraie date limite et que je n’avais pas le temps de me rappeler à quel moment on m’enseignait ce genre de choses et je me disais, "quand vais-je avoir besoin de cette merde" ;

Si je voulais être fréquenté et traité comme un écolier, je retournerais à mon école primaire et demanderais à mon professeur de 5e année si je pouvais aller aux toilettes

Merci encore

le nombre d'états est 3 ^ 5.

pseudocode est

for value from 0 to 3^5-1
    print base3(value)

où base3 est une fonction qui prend à plusieurs reprises le modulo 3 pour obtenir un chiffre, puis supprime ce chiffre (en divisant par 3)

Astuce: imaginez que chaque case est une position dans un nombre et que chaque couleur est un chiffre différent. Dans le monde réel, combien de combinaisons (y compris zéro) obtenez-vous avec 2 positions et 10 chiffres possibles? Qu'en est-il des 3 positions? Quelle est la relation entre l'ajout d'une position supplémentaire et le nombre de combinaisons, en fonction du nombre de chiffres disponibles?

Nombre unique de combinaisons: 3 ^ 5 = 243

Code:

n = 0
for i = 0 to 3^5-1
{
    s = ""
    for j = 1 to 5
    {
        d = n mod 3
        s = toascii(d) . s
        n = n / 3
    }
    println s
    i = i + 1
}

Voici comment j’ai appris à le faire: réfléchissez au nombre de choix que vous faites. Vous faites cinq choix, un pour chaque case. Alors écrivez cinq lignes vides avec des signes de multiplication:

__ x __ x __ x __ x __ = ?

Dans chaque espace, écrivez le nombre d'objets que vous devez choisir pour cette case. Étant donné que vous avez le choix entre 3 chiffres pour chaque case, vous écrivez un chaque espace:

3 x 3 x 3 x 3 x 3 = 243

Ceci vous donne le nombre total de permutations pour ces choix.

Le nombre de possibilités est de 3 à la puissance 5

Si vous passez de 0 à ce nombre moins 1 et l'exprimez en base 3, vous aurez toutes les possibilités (n'oubliez pas de préfixer des 0 si nécessaire)

En Ruby:

number_of_possibilities = 3**5-1

for i in (0..number_of_possibilities)
  base_3_number = i.to_s(3)
  puts "%05d" % base_3_number # number formatting used to prepend 0s where necessary
end

Puis-je vous demander ce que vous ne comprenez pas ou ce qui vous fait trébucher? Je constate que tout le monde ici a simplement répondu à la question, mais si vous avez copié ses réponses, vous n’avez rien appris et vous avez donc complètement manqué l’objet du devoir. En supposant que votre prochaine leçon se base sur celle-ci, vous ne pourrez plus vous laisser distancer.

Si vous travailliez pour moi ou si vous étiez dans ma classe, je demanderais simplement ce qui suit ...

"Comment pensez-vous que le problème devrait être résolu?" La réponse à cette question pourrait révéler où vous êtes en train de raccrocher. Un de mes professeurs avisés à la CMU a un jour déclaré: "Je ne peux pas vous aider à comprendre cela avant de savoir ce que vous ne comprenez pas". Je n'ai jamais compris ce que je ne comprenais pas et j'ai abandonné son cours, mais la leçon me tient à coeur.

Je sais que c'est probablement trop tard, mais pour ces questions sur les devoirs, je pense vraiment que nous devrions aider la personne à apprendre plutôt que de simplement fournir une réponse et faire ses devoirs à sa place.

Votre problème n'a plus besoin que de la règle de produit en combinatoire.

Vous pouvez choisir l'état de la première case de 3 manières, et l'état de la seconde de 3 manières, et ... et l'état de la 5ème case de 3 manières. Le nombre de façons dont vous pouvez définir l’état de toutes les cases est le produit des cinq nombres (égaux) de façons, c’est-à-dire 3x3x3x3x3 = 3 ⁵.

Question similaire: combien de nombres pouvez-vous former avec 5 chiffres dans le système décimal, en comptant les zéros de tête? Autrement dit, combien de chiffres y a-t-il entre 00000 et 99999? Vous pouvez choisir le premier chiffre de 10 manières différentes (0 à 9), etc., et ainsi de suite. La réponse est 10x10x10x10x10 = 100000, comme vous le savez déjà.

Cela semble être un problème de devoirs. Je vais simplement vous donner une aide quant à la solution, puis.

Ce que vous dites, c’est que chaque case a trois états, qui sont tous indépendants. Une case aurait 3 solutions, et deux cases auraient 3 * 3 solutions - pour chaque état de la première case, la seconde case aurait également trois états. Étendez-le à 5 cases.

Pour générer chaque solution, vous pouvez simplement la parcourir. Il est facile de créer des boucles imbriquées pour chaque case, et multiplier par 10 pour vous permettre d'afficher le nombre à la fois.

Vous pouvez généraliser le code pour plusieurs boîtes de la même manière.

N'essayez même pas d'écrire du code pour répondre à cela! La raison en est que vous avez besoin de très grands nombres (factorielles) pour le calculer. Ceux-ci créent des nombres beaucoup plus grands que n'importe quel type de base dans le CLR. Vous pouvez utiliser cette bibliothèque opensource pour effectuer le calcul.

void solve(int p=0,int n=5,int d=0)
{
    if (n==p)
    {
        int rev=d;
        int i=0;
        while (i<5) {
            cout << rev%10;
            rev /= 10;
            i++;## Heading ##
        }
        cout << endl;
        return;
    }
    for(int i=0; i<3 ; i++)
    {
        solve(p+1,n, d*10 + i);
    }
}

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow