[VB.Net] 14 Karakters, alle mogelijkheden berekenen

[fleppuhstein]

Ik ben bezig met een stukje code waarbij ik 14 karakters heb in een array. Van deze array wil ik alle unieke mogelijkheden berekenen en weergeven. Een karakter mag slecht 1 maal gebruikt worden.
Dus het aantal mogelijkheden is : 14x13x12x11x10x enz...

Alleen hoe is dit efficient te doen, ik kan wel 14 loops op starten, en steeds de karakters die ik gebruik in een tweede array op locked zetten, en vervolgens de check uit te voeren. Maar dan loopt mijn applicatie vast, en toont geen error.

Is er een betere manier van bereken van alle unieke mogelijkheden ?

[Creepy]

Zoek eens op permutatie of permutation

[kunnen]

Je wilt alle unieke mogelijkheden berekenen en weergeven? Je beseft dat dit er 14! = 87 178 291 200 zijn?

[KopjeThee]

Pulsher schreef op vrijdag 14 september 2007 @ 21:01:
Je wilt alle unieke mogelijkheden berekenen en weergeven? Je beseft dat dit er 14! = 87 178 291 200 zijn?

Bedenk dit inderdaad goed. Wegschrijven in een bestand zou wel eens een paar GB kunnen gaan kosten.

Het makkelijkst kan je dit soort dingen recursief oplossen, denk ik. Een eerste poging (niet gecontroleerd, C-achtig):

code:

void perm(int* list, int n)
{
  if (n == 1)
  {
    print(list);
    return;
  } 

  for (int i = 0; i < n; ++i)
  {
    swap(list, n - 1, i);
    perm(list, n - 1);
  }
}

Het idee zou zijn om met een array met de getallen 1 t/m 14 te beginnen. Je verwisselt telkens de laatste positie met een ander getal uit de rest van de lijst. Dan weet je zeker dat je elk getal een keer op de laatste positie hebt gehad. Vervolgens/daarbinnen doe je hetzelfde met dezelfde met dezelfde lijst, maar dan zonder het laatste getal. Het algoritme eindigt bij een lijst van lengte 1, want daarvan kan je makkelijk alle permutaties bepalen...

Nogmaals: dit is niet gecontroleerd, maar het zal niet ver van een mogelijke oplossing afliggen :-)

[Verwijderd]

KopjeThee schreef op zaterdag 15 september 2007 @ 11:31:
Bedenk dit inderdaad goed. Wegschrijven in een bestand zou wel eens een paar GB kunnen gaan kosten.

1.11 TB...

[Sjaaky]

Zoals de TS aangeeft wil hij het aantal unieke mogelijkheden berekenen. Dat wil niet zeggen dat hij ze ook allemaal in een bestand wil hebben.

Er is een simpele formule om uit te rekenen wat het aantal unieke mogelijkheden zijn. En die kun je vinden door de aanwijzing van Creepy te volgen.

Ik neem aan dat je binnen die 14 karakters dubbele karakters kunt hebben, anders geef je zelf namelijk het antwoord al.
Voorbeeld:
Bij BOEM is het aantal permutaties 6! = 24. Bij BOOM is het 12, omdat alle permutaties waar de O's met elkaar verwisselt zijn niet meetellen.

edit: hmm misschien toch iets te slecht gelezen.

[ Voor 4% gewijzigd door Sjaaky op 15-09-2007 18:29 ]

[prototype]

Sjaaky schreef op zaterdag 15 september 2007 @ 17:44:
Zoals de TS aangeeft wil hij het aantal unieke mogelijkheden berekenen. Dat wil niet zeggen dat hij ze ook allemaal in een bestand wil hebben.

Er is een simpele formule om uit te rekenen wat het aantal unieke mogelijkheden zijn. En die kun je vinden door de aanwijzing van Creepy te volgen.

Ik neem aan dat je binnen die 14 karakters dubbele karakters kunt hebben, anders geef je zelf namelijk het antwoord al.
Voorbeeld:
Bij BOEM is het aantal permutaties 6! = 24. Bij BOOM is het 12, omdat alle permutaties waar de O's met elkaar verwisselt zijn niet meetellen.

Ofwel 6!/2! in dat laatste geval: hoe deze berekening verloopt wordt uitvoerig in de discrete wiskunde behandeld waar dit gewoon een standaard telprobleem is.

Verder is het niet geheel duidelijk imho uit de TS-post op te maken of het nou gaat om het berekenen van het aantal mogelijkheden of alle daadwerkelijke permutaties verkrijgen. Misschien is het daarbij toch ook even handig om te vragen wat voor doeleinden TS precies voor ogen heeft met dit, want wellicht is dit iets dat TS eigenlijk helemaal niet wil...

[Engineer]

.

[ Voor 114% gewijzigd door Engineer op 14-10-2018 10:51 ]