 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Francis Glassborow
Guest
|
 Posted: Wed Aug 27, 2003 3:45 pm Post subject: Re: STL Proposal: partial _random_shuffle() |
 |
|
In article <3F4BAE2C.D33358BD (AT) acm (DOT) org>, Pete Becker <petebecker (AT) acm (DOT) org>
writes
| Quote: | Ross MacGregor wrote:
Shouldn't the STL include a partial_random_shuffle() to complement
partial_sort()?
It would shuffle the first N elements of a container.
std::vector<int> vec;
// populate vec
random_shuffle(vec.begin(), vec.begin() + N);
|
That would be simple but wasn't what the OP wanted which was N elements
selected at random from the whole sequence. Personally, unless the game
industry has started dealing with sequences of many thousands of
elements, I think that a full random_shuffle() should have perfectly
acceptable performance.
--
Francis Glassborow ACCU
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Pete Becker
Guest
|
| Posted: Fri Aug 29, 2003 8:31 am Post subject: Re: STL Proposal: partial _random_shuffle() |
|
|
Francis Glassborow wrote:
| Quote: |
In article <3F4BAE2C.D33358BD (AT) acm (DOT) org>, Pete Becker <petebecker (AT) acm (DOT) org
writes
Ross MacGregor wrote:
Shouldn't the STL include a partial_random_shuffle() to complement
partial_sort()?
It would shuffle the first N elements of a container.
std::vector
// populate vec
random_shuffle(vec.begin(), vec.begin() + N);
That would be simple but wasn't what the OP wanted which was N elements
selected at random from the whole sequence.
|
Read it again. He asked for a function that "would shuffle the first N
elements of a container."
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Francis Glassborow
Guest
|
| Posted: Fri Aug 29, 2003 3:27 pm Post subject: Re: STL Proposal: partial _random_shuffle() |
|
|
In article <3F4E18CB.CB6301FA (AT) acm (DOT) org>, Pete Becker <petebecker (AT) acm (DOT) org>
writes
| Quote: | That would be simple but wasn't what the OP wanted which was N elements
selected at random from the whole sequence.
Read it again. He asked for a function that "would shuffle the first N
elements of a container."
|
Sorry, I was guilty of 'mind reading' because what he wrote is clearly
not a specification of a partial_shuffle so I ignored his example and
focused on what a partial_shuffle could conceivably mean.
--
Francis Glassborow ACCU
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ross MacGregor
Guest
|
| Posted: Sat Aug 30, 2003 1:49 pm Post subject: Re: STL Proposal: partial _random_shuffle() |
|
|
Francis Glassborow wrote:
| Quote: | In article <3F4E18CB.CB6301FA (AT) acm (DOT) org>, Pete Becker
writes
That would be simple but wasn't what the OP wanted which was N elements
selected at random from the whole sequence.
|
Yes you were right. I failed to clearly state that it would select a
subset of random elements from the entire container.
| Quote: | Sorry, I was guilty of 'mind reading' because what he wrote is clearly
not a specification of a partial_shuffle so I ignored his example and
focused on what a partial_shuffle could conceivably mean.
|
I guess this proves my point that it is a complex operation, as I see no
flaws in my algorithm...Actually there is one flaw, if n is equal to the
size of the container shuffle_end must be adjusted to be (shuffle_end - 1).
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Sat Aug 30, 2003 11:32 pm Post subject: Re: STL Proposal: partial _random_shuffle() |
|
|
On 29 Aug 2003 04:31:33 -0400, Pete Becker <petebecker (AT) acm (DOT) org> wrote:
| Quote: | Francis Glassborow wrote:
In article <3F4BAE2C.D33358BD (AT) acm (DOT) org>, Pete Becker <petebecker (AT) acm (DOT) org
writes
Ross MacGregor wrote:
Shouldn't the STL include a partial_random_shuffle() to complement
partial_sort()?
|
Something like partial_sort which extracts the n smallest elements of a
container to the front and sorts them. Subset of whole implied here.
| Quote: | It would shuffle the first N elements of a container.
|
Poor choice of words. Intended to say that it would be a random order
subset of N elements from the container.
Code which produced the desired result was snipped.
| Quote: | std::vector
// populate vec
random_shuffle(vec.begin(), vec.begin() + N);
|
Matches the one misstatement of the three.
| Quote: | That would be simple but wasn't what the OP wanted which was N elements
selected at random from the whole sequence.
Read it again. He asked for a function that "would shuffle the first N
elements of a container."
|
Read all of it again.
Given [1 2 3 4 5] and N == 2, there are 20 possibilities for the first
two elements from the desired algorithm. The above gives only two.
Random_shuffle(vec.begin(), vec.end()) would give the desired results
with more effort. I can not make a value judgement on whether that
would be efficient enough for the desired applications.
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
