Algorthom for lottery draw

[bioshock]

does anybody know any algorithom that will chose k numbers form n numbers where k<n(random)
i want to create a lottery drawing system

 

[essellar]

There are a couple of ways to go about it. The simplest is to create an array of all possible numbers, shuffle the array, then either pop or shift off the required number of choices. (In PHP, you can do the shuffling with array_rand().) Since pseudorandom number generators are far from perfect (and array_rand() uses mt_rand()), this doesn't actually create an "every ticket can win" scenario. Slightly (and only slightly) more complex, but likely to be fairer, is to create two different shuffled arrays of the numbers, pop or shift off the required number of selections from one array and use that result as the index to fetch the drawn number from the other array.

 

[dlukin]

n = number of balls in bucket
k = number of balls to draw

bucket = Array( n );
winners = Array( k );

for( i = 0 , j = 1 ; i < n ; j++ , i++ ){
    bucket[ i ] = j ;  # throw the numbered balls into the bucket...
}

for( i = 0 ; i < k ; i++ ){
   pick = rand( i , n - 1 ) ;  # pick from 'remaining balls' ... number between i and n-1
   winners[ i ] = bucket[ pick ] ;
   bucket[ pick ] = bucket[ i ] ; # replace picked ball with 'top' ball 
}

 

[misson]

That's basically the Fisher-Yates shuffle. You're not likely to find much better, as the modern version requires O(n) space and has O(k) time complexity. The only difference is the modern Fisher-Yates shuffles in place; the picked numbers are held in the same array that holds the unpicked numbers at one end or the other (in your sample, bucket[0..i] would be the winning numbers).

Stackoverflow has many questions along these lines. Look over them if you want more.