|
I think that you can quickly accomplish this by assigning ordinately the requested numbers to an array and then randomly scrambling the array itself.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
|
|
|
|
|
CPallini wrote: I think that you can quickly accomplish this by assigning ordinately the requested numbers to an array and then randomly scrambling the array itself.
Thanks for your answer... but I'm not sure I get what you mean.
If I assign all numbers to an array, then should it not be some kind of "recursive scrambling", seeing that I need sub-groups also to contain all digits?
|
|
|
|
|
By your definition I guessed the set composed by all the numbers ranging from 0 to 10000 . Maybe my guess was wrong, let me know it.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
|
|
|
|
|
CPallini wrote: By your definition I guessed the set composed by all the numbers ranging from 0 to 10000. Maybe my guess was wrong, let me know it.
Ok, maybe I did not explain it well enough...
Maybe an example will help
I am giving below the first 10 numbers... of course this is only intended as an example, and not the numbers that I actually want.
21890
34775
54684
02397
17208
28116
59012
60271
72543
80849
In the above set of 10, you can see that the last digit occurs exactly once. Similar, the next set of 10 should also contain the digits 0 to 9 in the units position, and so on. The additional requirement being that the first set of 100 numbers should contain all numbers from 00 to 99 in the last two positions. In the above example, 10 of those are already filled in, leaving out the other 90.
I hope I have done a better job of explaining now
Thanks
Chandra
|
|
|
|
|
Now the task is clear; unfortunately I have no good idea (in fact no idea at all) about
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
|
|
|
|
|
CPallini wrote: Now the task is clear; unfortunately I have no good idea (in fact no idea at all) about
That's ok... thanks for your time.
|
|
|
|
|
I think Pallini actually has your answer. Think of it on a smaller scale at first...
With the numbers you gave, you just satisfied the first condition (Set of 10, ending in each digit from 0 to 9). Of course, just the numbers 0 to 9 would satisfy that condition.
Now move to the 100s... You basically need 100 numbers that end in 00-99, and 00, 01, 02, ... 98, 99 satisfies that condition. Move to the thousands, and the ten thousands, and there you are.
So technically, a set of 00000-99999 in order satisfies every condition except the randomness. If you want bigger numbers, you can just prepend a few random digits to each, the same way you use "21890" instead of just "0" in your example. Since the last N digits are unique, the number as a whole is unique.
So if I'm right so far, I have your answer.
Create an array of numbers from 0 to 99999 (Maximum - 1) such that Array[N] = N. Just to start off.
Start by randomly sorting each block of 10. First randomize elements 0-9, them 10-19, and so on.
Then sort the blocks themselves. Treat 0-9 as a cohesive unit, 10-19 as a unit, and so on. Sort each block of 100 as if it was comprised of ten blocks.
As you can probably see by now, you just move up one power of ten at a time. Next you sort each block of 1000, treating it as 10 blocks of 100 each, then the whole array as 10 blocks of 1000 each.
You could even do this backwards, first sorting the big blocks, then the little blocks.
At this point, the entire array is randomized, yet will still satisfy your conditions.
This will of course take quite a while if you use a larger set, but there are ways around that too. Use a tree instead. Build a tree where each node has ten children (Except the leaf nodes). These children start out as "0", "1", ..., "8", "9". Traverse the whole tree, level by level, and shuffle the children of each node. Then just traverse the tree to grab all of the shuffled numbers in order, and pipe them into an array. Someone elsewhere in the thread showed you how to quickly search for them.
Ok, this post is way longer than I intended, and I was going to leave the office over a half hour ago, so good luck
|
|
|
|
|
Hi
I think the tree is a really good idea...
As I said before, I have already written the bruteforce method that CPallini was talking about earlier.
I will try out the tree algorithm as it seems a more elegant solution to my problem.
Thank you for taking the time to look through this
Regards
Chandra
|
|
|
|
|
There is a brute force way to arrange these, but it is easier to describe a randomiser:
1. Start with the set of 10,000 numbers in order.
2. Generate a set of swap commands, swap the ith element with one n places away, i in [0,10000) n in [1,10000) with circular referencing. If the swap is within 10 places it always happens, if 10 - 99 places then it swaps with the nearest element in the range 10 - 99 with the same LSB, if 100 - 999 then to the nearest element with the same 2 LSB etc...
continue random swaps until the set is randomised.
To arrange by brute force:
1. generate 10000 random LSB so that each group of 10 contains {0,..,9}
2. for each group of 100 LSB's generate a random group of 100 next LSB's (i.e. 10 '0's, 10'1's etc) call these {Ai}. Assign these Ai as follows - Assign Ao to the first number. Then assign Ai with the lowest i such that the number formed by the two LSBs is not already in this group.
3. Do the same for the next LSB assigning 1000 numbers etc ..
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
cp9876 wrote: There is a brute force way to arrange these, but it is easier to describe a randomiser:
1. Start with the set of 10,000 numbers in order.
2. Generate a set of swap commands, swap the ith element with one n places away, i in [0,10000) n in [1,10000) with circular referencing. If the swap is within 10 places it always happens, if 10 - 99 places then it swaps with the nearest element in the range 10 - 99 with the same LSB, if 100 - 999 then to the nearest element with the same 2 LSB etc...
continue random swaps until the set is randomised.
To arrange by brute force:
1. generate 10000 random LSB so that each group of 10 contains {0,..,9}
2. for each group of 100 LSB's generate a random group of 100 next LSB's (i.e. 10 '0's, 10'1's etc) call these {Ai}. Assign these Ai as follows - Assign Ao to the first number. Then assign Ai with the lowest i such that the number formed by the two LSBs is not already in this group.
3. Do the same for the next LSB assigning 1000 numbers etc ..
Thank you... I shall try and post back... I am already doing the brute force method, but the first one seems quite interesting.
Meanwhile, is it possible, given a number, to say exactly where in the list it is? Speed is of essence - I will need to give out the answers within a 20 second framework, considering that I will have close to 2 million numbers that will form the base list. I cannot use any database engine...
The reason in my original post to ask for any algorithm for the generation was to see if I could utilize the reverse of that to find the position of numbers too...
|
|
|
|
|
ChandraRam wrote: considering that I will have close to 2 million numbers that will form the base list. I cannot use any database engine
If you need 2 million numbers such that each number only occurs once, then it may be best to precompute as any calculation process has state information that includes all previous numbers (of the 2 million) that have been issued. Unless you can come up with an algorithm that uses less state information, you may need to store up to 2 million numbers - so precomputation may be attractive.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
The speed of the generation is not so much an issue (as in hours, is also OK) as the ability to instantly retrieve any number's position in the list...
|
|
|
|
|
Unless you have RAM issues, generate two arrays each of 2 million integers:
a[i] being the randomised numbers
b[j] such that b[a[i]] = i
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
cp9876 wrote: Unless you have RAM issues, generate two arrays each of 2 million integers:
a[i] being the randomised numbers
b[j] such that b[a[i]] = i
Great!... Now, why didn't I think of that? :->
Language suggestions to hold 2.6 million array items?
|
|
|
|
|
What is the application for this? It's not going to come out very random with these constraints
I'd do something like this:
Its not going to win any awards for neatness, but I think it uses fairly minimal memory. Also its generating the numbers on the fly, rather than using a pre-sorted array, which is kindof cheating
IEnumerable< int > ChandrasCrazyNumbers()
{
use the hash-backed index to do removes. The bool is always true - its
a placeholder.
when its more generalised it gets harder to follow.
Dictionary< string, bool> ones =
Dictionary< string, Dictionary< string, bool>> tens =
Dictionary< string, List< string >> hundreds =
Dictionary< string, List< string >> thousands =
while(true)
{
initialise thousands like so: iterate 0-9999, for say 5983, file that under
"983", {... {"5983", true} .... }
while(thousands.Count > 0)
{
initialise hundreds like so: iterate 0-999, for say 583, file that under
"83", {... {"583", true} .... }
while(hundreds.Count >0)
{
initialise tens like so: iterate 0-99, for say 58, file that under
"8", {... {"58", true} .... }
while(tens.Count > 0)
{
init ones like so: {"0", "1"... "9"} all true;
while(ones.Count > 0)
{
string randomOne = ones.Keys[random between 0 and ones.Count)];
ones.Remove[randomOne];
string randomTen = tens[randomOne].Keys[random between 0 and tens.Count)];
tens.Remove[randomTen];
yield return int.Parse(string.Concat(...., randomTen, randomOne));
}
}
}}}}}
|
|
|
|
|
Hi Mark
Thank you for looking through this...
This is for a lottery number generator application, which is not actually _random_ in the true sense; there has to be a method in the madness My client is actually guaranteeing that each block of 10 will fetch 1 prize, each block of 100 - 10 prizes, and so on...
I don't quite get the logic, though - my requirement is to generate 26 million numbers, distributed as described above. I am always looking for different ways to implement this.
I would welcome any explanation that you can give on your logic.
Thank you in advance
Chandra
|
|
|
|
|
Dear everyone,
I am facing a problem about my AI assignment. It is to implement Expectation Maximization(EM) for learning a simple naive Bayes model. Who has programming experience about using this algorithm? I don't know where to begin? Thanks if you will give me some help.
|
|
|
|
|
There are several articles on artificial intelligence and neural networks here on CodeProject.
I suggest you use the search facilities on the top of most CP pages. That's where I
would begin.
Luc Pattyn [Forum Guidelines] [My Articles]
this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
yanhe0116 wrote: I don't know where to begin
I googled and came up with thesis, descriptions, hybrid improvements and even java code for a basic example. If it were me, I would start there.
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
I am trying to write some graphics code using the web-development tool Adobe ActionScript (version 3). AS3 has many sophisticated graphics capabilities, but what it does not have apparently, is any sort of BitBlt capability with raster operation (ROP) codes. This may have something to do with it being based on 'Sprites' which from my brief persual of some wikipedia info, is a different philosophy altogether from BitBlt.
I was trying to emulate BitBlt from scratch in ActionScript, by merely dumping three bitmaps into arrays, and then going through them pixel by pixel doing the logical ops on each pixel. As could probably be expected, this is way too slow. It was taking a full second to do ROP bitmap combinations that BitBlt would do instantaneously. (This has nothing to do with any inherent limitation in Actionscript, which does plenty of things graphical instantaneously.)
So I need to find out the algorithms that BitBlt is employing to do what it does and if its possible for me to emulate that (assuming that BitBlt isn't relying primarily on graphics hardware that can't be accessed from a web application.)
Important point:
There is only one ROP code I need to use, so possibly it could be optimized on that basis. (Its one of the more complex ROP codes involving XOR and AND of three different bitmaps).
-- modified at 14:44 Thursday 15th November, 2007
|
|
|
|
|
Hi, image operations in professional packages are implemented using highly optimized code,
typically a combination of C and assembly code; where possible SIMD techniques are applied
(that's MMX/SSE on Intel Pentium). It is the result of extensive research, so you won't
match its performance easily.
Luc Pattyn [Forum Guidelines] [My Articles]
this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
"Hi, image operations in professional packages are implemented using highly optimized code, typically a combination of C and assembly code; where possible SIMD techniques are applied (that's MMX/SSE on Intel Pentium). It is the result of extensive research, so you won'tmatch its performance easily."
If it were documented anywhere, of course I would be able to emulate it (w/ exception of hardware capabilities). There's no apparent performance hit merely from using ActionScript either, which does some things much faster (e.g. antialiasing) than can be done with Windows code, although I have no idea how its done.
|
|
|
|
|
Windows apps can call on the built-in BitBlt functions[^].
Google (BilBlt, rasterop, theory, internals, ...) will lead you to some junk and some
code snippets; there must be some C/C++/Java implementations around. But again, performance
wise none of those will match specialized products.
Luc Pattyn [Forum Guidelines] [My Articles]
this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Luc Pattyn wrote: Windows apps can call on the built-in BitBlt functions[^].
The Windows BitBlt was the one I was referring to, and I am familiar with the documented interface for it.
Luc Pattyn wrote: Google (BilBlt, rasterop, theory, internals, ...) will lead you to some junk and some
code snippets; there must be some C/C++/Java implementations around. But again, performance
wise none of those will match specialized products
You could save yourself some typing by just responding to every post with "Google it". (Incidentally why does this forum even exist when a link to google is all that's needed.)
There are several people in this forum with "Microsoft MVP" in their signature. Don't know if that's literal or some code unique to this forum, but maybe I was thinking someone like that might run across this thread.
As far as my problem, I have three bitmaps - two of them never change position in relation to the client area, and the third scrolls up and down. With each scroll the BitBlt w/ ROP code has to be done. I'm thinking now since the first two bitmaps don't move, I can precalclulate values for them and store them in another table maybe 10-15 megs in size. So, part of the ROP calculation could be replaced by an indexed table look-up, though given the ROP code, I don't know how to do this yet, and furthermore don't know if there's any time saving with this method.
|
|
|
|
|
Most of the people active on this forum use Windows; when they would need BitBlt, they
would call the function, without worrying too much how it is implemented (that was
Microsoft's job).
If you want to implement your own BitBlt function, you will run into performance issues;
the general lines to maximize performance on pixel operations are: avoid testing
and branching, avoid function calls, avoid unnecessary moves, and try to handle as
many pixels as possible in a single operation. The details of all this are way beyond the
scope of a forum such as this, as I already indicated.
With the partial description you provided, I would judge your table look-up is unlikely
to provide any speed-up unless it replaces two of the three images, which probably it isn't.
A Pentium-class CPU is better at reading a couple of pixel streams (which is a very
predictable process, and a prefetch can be organized), than at looking up tables;
and it is unlikely the table replaces more than a couple of (fast) instructions anyway.
Luc Pattyn [Forum Guidelines] [My Articles]
this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|