RE: algorithm help ?

It sounds like this is two problems. First you want to select 19 numbers between 1 and 49. Then you want to figure all of the possible permutations (or combinations, there is a big difference here) of those numbers. If I read you correctly for any given 19 numbers you will have 19*18*17*16*15*14 =aprox 20 million permutations. If you really want cominations (the difference is whether order matters or not. i.e. is 1 2 3 4 5 6 the same as 1 2 3 5 4 6, if so you want a permutation, if not you want a combination) the formula for determining the number of combinations is C(n,r) = n!/((n-r)!r!) where n is the number of items (19 in this subcase) and r is the number of items chose (6 in this case).This drops the number of combinations for EACH group of 19 numbers to a mere 27,000 combinations per group. If you multiply this times the number of groups of 19 numbers out of 49 (or C(49,19) = 49!/(30!*19!) = 18.8 x 10^12) you end up with a whopping 5 x 10^17 combinations, which is a whole lot more than your web server can do anything with in less time than your max_execution_time value is set to (even if it's running linux ;) ) All this to say (rather obtusely), what do you want to do with the combinations? Do you really need to work them all out, or can you narrow down the unnecessary ones by some other criteria. There are a lot of cases where an exact solution is not practical, but a reasonable guess can be good enough. This may be one of those cases. To generate permutations, I have always used (though there may be much more efficient ways) nested for loops. $a[1..19] = list of 19 numbers for i = 1 to 19 for j = 1 to 19 if j==i then j++ for k = 1 to 19 if k==(j|i) then k++ for L = 1 to 19 if L == (k|j|i) then L++ for m = 1 to 19 if m== (L|k|j|i) then m++ for n = 1 to 19 if n == (m|L|k|j|i) then n++ $permutation = a[i].a[j].a[k].a[L].a[m].a[n] next n next m next L next k next j next I I apologize for the horrible syntax, but hopefully you get the jist. To generate combinations, do similarly. for i = 1 to 19 for j = 2 to 19 if j==i then j++ for k = 3 to 19 if k== (j|i) then k++ etc... ........ as I think further, I'm not so sure about the combination generator. Any suggestions?? John Parker > -----Original Message----- > From: Gianni Ponzi [SMTP:gianni@adept.co.za] > Sent: Friday, December 29, 2000 3:47 AM > To: php-general@lists.php.net > Subject: algorithm help ? > > ok > > this is what i'd like to do.... > > I'd like to be able to select 19 numbers between 1 and 49 and work out > the permutations / combinations of those numbers in groups of six. > > eg 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19 > > results: > > 1 2 3 4 5 6 > 1 2 3 5 6 7 > 1 2 3 6 7 8 > > > and so on..... > > I have looked around a bit and I believe the way it should be done is > in the Linear Reduction method ? ( if this means anything). I haven't > had any luck as I'm not that hot when it comes to mathematics > > do you think you could help ? > > Thanks for the time > Gianni >