I want to generate a group of items at 25 different locations. The part I need help with is to generate them without wasting processing power. Basically I can say random 0-24 and then apply the item to the number location. But then, if the loop runs a second time, whatever location is taken up wont be a solution, so the random number has to be generated again.
This would be okay if the pool wasnt so large. But once 23 locations are taken up, the loop will continue to persist until the last two numbers are randomly selected. This might sound confusing but if anyone out there understands, then maybe you, with your infinite wisdom, can suggest an algorithm that eliminates selected numbers in a pool as it chooses them.
Need a bit more details before I can attempt to help. Are your locations preset? Or random over the map? Because it sounds to me like they are preset..
Do you have 25 items that have attached numbers like 1,2,3,4 and you wish to spawn item 1 at location 1, where location 1 is a random location amongst 25 different locations?
Take a looky at this thread .... I flesh out some trigger examples that are basically the same kinda thing but your spawning items instead of nydus cannals
That will not give you an unbiased result. That algorithm does N number of random swaps. Thus permutations that require less swaps have more ways to be generated than ones that require close to N swaps. Another way of putting it is that if you were to go through every case of doing N swaps, you would count some permutations more than others, so they would be more likely to come up. It's better to use the Fisher-Yates shuffle (as outlined below), as it counts every permutation only once.
You have a set of locations and you want to assign them to a set of items. The classic way of doing this unbiasedly that everyone is familiar with is to assign them numbers, toss them into a hat and pick them out randomly one by one to generate a permutation. When you do this, it doesn't even matter in what order you assign the numbers to the items. For instance, for 4 items/locations, we randomly generate the sequence a={1,0,3,2} and each item[i] will correspond to Location[a[i]]. The locations have thus been randomly and unbiasedly shuffled (provided your permutation have been randomly and unbiasedly generated).
The actual generation of the permutation goes as follows. You set up a sequence of numbers 0-24 and pick one randomly (since we're picking randomly it doesn't matter if you have an ordered sequence of numbers or a random distribution in a hat). Then you swap this number with the very last number to keep track of it. Now the remaining unshuffled numbers are in the first 24 elements and your shuffled one is in the last element, which is no longer part of the pool. This is repeated for the remaining pool until no elements are left. The algorithm is then
Int[N] a = {0,1,2,....,N-1}
For int i From N-1 to 1; i-- do
int k = RandInt(0, i);
swap a[k], a[i]
I want to generate a group of items at 25 different locations. The part I need help with is to generate them without wasting processing power. Basically I can say random 0-24 and then apply the item to the number location. But then, if the loop runs a second time, whatever location is taken up wont be a solution, so the random number has to be generated again.
This would be okay if the pool wasnt so large. But once 23 locations are taken up, the loop will continue to persist until the last two numbers are randomly selected. This might sound confusing but if anyone out there understands, then maybe you, with your infinite wisdom, can suggest an algorithm that eliminates selected numbers in a pool as it chooses them.
^_^ Thanks
Need a bit more details before I can attempt to help. Are your locations preset? Or random over the map? Because it sounds to me like they are preset..
Do you have 25 items that have attached numbers like 1,2,3,4 and you wish to spawn item 1 at location 1, where location 1 is a random location amongst 25 different locations?
Take a looky at this thread .... I flesh out some trigger examples that are basically the same kinda thing but your spawning items instead of nydus cannals
http://forums.sc2mapster.com/development/triggers/14948-solved-storing-points-with-a-random-id/
@BasicGear: Go
@Naim2k10: Go
That will not give you an unbiased result. That algorithm does N number of random swaps. Thus permutations that require less swaps have more ways to be generated than ones that require close to N swaps. Another way of putting it is that if you were to go through every case of doing N swaps, you would count some permutations more than others, so they would be more likely to come up. It's better to use the Fisher-Yates shuffle (as outlined below), as it counts every permutation only once.
@BasicGear: Go
You have a set of locations and you want to assign them to a set of items. The classic way of doing this unbiasedly that everyone is familiar with is to assign them numbers, toss them into a hat and pick them out randomly one by one to generate a permutation. When you do this, it doesn't even matter in what order you assign the numbers to the items. For instance, for 4 items/locations, we randomly generate the sequence a={1,0,3,2} and each item[i] will correspond to Location[a[i]]. The locations have thus been randomly and unbiasedly shuffled (provided your permutation have been randomly and unbiasedly generated).
The actual generation of the permutation goes as follows. You set up a sequence of numbers 0-24 and pick one randomly (since we're picking randomly it doesn't matter if you have an ordered sequence of numbers or a random distribution in a hat). Then you swap this number with the very last number to keep track of it. Now the remaining unshuffled numbers are in the first 24 elements and your shuffled one is in the last element, which is no longer part of the pool. This is repeated for the remaining pool until no elements are left. The algorithm is then
Int[N] a = {0,1,2,....,N-1} For int i From N-1 to 1; i-- do int k = RandInt(0, i); swap a[k], a[i]