Wie kann ich die Anzahl der Permutationen in der Basis 3 Kombinatorik berechnen?

https://stackoverflow.com/questions/447783

22-07-2019
|

Frage

Ich habe noch nie für Mathe viel gewesen, und ich bin die Hoffnung, dass jemand mir mit folgenden helfen kann.

Ich habe 5 Boxen:

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

Die Boxen können entweder weiß, grau oder schwarz (oder betrachten Sie es als 0, 1, 2)

Wie viele mögliche Zustände kann die Box sein?

Was ist der Pseudo-Code (oder in einer beliebigen Sprache), um alle möglichen Ergebnisse zu generieren ??

also ...

etc, etc ...

Ich schätze wirklich jede Hilfe jemand mir mit diesem geben kann.

Lösung

Dies ist eine klassische Permutation Generation Problem. Sie haben 3 Möglichkeiten für jede Position und 5-Positionen. Die Gesamtzahl der erzeugten Zeichenfolge ist 3 ^ 5 = 243. Sie müssen Rekursion, wenn Sie eine allgemeine Lösung wollen (eine einfache iterative Schleife nur für eine einzelne Instanz des Problems arbeitet).

Hier ist ein kleines Beispiel:

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);
    }
}

Andere Tipps

die Antwort für die Anzahl von Kombinationen ist: 3x3x3x3x3 (3 ^ 5), da jede Box 3 mögliche Farben haben kann

Wie für die Ergebnisse zu erzeugen, sehen, wenn Sie es aus mit dieser Matrix mit 0 Abbildung können, 1 oder 2, um die Farbe der Box darzustellen. In kleinerem Maßstab (Nehmen wir an, 3 Boxen) es würde wie folgt aussehen:

Um Ihre erste Frage zu beantworten, was wäre die Antwort, wenn die Boxen nur einer von zwei Werten enthalten könnten? Also, was ist die Antwort, wenn die Boxen einen von drei Werten enthalten?

Ihre zweite Frage zu beantworten, welche Pseudo-Code generiert alle möglichen Ergebnisse einer Box? Nun Pseudo-Code generiert alle möglichen Ergebnisse von zwei Boxen?

Ich würde empfehlen, das Problem auf dem Papier zu lösen zuerst. Versuchen Sie es mit einer kleineren Anzahl von Boxen zu lösen (vielleicht drei), und alle Möglichkeiten aufzulisten. Dann denken Sie an, wie Sie Ihre Argumentation ging, oder wie würden Sie erklären, was Sie zu einem kleinen Kind getan hat.

Vielen Dank für Ihre Antworten, zumindest diejenigen, die man tatsächlich gab mir.

Während ich zu schätzen wissen, dass die Frage klang wie es gerade aus der Informatik 101 gezogen wurde, war es nicht. Die Ironie an der Sache ist, dass es für die wirkliche Leben auf einer echte Frist war, und ich habe keine Zeit, um zu horchen zu haben, als ich dieses Zeug gelehrt wurde, und sagte zu mir: „Wenn ich mich jemals diesen Mist gehen zu müssen“

Wenn ich wie ein Schuljunge zu bevormundet werden und behandelt wollte würde ich zu meiner Grundschule gehen zurück und fragen meine 5. Klasse Lehrer, wenn I können auf die Toilette gehen

Danke nochmal

die Anzahl der Zustände ist 3 ^ 5.

Pseudo-Code ist

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

wo base3 ist eine Funktion, die wiederholt Modulo 3 nimmt eine Stelle zu bekommen, dann die Ziffer (durch Division durch 3) entfernt

Hinweis: sich vorstellen, dass jede Box eine Position in einer Reihe ist und jede Farbe ist eine andere Ziffer. In der realen Welt, wie viele Kombinationen (einschließlich Null) bekommt man mit 2 Positionen und 10 möglichen Stellen? Was etwa 3 Positionen? Was ist die Beziehung eine zusätzliche Position und die Anzahl der Kombinationen zwischen dem Hinzufügen, da die Anzahl der Ziffern, die Sie zur Verfügung haben?

Einzigartige Anzahl von Kombinationen: 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
}

Hier ist, wie ich gelernt, dies zuerst zu tun: zuerst darüber nachdenken, wie viele Entscheidungen, die Sie machen. Sie machen fünf Möglichkeiten, einen für jede Box. So aufzuschreiben fünf Leerzeilen mit Multiplikationszeichen:

__ x __ x __ x __ x __ = ?

In jedem Zuschnitt, schreibt die Anzahl der Objekte, die Sie aus für das Feld zur Auswahl. Da Sie 3 Zahlen zur Auswahl für jede Box, schreiben Sie eine 3 in alle blank:

3 x 3 x 3 x 3 x 3 = 243

Das gibt Ihnen die Gesamtzahl der Permutationen für diese Entscheidungen.

Die Anzahl der Möglichkeiten ist 3 potenziert 5

Wenn Sie Schleife von 0 bis diese Zahl minus 1 und drücken Sie es in der Basis 3 Sie alle Möglichkeiten haben werden (denken Sie daran 0s vorangestellt wird, wo erforderlich)

In 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

Darf ich fragen, was ist das Sie nicht verstehen, oder was Stolpern Sie sich? Ich sehe, dass jeder hier hat einfach die Frage beantwortet, aber wenn Sie ihre Antworten kopiert haben, Sie haben nichts gelernt und damit vollständig den Punkt der Hausaufgaben verpasst. Angenommen, Ihre nächste Lektion baut auf diesen einen, Sie gehen einfach weiter hinten fallen.

Wenn Sie entweder für mich gearbeitet oder waren in meiner Klasse würde ich einfach folgende fragen ...

„Wie denken Sie, das Problem gelöst werden soll?“ Die Antwort, auf die vielleicht verraten, wo Sie bis zu werden gehängt sind. Ein weiser Professor von mir an der CMU sagte einmal: „Ich kann Ihnen nicht helfen, zu verstehen, bis Sie wissen, was Sie nicht verstehen“ ich herausfinden, nie tat, was ich nicht verstand, und ich ließ seine Klasse, aber die Lektion stecken mit ich.

Ich weiß, dass es wahrscheinlich zu spät, aber für diese Hausaufgaben Fragen, die ich denke wirklich, wir sollten die Person erfahren werden helfen, im Gegensatz zu einfach eine Antwort zu geben und ihre Hausaufgaben für sie zu tun.

Ihr Problem braucht nichts mehr als die Regel Produkt in Kombinatorik rel="nofollow.

Sie können den Zustand der wählen Sie zuerst Box auf 3 Arten, und den Zustand der zweiten Box auf 3 Arten, und ... und den Zustand der 5. Kasten auf 3 Arten. Die Anzahl der Möglichkeiten, in denen Sie den Zustand aller Boxen eingestellt kann, ist das Produkt aller fünf (gleich) Anzahl von Wegen, das heißt 3x3x3x3x3 = 3 ⁵.

ähnliche Frage: Wie viele Zahlen können Sie mit 5 Ziffern im Dezimalsystem bilden, die führenden Nullen zu zählen? Das heißt, wie viele Zahlen gibt es 00.000 bis 99.999? Sie können die erste Ziffer in 10 Möglichkeiten wählen (0 ... 9), und so weiter und so weiter, und die Antwort ist 10x10x10x10x10 = 100000, wie Sie bereits wissen.

Dies scheint ein Hausaufgaben Problem. Ich werde Ihnen nur etwas Hilfe geben in Bezug auf die Lösung dann.

Was Sie sagen, ist, dass jedes Feld drei Zustände hat, die alle unabhängig sind. Eine Box würde drei Lösungen hat, und zwei Boxen haben würden 3 * 3-Lösungen - für jeden Zustand des ersten Feldes der zweite Box als auch drei Staaten haben würde. Erweitern Sie das zu 5 Boxen.

jede Lösung generieren, können Sie einfach durchlaufen sie. Es ist einfach für Schleifen für jede Box verschachtelte zu machen, und durch Potenzen von 10 multiplizieren kann können Sie die Nummer auf einmal zeigen.

Sie können den Code für mehrere Boxen in ähnlicher Weise verallgemeinert werden.

Noch nicht einmal versuchen, Code zu schreiben, dies zu beantworten! Der Grund dafür ist, dass Sie einige sehr große Zahlen (factorials) müssen sie berechnen. Diese schaffen Zahlen viel größer als jeder Basistyp in der CLR. Sie können diese verwenden Open-Source-Bibliothek die Berechnung zu tun.

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);
    }
}

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow