Bepaling aantal permutaties van X uit Y met een restrictie.
Bepaling aantal permutaties van X uit Y met een restrictie.
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?
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?
Re: Bepaling aantal permutaties van X uit Y met een restrict
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, ... ??
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, ... ??
Re: Bepaling aantal permutaties van X uit Y met een restrict
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
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
Re: Bepaling aantal permutaties van X uit Y met een restrict
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
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.
Re: Bepaling aantal permutaties van X uit Y met een restrict
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:
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:
Re: Bepaling aantal permutaties van X uit Y met een restrict
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.
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.
Re: Bepaling aantal permutaties van X uit Y met een restrict
- 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/):
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)??
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) }
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)??
Re: Bepaling aantal permutaties van X uit Y met een restrict
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];
}
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];
}
Re: Bepaling aantal permutaties van X uit Y met een restrict
Hier kan enorm veel tijdwinst behaald worden:
is gelijk aan:
er van uit gaande dat je Faculteit() functie een faculteit berekent.
Code: Selecteer alles
c2 = _c1array[j - 1, i] / Faculteit(j - 1) * Faculteit(j);
Code: Selecteer alles
c2 = _c1array[j - 1, i] * j;
Re: Bepaling aantal permutaties van X uit Y met een restrict
Helaas, dit is bekende materie.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
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.
Re: Bepaling aantal permutaties van X uit Y met een restrict
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.
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.
Re: Bepaling aantal permutaties van X uit Y met een restrict
Arie, in je 'multiply met binom(y,z)' stukje code zit een foutje:
moet zijn:
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?
Code: Selecteer alles
r = r*(y+1-z);
Code: Selecteer alles
r = r*(y+i-z);
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?
Re: Bepaling aantal permutaties van X uit Y met een restrict
[1]
Ik bedoelde eigenlijkmaar 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:
Hoewel ik verwacht dat zo'n soort pow()-versie in BigInt geimplementeerd is.
Staat nog open:
Ik bedoelde eigenlijk
Code: Selecteer alles
r = r*(y+1-i);
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);
}
Staat nog open:
tsagld schreef:Stephan, hoe slim is jouw BigInt class?
Re: Bepaling aantal permutaties van X uit Y met een restrict
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.
Had hetzelfde truc geprobeerd voor de vermenigvuldiging, maar ook dat werd alleen maar trager.
Re: Bepaling aantal permutaties van X uit Y met een restrict
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)
(Raffiek Torreman)