Come calcolo il numero di permutazioni nella combinatoria di base 3?

https://stackoverflow.com/questions/447783

22-07-2019
|

Domanda

Non sono mai stato molto per la matematica e spero che qualcuno possa aiutarmi con quanto segue.

Ho 5 scatole:

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

Le caselle possono essere bianche, grigie o nere (o considerarle come 0, 1, 2)

In quanti possibili stati può essere impostato il box?

Qual è lo pseudocodice (o in qualsiasi lingua) per generare tutti i possibili risultati ??

vale a dire ...

etc, etc ...

Apprezzo davvero qualsiasi aiuto che qualcuno possa darmi in questo.

Soluzione

Questo è un classico problema di generazione di permutazione. Hai 3 possibilità per ogni posizione e 5 posizioni. Il numero totale della stringa generata è 3 ^ 5 = 243. Hai bisogno di ricorsione se desideri una soluzione generale (un semplice ciclo iterativo funziona solo per una singola istanza del problema).

Ecco un breve esempio:

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

Altri suggerimenti

la risposta per il numero di combinazioni è: 3x3x3x3x3 (3 ^ 5) poiché ogni scatola può avere 3 colori possibili.

Per quanto riguarda la generazione dei risultati, vedi se riesci a capirlo usando questa matrice con 0, 1 o 2 per rappresentare il colore del riquadro. Su una scala più piccola (supponiamo che 3 caselle) sia simile a questo:

Per rispondere alla tua prima domanda, quale sarebbe la risposta se le caselle potessero contenere solo uno dei due valori? Quindi, qual è la risposta se le caselle contengono uno dei tre valori?

Per rispondere alla tua seconda domanda, quale pseudocodice genera tutti i possibili risultati di una casella? Ora, lo pseudocodice genera tutti i possibili risultati di due caselle?

Consiglio innanzitutto di risolvere il problema sulla carta. Prova a risolverlo con un numero inferiore di caselle (forse tre) ed elenca tutte le possibilità. Quindi, pensa a come sono andati i tuoi ragionamenti o come spiegheresti cosa hai fatto a un bambino piccolo.

Grazie a tutti per le risposte, almeno quelle di voi che mi hanno dato una.

Mentre posso apprezzare che la domanda sembrava essere stata tirata fuori da Computer Science 101, non lo era. L'ironia della questione è che era per la vita reale in una vera scadenza e non ho avuto il tempo di rispondere a quando mi è stato insegnato questa roba e mi sono detto, "quando avrò mai bisogno di questa schifezza "" ;

Se volevo essere patrocinato e trattato come un ragazzo di scuola, tornerei alla mia scuola elementare e chiederei al mio insegnante di quinta elementare se posso andare in bagno

Grazie ancora

il numero di stati è 3 ^ 5.

pseudocodice è

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

dove base3 è una funzione che richiede ripetutamente modulo 3 per ottenere una cifra, quindi rimuove quella cifra (dividendo per 3)

Suggerimento: immagina che ogni casella sia una posizione in un numero e che ogni colore sia una cifra diversa. Nel mondo reale, quante combinazioni (incluso lo zero) ottieni con 2 posizioni e 10 cifre possibili? Che dire di 3 posizioni? Qual è la relazione tra l'aggiunta di una posizione aggiuntiva e il numero di combinazioni, dato il numero di cifre che hai a disposizione?

Numero unico di combinazioni: 3^5=243

Codice:

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
}

Ecco come ho imparato per la prima volta a fare questo: prima pensa a quante scelte stai facendo. Stai facendo cinque scelte, una per ogni scatola. Quindi scrivi cinque righe vuote con segni di moltiplicazione:

__ x __ x __ x __ x __ = ?

In ogni spazio vuoto, scrivi il numero di oggetti che devi scegliere per quella casella. Dato che hai 3 numeri tra cui scegliere per ogni casella, scrivi 3 in ogni vuoto:

3 x 3 x 3 x 3 x 3 = 243

Questo ti dà il numero totale di permutazioni per quelle scelte.

Il numero di possibilità è 3 rispetto alla potenza 5

Se esegui il ciclo da 0 a quel numero meno 1 e lo esprimi nella base 3 avrai tutte le possibilità (ricorda di anteporre 0 se necessario)

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

Posso chiederti cosa non capisci o cosa ti fa inciampare? Vedo che tutti qui hanno semplicemente risposto alla domanda, ma se hai copiato le loro risposte, non hai imparato nulla e quindi hai completamente perso il punto dei compiti. Supponendo che la tua prossima lezione si basi su questa, rimarrai più indietro.

Se o hai lavorato per me o facessi parte della mia classe, ti chiedo semplicemente quanto segue ...

" Come pensi che il problema debba essere risolto? " La risposta a cui potrebbe rivelare dove sei stato bloccato. Un mio saggio professore alla CMU una volta disse: "Non posso aiutarti a capirlo finché non sai cosa non capisci" Non ho mai capito cosa non capivo e ho lasciato la sua lezione, ma la lezione è rimasta con me.

So che probabilmente è troppo tardi, ma per queste domande a casa penso davvero che dovremmo aiutare la persona a imparare invece di fornire semplicemente una risposta e fare i compiti per loro.

Il tuo problema non richiede altro che la regola del prodotto in combinatoria.

Puoi scegliere lo stato della prima casella in 3 modi, e lo stato della seconda casella in 3 modi, e ... e lo stato della 5a scatola in 3 modi. Il numero di modi in cui è possibile impostare lo stato di tutte le caselle è il prodotto di tutti e cinque i (uguali) numeri di modi, ovvero 3x3x3x3x3 = 3 ⁵.

Domanda simile: quanti numeri puoi formare con 5 cifre nel sistema decimale, contando gli zeri iniziali? Cioè, quanti numeri ci sono da 00000 a 99999? Puoi scegliere la prima cifra in 10 modi (0 ... 9) e così via e così via, e la risposta è 10x10x10x10x10 = 100000, come già sai.

Sembra un problema a casa. Allora ti darò solo un aiuto per quanto riguarda la soluzione.

Quello che stai dicendo è che ogni casella ha tre stati, che sono tutti indipendenti. Una scatola avrebbe 3 soluzioni e due scatole avrebbero 3 * 3 soluzioni - per ogni stato della prima scatola anche la seconda scatola avrebbe tre stati. Estendilo a 5 caselle.

Per generare ogni soluzione, puoi semplicemente scorrere attraverso di essa. È facile annidare i loop per ogni casella e la moltiplicazione per potenze di 10 può farti mostrare il numero in una sola volta.

Puoi generalizzare il codice per più caselle in modo simile.

Non provare nemmeno a scrivere codice per rispondere a questa domanda! Il motivo è che hai bisogno di numeri molto grandi (fattoriali) per calcolarlo. Questi creano numeri molto più grandi di qualsiasi tipo di base nel CLR. Puoi utilizzare questa libreria opensource per eseguire il calcolo.

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

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow