Imagine, you have a list of N variables, some of which are marked empty. You need to randomly select an empty one and return it’s number so that code elsewhere may use it as a slot to put in a non-empty one.

**The obvious approach**: Make a list of the numbers of the empty ones, randomly select one of these.

Well, it doesn’t work, cause there may be hundreds of them and we’re operating close to memory limits as it is, and a list of 100 integers will chew up 1521 bytes of memory. *(…yes, it’s already in Mono, without Mono it wouldn’t be feasible at all.)*

**The less obvious approach**: Keep selecting a random one until you bump into an empty one.

Doesn’t work either, because recursively selecting it takes even more memory, and if you do a while loop instead, with LSL random number generator being what it is, it might stall forever and you’ll never know.

**The dirty hack approach**: Behold and stare what these bloody people made me do.

```
integer findspot() {
string empties = "";
integer i;
for (i=0;i<llGetListLength(items);++i) {
if (llList2Key(items,i) == BLANK) {
empties += llGetSubString("00"+(string)i,-3,-1);
}
}
integer index = randInt(llStringLength(empties)/3);
return (integer)llGetSubString(empties,index*3,(index+1)*3-1);
}
```

That only needs 338 bytes of memory to find an empty spot among 100 items, and actually works. 🙂

haha lovely!

I just find your blog today. Is very good. I always wondered about the copy thingy so I was pleased to read here all about it. So thanks for that =)

I was looking at this problem here and I not really up with lsl coding to fully understand how your code works. But I think you wanting to work with a permutation set ya ???

I do a lab last year about this kinda thing and end up using a feistal network to try solve this problem. I not sure if will be useful for you but is quite efficient because you can just start with an empty list and add to it as you go and just use the list index to get ‘encode’ a randomish unique value within the set to pair with the index. And can reverse ‘decode’ the value to return the index of the list item if you want.

Is in BASIC though =) and I dont know if can be coded in LSL or if it will be at all useful to you. Anyways I copy here just in case. Hope the indenting works)

[php]

‘ a simple arithmetic feistal network

‘ to make reversible sets of permutations

‘ – can be any factors of maxitems including 1

‘ – lofactor can be greater than hifactor

‘ – fudge is in the range 0<maxitems

‘ – fudge can come from any source

‘ – rounds can be anything. more = slower

‘ – decoding requires same values as encoding

global lofactor, hifactor, fudge, rounds

maxitems = 100 ‘ items to permutate

lofactor = 5 ‘ a factor of maxitems

hifactor = 20 ‘ the other factor

fudge = 43 ‘ add some fudge

rounds = 4 ‘ number of mixing rounds

‘ *** begin test ***

for i = 0 to maxitems-1

value = encode (i)

index = decode (value)

print i, value, index

next i

‘ *** end test ***

function encode (index)

lo = index mod lofactor

hi = INT (index / lofactor)

for r = 1 to rounds

m = hi mod lofactor

lo = (lo + m * m + fudge) mod lofactor

m = lo mod hifactor

hi = (hi + m * m + fudge) mod hifactor

next r

encode = hi * lofactor + lo

end function

function decode (value)

lo = value mod lofactor

hi = INT (value / lofactor)

for r = 1 to rounds

m = lo mod hifactor

hi = (hi – m * m – fudge) mod hifactor

if hi < 0 then hi = hi + hifactor

m = hi mod lofactor

lo = (lo – m * m – fudge) mod lofactor

if lo < 0 then lo = lo + lofactor

next r

decode = hi * lofactor + lo

end function

[/php]