Another unique random numbers question

Got a LiveCode personal license? Are you a beginner, hobbyist or educator that's new to LiveCode? This forum is the place to go for help getting started. Welcome!

Moderators: FourthWorld, heatherlaine, Klaus, kevinmiller

Post Reply
Sjatplat
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 75
Joined: Wed Jun 22, 2011 1:53 pm

Another unique random numbers question

Post by Sjatplat » Mon Apr 14, 2014 9:53 pm

Salute,
I guess you veterans are fed up with these random number questions but I have challenge that I could not solve browsing this forum.

I´m making a program where the user writes text and put in references. These references looks like this: {k1}
So the user can type e.g. I have {k1} apples but I really want {k1} coconuts.

this particular reference ({k1}) points to a number-range the user has created. Let´s say 1 as minimum and 10 as maximum and the program picks a random number within that range and replaces the reference.
So far so good....but since the user has the ability to put in a huge range e.g. min:-5000 max:100000 and also the ability to demand a unique number each time the program finds the reference - my challenge is to find a way to create unique numbers both in a small range and a huge range.

I could use the shuffle-method: create a list of all possible numbers and shuffle them but this will take too much time with a huge range.
I could use a repeat loop that creates a list of random numbers and only add to the list if the random number is unique - but this could potentially lock the computer with a small range.

The only factor I have now that could reduce the amount of work for the cpu is that the amount of references {k1} in the text will probably be limited.

Anyone know a smart method to pick unique random numbers both from a small range and a huge range of integers?

Sjat

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 10333
Joined: Wed May 06, 2009 2:28 pm

Re: Another unique random numbers question

Post by dunbarx » Mon Apr 14, 2014 10:45 pm

Hi.

Not sure I understand your problem, because you seem to understand the "random()" function. Is it that once you pick a number, you never want that number to be available again?

If so, you can see that you cannot simple invoke random() more than once. What I would do is set up a custom property with the range the user selects, (pseudocode):

Code: Select all

get the lower and upper limits --lower and upper
repeat with y = lower to upper
put y & return after temp
end repeat
set the range of this card to temp
Now you have a return delimited list of all those numbers. If that range is quite large, you may want to rewrite the loop. But anyway, then you can:

Code: Select all

get any line of the range of this card
delete line it of the range of this card
answer it
You now have a random sample from that list, and that list no longer contains that sample.

Craig Newman

Sjatplat
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 75
Joined: Wed Jun 22, 2011 1:53 pm

Re: Another unique random numbers question

Post by Sjatplat » Mon Apr 14, 2014 11:18 pm

Hi,
you never want that number to be available again?
Yes - correct -the user can choose if he wants the output to be unique every time

Custom property list: I´ve tried this but it seems to go slow with a high number and I have to be prepared for the user to go bananas with the numbers. I could put a range limit but I´m not yet sure if this is any good for the user.

Code: Select all

on mouseUp
   put the milliseconds into tMS
   repeat with x=1 to 1000000
      put x & return after temp
   end repeat
   set the range of me to temp
   put "finished in: " & the milliseconds-tMS & " milliseconds."
end mouseUp
This takes a about 1200 milliseconds on my computer. If the user had used a larger range - let´s say: -1000000 to 1000000 then it bumps up to on 3200 millisecs.

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 10333
Joined: Wed May 06, 2009 2:28 pm

Re: Another unique random numbers question

Post by dunbarx » Tue Apr 15, 2014 12:10 am

Howdy.

Think about what you just timed. The repeat loop, no? The form "repeat with" is not slow, but does require the engine to do a bit of bookkeeping with each iteration. Anyway, this begs the question of the speed of accessing data in a custom property. You will find no issue with that. Try this with your 2,000,000 line custom property. You will have to modify the names, of course:

Code: Select all

on mouseup
   get the yourPropName of this cd
  put any line of it into testLine
  delete line testLine of it
  set the yourPropName of this cd to it
   answer testline
end mouseup
What, about a millisecond or two?

Craig

magice
Posts: 457
Joined: Wed Mar 18, 2009 12:57 am

Re: Another unique random numbers question

Post by magice » Tue Apr 15, 2014 2:52 am

Excuse me for interrupting, but I often see these kind of questions as an opportunity to test my own ability and learn something new. Would something like this be faster?

Code: Select all

on mouseUp
   put randNumGen(1000, 2000) 
end mouseUp

function randNumGen tX tY
   put the cNumbers of this stack into tNumbers
   put false into tCheck
   put tY-tX into tRange
   repeat until tCheck is true
      put random(tRange) + tX into tResult
      if tResult is not in tNumbers
      then
         put true into tCheck
         put comma & tResult after tNumbers
         set the cNumbers of this stack to tNumbers
         return tResult
      end if
   end repeat
end randNumGen

Sjatplat
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 75
Joined: Wed Jun 22, 2011 1:53 pm

Re: Another unique random numbers question

Post by Sjatplat » Tue Apr 15, 2014 8:40 am

Craig, (and magice)
The method of getting the random values from a custom property is absolutely fast. but that´s not the problem. It´s creating the list of numbers that takes time as I showed in my example code. I have to take into account that the user could create even much higher numbers.

Magice,
That is also fine and I suggested this in my first post, but as I wrote:
I could use a repeat loop that creates a list of random numbers and only add to the list if the random number is unique - but this could potentially lock the computer with a small range.
Sjat

magice
Posts: 457
Joined: Wed Mar 18, 2009 12:57 am

Re: Another unique random numbers question

Post by magice » Tue Apr 15, 2014 9:34 am

I woke up in the middle of the night and realized that my solution doesn't take into consideration the possibility of running out of numbers and creating non-terminating loop. Maybe you could throw in an evaluation of the number of commas in tNumbers compaired to tRange. I need to go back to sleep or I would test that.

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 10333
Joined: Wed May 06, 2009 2:28 pm

Re: Another unique random numbers question

Post by dunbarx » Tue Apr 15, 2014 2:21 pm

Ah. I see what you are getting at now. If it is to be allowed that the user can select a range of values into the multi-millions or beyond, then to generate that list natively in LC is going to take some time. So how do we get around this?

1- Limit those greedy users to reasonable values, say a 100,000 swing. This will run fairly quickly. The noticeable time lag will start a bit beyond there, and at a million, you do have to wait a few seconds.

Now then...

2- Is it feasible in your application to prepare a comprehensive list beforehand, when nobody is looking, that might cover a very broad range like -10,000,000 to + 10,000,000? This would take a little while, but you need only do it once. You could store that long list in a custom property, and then pick from it. You never change that list. (PseudoCode):

Code: Select all

ask for lower value
ask for upper value
put line lowerValue to upperValue of the longList of this stack into yourWorkingVariable
If you want to put, say line 2000 to 2,000,000 of that list into a variable, the action would take only a tick or two. This is not cheating.

Craig
Last edited by dunbarx on Wed Apr 16, 2014 4:35 am, edited 1 time in total.

Sjatplat
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 75
Joined: Wed Jun 22, 2011 1:53 pm

Re: Another unique random numbers question

Post by Sjatplat » Tue Apr 15, 2014 3:12 pm

Thanks a lot, Craig

This what I have arrived at. A limit. Either a low enough limit so the number can be created on the fly (like max 1,000,000) or as your suggestion nr. 2. - a premade list with a higher range.

both solutions needs a kind of upper limit and right now it seems to be the right choice. (I can´t think of any reason the user would want higher number, but you never know when you´re creating an editor/creative program and want to make sure it´s flexible enough for those "Greedy" users :D )

But I thought of something else. How about this:
If the number range is larger than e.g. 1,000,000 then maybe the program can use the "only add to list if it´s unique" repeat loop"
With such a high number the possibility of picking a duplicate random number is Very small...

So to summarize:
if number-range is less than 1,000,000 - then create a complete list of all possible numbers and pick a unique random list from this list (the custom property method)
if number-range is greater than 1,000,000 - then write a repeat while loop - until a unique list is created....

what do you think....is this risky? (I´m a little scared of those repeat while loops :) )

magice
Posts: 457
Joined: Wed Mar 18, 2009 12:57 am

Re: Another unique random numbers question

Post by magice » Tue Apr 15, 2014 3:54 pm

I adjusted my earlier code to prevent the non-terminating loop. I also made adjustments that allowed the range of numbers to be inclusive. This is what I came up with.

Code: Select all

on mouseUp
   put randNumGen(1000, 2000)
end mouseUp

function randNumGen tX tY
   put the cNumbers of this stack into tNumbers
   put false into tCheck
   put tY-tX+1 into tRange
   if tRange > the number of words in tNumbers - 1
   then
   repeat until tCheck is true
      put random(tRange) + tX-1 into tResult
      if tResult is not in tNumbers
      then
         put true into tCheck
         put comma & space & tResult after tNumbers
         set the cNumbers of this stack to tNumbers
         return tResult
      end if
   end repeat
else
   answer "You have used all of the available numbers"
   return 0
   end if
end randNumGen
Where I think you will gain an advantage, is when the range of numbers is large and early on while most numbers are still available. It will however steadily get slower as more numbers are added to used list.

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 10333
Joined: Wed May 06, 2009 2:28 pm

Re: Another unique random numbers question

Post by dunbarx » Tue Apr 15, 2014 3:57 pm

I like the prepared list more and more. Once the list is generated, you are done. This can be used in all the ways we discussed earlier; you can delete any line instantly, you can find out if a number is among the lines of that list instantly, etc.

I once made an app, that still runs a part of my business, in Hypercard, and in a spate of pure indolence, I allowed the user to assign a randomly generated eight digit number to a list of existing numbers, hoping no duplicates would be generated over the few thousand that we still use today. So far, no dups. But you are the first person I have ever admitted to doing that.

So delete from the list when you choose a number. Be a mensch.

Craig

[-hh]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm

Re: Another unique random numbers question

Post by [-hh] » Tue Apr 15, 2014 4:56 pm

..........
Last edited by [-hh] on Wed Aug 13, 2014 1:13 pm, edited 2 times in total.
shiftLock happens

Sjatplat
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 75
Joined: Wed Jun 22, 2011 1:53 pm

Re: Another unique random numbers question

Post by Sjatplat » Tue Apr 15, 2014 5:44 pm

Magice,
Thank you so much for that code. I have checked every line of it to make sure I understand what´s happening.

And thank you, both Craig and [-hh] for the explanations - I now have a solution I´m happy with and have learned more about the "lottery".

Since my program know how many unique numbers the user will ask for (and that number will never be too great) this is just the solution I´m looking for.
I don´t need a limit now (well just the universe limit - but if the sky is the limit then people should not complain :) ).

Thank you all, great learning!

Post Reply