tag:blogger.com,1999:blog-7225373.post4425606393163873123..comments2024-02-29T03:34:23.190-05:00Comments on Who Were the Sea Peoples?: Algorithm Bleggcallahhttp://www.blogger.com/profile/10065877215969589482noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-7225373.post-54274460549223097832015-02-25T13:36:54.426-05:002015-02-25T13:36:54.426-05:00Exactly. N agents, pick the first N elements from ...Exactly. N agents, pick the first N elements from a shuffled list.<br /><br />(This could be a problem if the number of elements is >> N. But in that case then in fact the chance of collisions will be slim and you can just generate random numbers. )Ken Bhttps://www.blogger.com/profile/12976919713907046171noreply@blogger.comtag:blogger.com,1999:blog-7225373.post-82844799420644802092015-02-25T10:11:54.211-05:002015-02-25T10:11:54.211-05:00Nice rob!Nice rob!gcallahhttps://www.blogger.com/profile/10065877215969589482noreply@blogger.comtag:blogger.com,1999:blog-7225373.post-81528539140982009192015-02-25T10:07:00.120-05:002015-02-25T10:07:00.120-05:00You could always traverse the grid looking for an...You could always traverse the grid looking for an empty space , but just start the search from a random place and go back to 0,0 when you reach the end of the grid without having found an empty slot.<br />robhttps://www.blogger.com/profile/04682517711551179057noreply@blogger.comtag:blogger.com,1999:blog-7225373.post-43948245837965155242015-02-24T19:45:54.875-05:002015-02-24T19:45:54.875-05:00Thanks for the great suggestions! The newest post ...Thanks for the great suggestions! The newest post shows what I did, based on these.gcallahhttps://www.blogger.com/profile/10065877215969589482noreply@blogger.comtag:blogger.com,1999:blog-7225373.post-52184770656072250532015-02-24T17:23:07.039-05:002015-02-24T17:23:07.039-05:00Create an array that stores available cells as a p...Create an array that stores available cells as a pair of x- and y-coordinates and used your random number generator to select a coordinate pair in that array. Remove said item after selection.Samson Corwellhttps://www.blogger.com/profile/10148822362930969284noreply@blogger.comtag:blogger.com,1999:blog-7225373.post-6556868782747865892015-02-24T10:52:42.824-05:002015-02-24T10:52:42.824-05:00Create an index of empty cells and remove items fr...Create an index of empty cells and remove items from that as necessary.Samson Corwellhttps://www.blogger.com/profile/10148822362930969284noreply@blogger.comtag:blogger.com,1999:blog-7225373.post-6033048278968406942015-02-24T10:31:38.529-05:002015-02-24T10:31:38.529-05:00The shuffled list of coordinates is a good solutio...The shuffled list of coordinates is a good solution if you don't need to move the agents around and it fits in memory.<br /><br />If you do need to move agents around efficiently and/or you want to get fancy for fun, you could use a data structure called a "quadtree". Recursively decompose the 2D space into four squares. For each square (at each level of decomposition) store how much room there is remaining in its enclosed space.<br /><br />When you need to find a place to put an agent, start at the top and randomly choose one of the 1-4 squares with room remaining, then recurse until you get to a final cell with room. When you add the agent, recurse back up to decrement the remaining room at each level. Both operations are O(log n).Matthttps://www.blogger.com/profile/02470489293820651609noreply@blogger.comtag:blogger.com,1999:blog-7225373.post-85045557121223472862015-02-24T03:35:11.750-05:002015-02-24T03:35:11.750-05:00Why not shuffle the list (O(n)) at the start and t...Why not shuffle the list (O(n)) at the start and then pick the first element?Per Johanssonhttps://www.blogger.com/profile/04708395220131816350noreply@blogger.comtag:blogger.com,1999:blog-7225373.post-62533330328678502362015-02-24T00:47:05.118-05:002015-02-24T00:47:05.118-05:00One idea: if you want to place k agents, take the ...One idea: if you want to place k agents, take the first k pairs in the output of numpy.random.permutation([(x,y) for x in range(X) for y in range(Y)]).shonkhttps://www.blogger.com/profile/17369367271546487712noreply@blogger.comtag:blogger.com,1999:blog-7225373.post-23956549471754544282015-02-24T00:10:26.238-05:002015-02-24T00:10:26.238-05:00Yes, but that O(n^2) is much better than an unboun...Yes, but that O(n^2) is much better than an unbounded run-time! And it is only done once, as agents are setup.gcallahhttps://www.blogger.com/profile/10065877215969589482noreply@blogger.comtag:blogger.com,1999:blog-7225373.post-8209657771444747032015-02-23T23:58:44.740-05:002015-02-23T23:58:44.740-05:00Looks like what you want is a 'shuffle algorit...Looks like what you want is a 'shuffle algorithm' such as <a href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle" rel="nofollow">Fisher–Yates shuffle</a> - then you take a list of your co-ordinates, shuffle them, and pick the first n.Crosbiehttps://www.blogger.com/profile/02005295490663931940noreply@blogger.comtag:blogger.com,1999:blog-7225373.post-52787299421264342082015-02-23T23:53:07.577-05:002015-02-23T23:53:07.577-05:00Sorry, my last comment was a bit glib as I did not...Sorry, my last comment was a bit glib as I did not consider the cost of the data structure. Finding and removing the nth element from either an array or linked list will require O(n) time, resulting in an undesirable overall O(n^2) run-time. More detail required, but I am going back to bed.Crosbiehttps://www.blogger.com/profile/02005295490663931940noreply@blogger.comtag:blogger.com,1999:blog-7225373.post-72278794420034151612015-02-23T23:49:49.604-05:002015-02-23T23:49:49.604-05:00Sorry, made that too complicated. Just make a lis...Sorry, made that too complicated. Just make a list, and use the indexes of the list. Remove entries from the list as you use them up. You don't need to get as complex as a dictionary or database...Scotthttps://www.blogger.com/profile/12915297057336831151noreply@blogger.comtag:blogger.com,1999:blog-7225373.post-62895221309127002912015-02-23T23:47:20.837-05:002015-02-23T23:47:20.837-05:00You can create a list of all possible x,y co-ordin...You can create a list of all possible x,y co-ordinate pairs, then randomly pick pairs from the list, removing them as you do so. Then to select n pairs will need exactly n attempts, and you are guaranteed no duplicates.Crosbiehttps://www.blogger.com/profile/02005295490663931940noreply@blogger.comtag:blogger.com,1999:blog-7225373.post-8246100130840094032015-02-23T23:46:49.692-05:002015-02-23T23:46:49.692-05:00Not a computer guy, but random thought --
1) make...Not a computer guy, but random thought --<br /><br />1) make your x,y cells into a dictionary or database or something (key-value pairs); keys = 1 to x*y<br />2) as you randomly pick out of the dictionary, remove them from the dictionary. (by choosing between 1 and (X*y - times you've been through the loop))<br /><br />Or something like that...Scotthttps://www.blogger.com/profile/12915297057336831151noreply@blogger.com