Advanced RANDOM functions/techniques

'lo all! Got a couple specific scenarios I need to plan for. I have already built fully working code in both of these cases, but fully expect I did NOT go about it the right way! Here are the scenarios:

1. I have a series of items/objects and I need to select *some* of them at random. So a simple, real world example would be I have the numbers 1 to 100, and I need to randomly select 13 of those numbers. Right now the way I'm doing this is by choosing a normal random number between 1 and 100 and then seeing if it's a random number that has already been picked - if so, I re-randomly select a number and start the check again, and so on. The problem is this could theoretically cause an infinite loop, and I further suspect it's bad programming etiquette to build it this way.

2. This is a somewhat similar scenario, just with screen coordinates this time. I need to generate N number of random boxes on the screen (random sizes, colors, locations, etc.), but need to be sure none of them overlap. Once again, the way I'm doing this now is to create one box and then test for collision against every other box already built - if overlap then re-randomly generate the box. Again, this could theoretically cause an infinite loop and I'm sure it's a bad approach to solving this problem.

Thusly, I open the table to suggestions! Thanks all, Jason

Mersenne Twister? I believe there's a BlitzMAX version in the code archives somewhere.

1. Alternatively, have an array with all numbers in it. Select a random position. Swap that with the last element. Slice the Array to be one smaller. Rinse / Repeat for as many numbers as you need. This has a worst case time complexity O(n).

2. One approach would be to make the boxes in serial progression. Start in one corner, and then work your way across, then down the screen, using semi random offsets. It kinda depends on exactly what you're looking for (i.e. should the boxes cover the entire screen, or have arbitrary spaces between them, and how should they be distributed).

I like your solution to #1, and actually thought about something like this after my original post - was remembering how I did my shuffle cards function years ago, and that the same logic could apply here (shuffle deck of cards, then select the first 3 - same effect that I'm looking for now).

With #2, I basically don't want any restrictions - boxes COULD be all in one corner of the screen, COULD be in logical "rows", or COULD be spaced evenly around the screen - just that they cannot overlap... I was toying around with the idea that after each box is added to the screen, the pixels it covers are no longer "available" (thusly I would have needed to previously create a array of available pixels) - then when I go to create a new box I simply check to see if it intends on consuming any unavailable pixels. If so, re-randomize. This prevents the need to enumerate the checks amongst all previously created objects, but still could end in an infinite loop - I guess to tackle this I could simply count the number of attempts - if over 100 then break and consider the fact that we cannot create any further boxes... seems like a viable compromise...

In the first one I'd just Rand() numbers and check if they're picked. Faster than creating arrays I think (you could check, of course).

In the second one you shouldn't just start drawing and test for collision. Depending on your size limits some of the boxes could fill the whole screen before all boxes are created - an infinite loop. If it's possible to have a screen sized box, this isn't even that unlikely.

One solution is to have a list or array of empty spaces. Randomly select one of them to generate the box to. Then divide the space to 5 areas: 4 new empty areas and the box. Store the empty areas to the space list and the box to another list.

Something like this:
123
1b3
143