Bepaling aantal permutaties van X uit Y met een restrictie.

Wiskunde is niet alleen een vak op school. Kom je ergens in de praktijk (bijvoorbeeld tijdens je werk) een wiskundig probleem tegen dan kun je hier om hulp vragen.
Plaats reactie
Stephan
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 13 feb 2013, 18:08

Bepaling aantal permutaties van X uit Y met een restrictie.

Bericht door Stephan » 14 feb 2013, 18:09

Hoe ziet de functie F(x,y,z) eruit waarvoor geldt:

Een oneindig aantal personen trekken precies X ballen uit een bak met oneindig veel ballen met Y kleuren. Alle personen die precies Z verschillende kleuren hebben getrokken sturen een email met in het subject de kleuren van de achtereen getrokken ballen.

Hoeveel verschillende! email subjects ontstaan er? Dit aantal is F(x,y,z). Hoe ziet deze functie eruit?

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Bepaling aantal permutaties van X uit Y met een restrict

Bericht door arie » 15 feb 2013, 01:24

De vraag is in feite: je trekt een rij van x ballen met daarin precies z (uit y mogelijke) kleuren, hoeveel verschillende rijtjes zijn er mogelijk voor gegeven (x,y,z).

Het aantal verschillende manieren R(x,z) waarop je rijtjes van lengte x met precies z verschillende kleuren kan inkleuren =
het aantal surjectieve afbeeldingen |S(x,z)| van een verzameling met x elementen naar een verzameling met z elementen.

Dit aantal kan je tellen met (bijvoorbeeld) het principe van inclusie en exclusie,
zie bv. onderaan http://www.cs.duke.edu/courses/cps102/s ... s/L-15.pdf
(de paragraaf "Counting surjective functions")

Hoe luidt die formule in ons geval?
R(x,z) = ...

Waar moet je R(x,z) nog mee vermenigvuldigen om F(x,y,z) te krijgen?
Dus:
F(x,y,z) = ...


Is dit zuiver een praktijkprobleem of ben je ook bezig met combinatoriek, inclusie/exclusie, genererende functies, ... ??

Stephan
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 13 feb 2013, 18:08

Re: Bepaling aantal permutaties van X uit Y met een restrict

Bericht door Stephan » 15 feb 2013, 12:18

Bedankt voor je antwoord.

Ik ben zelf geen wiskundige maar heb op basis van een numerieke for-loop een aantal resultaten laten berekenen d.m.v. een computer programma. Het spreekt voor zich dat dit enorm lang duurt zodra x,y of z een groot getal worden. Vandaar dat ik aan het puzzelen ben gegaan met de resultaten van een aantal 'kleine' x,y en z waardes. Na een hoop gepuzzel van uitkomsten heb ik op basis hiervan een hele vage computer-routine gefabriceerd die alle uitkomsten lijkt te kunnen reproduceren. Dit keer niet op basis van een for-loop, maar op basis van sommaties van diverse N! en C(N,K) functies.

Ik vroeg me af of deze routine overeen kwam met wat de wiskunde voor dit probleem beschrijft.
Uit de pdf kon ik overigens niet direct afleiden of het een en ander dezelfde uitkomst geeft, vandaar dat ik een aantal uitkomsten hieronder heb opgesomd. Kan iemand dit controleren met de formule als beschreven in de pdf? Mijn uitkomsten zijn correct. Alvast bedankt!

Stephan

F(7,8,4) = 588000
F(4,6,2) = 210
F(8,16,6) = 1533692160
F(16,32,12) = 298196460205427976192000

(voor de gein,... als iemand het durft na te rekenen)
F(80,160,60) = 162652513618048781825655510007265152104050479646796059637518070435273448744530
1665990685622533987325178639136170961709698151938740497387457220070419214919480115200000000
0000000

Gebruikersavatar
barto
Vergevorderde
Vergevorderde
Berichten: 654
Lid geworden op: 07 jun 2011, 16:02

Re: Bepaling aantal permutaties van X uit Y met een restrict

Bericht door barto » 15 feb 2013, 15:35

Dit komt op hetzelfde neer:
Genummerde ballen

Het antwoord op jouw vraag wordt dan .
Ik zou dus niet hopen op een mooie formule als resultaat.

p.s: ik heb het nagerekend en het klopt:
http://www.wolframalpha.com/input/?i=bi ... i%29^80%29
Given that, by scientifical reasons, the state of an object is completely determined by the physical influence of its environment, the probability to roll six with a dice is either one or zero.

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Bepaling aantal permutaties van X uit Y met een restrict

Bericht door arie » 15 feb 2013, 16:41

In welke taal werk je?
Hoe ziet jouw routine er uit?
Lukt het je ook om bovenstaande formule daarin te schrijven?


PS: de sommatie hoeft maar tot z-1: de laatste term in de formule van barto (dus als i=z) is altijd nul. Dus voor een minimale tijdwinst in je programma gebruik je:


Stephan
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 13 feb 2013, 18:08

Re: Bepaling aantal permutaties van X uit Y met een restrict

Bericht door Stephan » 15 feb 2013, 17:57

Ik programmeer in C# (.NET). Ik heb een eigen implementatie gemaakt van een integer-object waarbij ik de lengte zelf kan bepalen (qua aantal bits). Hierdoor kan ik rekenen met enorm grote getallen (int32, int64, maar dus ook een int65536 etc).

De formule lijkt heel erg veel op mijn routine, maar ik gebruik nergens de + en - termen in de reeksontwikkeling aangegeven door de -1^i term.

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Bepaling aantal permutaties van X uit Y met een restrict

Bericht door arie » 17 feb 2013, 10:08

- tav je formule:
Ik ben nu wel benieuwd hoe jouw formule (de sommatie zonder +/-) er uit ziet.

- tav je implementatie:
Als ik onze formule omzet in Pari/GP (http://pari.math.u-bordeaux.fr/):

Code: Selecteer alles

F(x,y,z)={ binomial(y,z)*sum(i=0,z-1,binomial(z,i)*(z-i)^x*(-1)^i) }
dan vind ik:
F(1000000,100000,10000) = F(10^6, 10^5, 10^4) =
6.2796525127172250433858032139889920524033035332154... * 10^4014115
(berekend met volledige nauwkeurigheid, dus alle 4014116 cijfers)
Dit kost me wel meer dan een uur rekentijd.
Hoe snel is jouw C# programma met deze berekening (ik vermoed veel sneller)??

Stephan
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 13 feb 2013, 18:08

Re: Bepaling aantal permutaties van X uit Y met een restrict

Bericht door Stephan » 18 feb 2013, 12:19

Mijn routine ziet er alsvolgt uit. Ik heb nog geen snelheidsoptimalisaties gedaan omdat ik eerst het algoritme werkend wilde hebben. Zoals je ziet is het uitsluitend een herhaald optellen en vermenigvuldingen.
Mocht het zo zijn dat ik iets nieuws heb ontdekt in de wiskunde, laat mij het ff weten. Dan kan ik meedoen in de credits :-)

Stephan

public static BigInt Calculate(int X, int Y, int Z)
{
var _c1array = new BigInt[X + 1, X + 1];
var _c2array = new BigInt[X + 1, X + 1];
var _results = new BigInt[X + 1, X + 1];

for (int i = 1; i <= X; i++)
{
_c2array[1, i] = 0;
}

BigInt c1 = Faculteit(2);
BigInt c2 = 2;
for (int i = 2; i <= X; i++)
{
BigInt kuitn = KuitN(2, i);
_c1array[2, i] = c1;
_c2array[2, i] = 2;
c1 = c1 * 2 + c2;
}

for (int j = 3; j <= X; j++)
{
c1 = Faculteit(j);
c2 = _c1array[j - 1, j] / Faculteit(j - 1) * Faculteit(j);
for (int i = j; i <= X; i++)
{
c2 = _c1array[j - 1, i] / Faculteit(j - 1) * Faculteit(j);
_c1array[j, i] = c1;
_c2array[j, i] = c2;
c1 = c1 * j + c2;
_c1array[j - 1, i] = null; // memory save
}
}

for (int j = 1; j <= Z; j++)
{
BigInt c3 = Faculteit(j);
for (int i = j; i <= X; i++)
{
_results[j, i] = c3 * KuitN(j, Y);
c3 = c3 * j + _c2array[j, i];
}
}

return _results[Z, X];
}

tsagld
Vergevorderde
Vergevorderde
Berichten: 341
Lid geworden op: 23 mar 2009, 12:07
Contacteer:

Re: Bepaling aantal permutaties van X uit Y met een restrict

Bericht door tsagld » 21 feb 2013, 14:09

Hier kan enorm veel tijdwinst behaald worden:

Code: Selecteer alles

c2 = _c1array[j - 1, i] / Faculteit(j - 1) * Faculteit(j);
is gelijk aan:

Code: Selecteer alles

c2 = _c1array[j - 1, i] * j;
er van uit gaande dat je Faculteit() functie een faculteit berekent.

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Bepaling aantal permutaties van X uit Y met een restrict

Bericht door arie » 24 feb 2013, 14:59

Stephan schreef:Mocht het zo zijn dat ik iets nieuws heb ontdekt in de wiskunde, laat mij het ff weten. Dan kan ik meedoen in de credits :-)
Helaas, dit is bekende materie.

We hadden:



dit kunnen we herschrijven als:



en dit is precies gelijk aan



waarbij S(x,z) de Stirling-getallen van de tweede soort zijn,
zie bv http://nl.wikipedia.org/wiki/Stirling-g ... eede_soort

Deze kunnen we direct berekenen, maar ook recursief, vergelijkbaar met wat jij gedaan hebt.
We gebruiken dan:



Hiermee berekenen we eerst S(x,z), vervolgens vermenigvuldigen we dit resultaat met




In Java ziet deze versie van jouw algoritme er zo uit:
(merk op dat het lukt met sterk verminderd geheugengebruik)

Code: Selecteer alles

public static BigInt Calculate_v2(int x, int y, int z)
{
var s = new BigInt[z + 1];
var r = new BigInt;

for (int j = 2; j <= x; j++)
  s[j] = 0;
s[1]=1;

for(int i = 2 ; i <= x; i++)
  for(int j = z; j > 1; j--)
    s[j] = s[j]*j + s[j-1];
r=s[z];

for(int j = y-z+1; j <= y; j++)
  r = r*j;

return(r);
}

Terug naar onze formule:



Als we deze direct in Java implementeren krijgen we de derde versie, met nog veel minder geheugengebruik:

Code: Selecteer alles

public static BigInt Calculate_v3(int x, int y, int z)
{
var b = new BigInt; // = bin coef
var p = new BigInt; // = power
var t = new BigInt; // = term
var r = new BigInt; // = result

// calculate sigma:
// -->  first term first:
p = z;
r = p.pow(x);
// -->  then all other terms:
b = 1;
for (int i = 1; i < z; i++)
  {
  b = b*(z+1-i);
  b = b/i;
  p = z-i;
  p = p.pow(x);
  t = b*p;
  if(i%2==1)
    r = r-t;
  else
    r = r+t;
  }

// multiply by binom(y,z):
for(int i = 1; i <= z; i++)
  {
  r = r*(y+1-z);
  r = r/i;
  }

return(r);
}


PS:
Ik heb geen Java op mijn computer, kan iemand bovenstaande codeblokken s.v.p. even testen?
Ik ben ook benieuwd naar de prestaties in Java:
- snelheid = ?
- lukt F(1000000,100000,10000) met versie 3 ?
Noot: Pari/GP heeft voor de laatste berekening bij mij ongeveer 64 minuten nodig, zie mijn eerdere post.

tsagld
Vergevorderde
Vergevorderde
Berichten: 341
Lid geworden op: 23 mar 2009, 12:07
Contacteer:

Re: Bepaling aantal permutaties van X uit Y met een restrict

Bericht door tsagld » 25 feb 2013, 10:58

Er wordt gebruik gemaakt van Stephan's eigen BigInt class, in C#.
Lastig testen dus, behalve door Stephan zelf. De syntax van jouw Java code is identiek aan die van C#, dis kan zonder meer gekopieerd worden.

tsagld
Vergevorderde
Vergevorderde
Berichten: 341
Lid geworden op: 23 mar 2009, 12:07
Contacteer:

Re: Bepaling aantal permutaties van X uit Y met een restrict

Bericht door tsagld » 25 feb 2013, 11:59

Arie, in je 'multiply met binom(y,z)' stukje code zit een foutje:

Code: Selecteer alles

r = r*(y+1-z);
moet zijn:

Code: Selecteer alles

r = r*(y+i-z);
Ik ben nu F(1000000, 100000, 10000) in C# aan het draaien, met de standaard .Net 4.5 BigInteger class. Uitkomst volgt....

Edit:
Heb hem afgebroken. Duurt vijf minuten per iteratie, dat gaat ruim vijf weken duren.
Zit hem vrijwel uitstluitend in het machtsverheffen. Stephan, hoe slim is jouw BigInt class?

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Bepaling aantal permutaties van X uit Y met een restrict

Bericht door arie » 26 feb 2013, 00:07

[1]
Ik bedoelde eigenlijk

Code: Selecteer alles

r = r*(y+1-i);
maar jouw verbetering volstaat ook.
Misschien moet ik toch maar eens een Java compiler instaleren...

[2]
Dank je voor de tijdmeting.
Ik had niet verwacht dat Pari/GP zoveel sneller was.

Zou je ipv de standaard pow() mogelijk deze power() eens een keer willen uitproberen:

Code: Selecteer alles

public static BigInt power(BigInt a, int n)
{
var r = new BigInt;   // result
var p2 = new BigInt;  // iterated squaring of a

r = 1;
p2 = a;
while(n>0){
  if(n%2==1)
    r = r.multiply(p2);
  n/=2;
  if(n>0)
    p2 = p2.multiply(p2);
  }
return(r);
}
Hoewel ik verwacht dat zo'n soort pow()-versie in BigInt geimplementeerd is.

Staat nog open:
tsagld schreef:Stephan, hoe slim is jouw BigInt class?

tsagld
Vergevorderde
Vergevorderde
Berichten: 341
Lid geworden op: 23 mar 2009, 12:07
Contacteer:

Re: Bepaling aantal permutaties van X uit Y met een restrict

Bericht door tsagld » 26 feb 2013, 12:09

Die slimme Pow functie had ik al geprobeerd maar bleek alleen maar trager...
Had hetzelfde truc geprobeerd voor de vermenigvuldiging, maar ook dat werd alleen maar trager.

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: Bepaling aantal permutaties van X uit Y met een restrict

Bericht door David » 26 feb 2013, 15:41

Liever helemaal geen machten? Anders misschien ook deze whileloop (met zelfde initialisaties):

Code: Selecteer alles

while(n>0){
  r = r.multiply(p2^(n%2));
  n/=2;
  p2 = p2.multiply(p2);
}
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

Plaats reactie