C++Talk.NET Forum Index C++Talk.NET
C++ language newsgroups
 
Archives   FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Random Shuffle for List
Goto page 1, 2  Next
 
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated)
View previous topic :: View next topic  
Author Message
Lawrence Lim
Guest
PostPosted: Sat Jun 28, 2003 11:07 pm    Post subject: Random Shuffle for List Reply with quote


Does anyone here know a random_shuffle implementation for std::list? The
standard random_shuffle does not work on bidirectional iterators.


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Back to top
Jeff Greif
Guest
PostPosted: Sun Jun 29, 2003 11:32 am    Post subject: Re: Random Shuffle for List Reply with quote


copy to vector, shuffle, copy back.

Jeff
"Lawrence Lim" <thadeus (AT) shaw (DOT) ca> wrote

Quote:
Does anyone here know a random_shuffle implementation for std::list? The
standard random_shuffle does not work on bidirectional iterators.


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
nick@byu.edu
Guest
PostPosted: Sun Jun 29, 2003 11:35 am    Post subject: Re: Random Shuffle for List Reply with quote


Lawrence Lim wrote:

Quote:
Does anyone here know a random_shuffle implementation for std::list?
The standard random_shuffle does not work on bidirectional
iterators.

If your lists are small enough, you could use an adapter to provide
random access iterators for it. (But it will be slow)

Better yet, write your own random_shuffle for list<>.
How about:

list<>::iterator begin = l.begin();
list<>::iterator end = l.end();
list<>::iterator p = begin;

for (int i = l.size(); i > 0; --i) {
for (int r = random(e); r > 0; --r) {
if (++p == end)
p = begin;
}
swap<>(*begin, *p);
}

That still has to walk it a bunch, but not nearly as much as a
random-access to bidi. iterator adapter would. Surely someone else
can improve it?


Nick


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
nick@byu.edu
Guest
PostPosted: Sun Jun 29, 2003 11:37 am    Post subject: Re: Random Shuffle for List Reply with quote
In my previous post, I take back that my implementation is any faster
than an adapter. They're both O(n^2) afaict.


Nick


[ 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
PostPosted: Sun Jun 29, 2003 12:33 pm    Post subject: Re: Random Shuffle for List Reply with quote
In message <Gh7La.309503$ro6.7548585 (AT) news2 (DOT) calgary.shaw.ca>, Lawrence
Lim <thadeus (AT) shaw (DOT) ca> writes
Quote:
Does anyone here know a random_shuffle implementation for std::list? The
standard random_shuffle does not work on bidirectional iterators.

I suspect that even if one was written it would be no more efficient
than creating a vector (possibly of pointers) from your list, calling
random_shuffle on that then using the result to build a list.

--
ACCU Spring Conference 2003 April 2-5
The Conference you should not have missed
ACCU Spring Conference 2004 Late April
Francis Glassborow ACCU


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Andy Sawyer
Guest
PostPosted: Sun Jun 29, 2003 2:03 pm    Post subject: Re: Random Shuffle for List Reply with quote
In article <Gh7La.309503$ro6.7548585 (AT) news2 (DOT) calgary.shaw.ca>,
on 28 Jun 2003 19:07:54 -0400,
Lawrence Lim <thadeus (AT) shaw (DOT) ca> wrote:

Quote:
Does anyone here know a random_shuffle implementation for std::list?
The
standard random_shuffle does not work on bidirectional iterators.

You could try:

template<typename T>
void shuffle_list( std::list<T>& mylist )
{
std::vector<T> v( mylist.begin(), mylist.end() );
std::random_shuffle( v.begin(), v.end() );
mylist.assign( v.begin(), v.end() );
}


Or you might prefer:

template<typename BidirectionalIterator>
void random_shuffle_bidit( BidirectionalIterator begin,
BidirectionalIterator end )
{
typedef typename
std::iterator_traits<BidirectionalIterator>::value_type
value_type;
std::vector<value_type> v( begin, end );
std::random_shuffle( v.begin(), v.end() );
std::copy( v.begin(), v.end(), begin );
}

Regards,
Andy S
--
"Light thinks it travels faster than anything but it is wrong. No matter
how fast light travels it finds the darkness has always got there
first,
and is waiting for it." -- Terry Pratchett, Reaper Man

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Siemel Naran
Guest
PostPosted: Sun Jun 29, 2003 10:20 pm    Post subject: Re: Random Shuffle for List Reply with quote
"Carl Barron" <cbarron3 (AT) ix (DOT) netcom.com> wrote


Quote:
template <class T,class A
void random_shuffle_list(std::list {
typedef std::list<T,A>::iterator iterator;
std::vector<iterator> index;
for(iterator it = data.begin(),it != data.end();++it)
index.push_back(it); // O(n)
std::random_shuffle(index.begin(),index.end());//O(n)
std:list<T,A> temp;
for(std::vector<iterator>::iterator it =
index.begin();it!=index.end();++it)
{
temp.splice(temp.end(),data,*it);
} // O(n)
data.swap(temp); // O(1);
}

Good. Can you accomplish the same without using temporary storage space
temp? Storage space index is OK.

I'm think of this, but too bad the standard does not have a function
list::swap(iterator,iterator)

Quote:
for(std::vector<iterator>::iterator it =
index.begin();it!=index.end();++it)
{
temp.splice(temp.end(),data,*it);
} // O(n)

==>

assert(index.size()==data.size());
typedef std::vector<iterator>::iterator IndexIter;
IndexIter i = index.begin();
const IndexIter iend = index.end();
typedef std::list<T,A>::iterator Iter;
Iter d = data.begin();
const Iter dend = data.end();
for( ;i!=iend; ++i,++d)
{
data.swap(i,d);
} // O(n)


Can anyone help?

--
+++++++++++
Siemel Naran


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Siemel Naran
Guest
PostPosted: Sun Jun 29, 2003 10:20 pm    Post subject: Re: Random Shuffle for List Reply with quote
"Andy Sawyer" <andys (AT) despammed (DOT) com> wrote in message

Quote:
template<typename T
void shuffle_list( std::list {
std::vector<T> v( mylist.begin(), mylist.end() );
std::random_shuffle( v.begin(), v.end() );
mylist.assign( v.begin(), v.end() );
}

Good if T is small, but what if T is big? The vector of iterators idea
by
Carl Barron seems better for the general case, though it seems to use
too
much storage space.

--
+++++++++++
Siemel Naran


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Carl Barron
Guest
PostPosted: Mon Jun 30, 2003 9:40 am    Post subject: Re: Random Shuffle for List Reply with quote
Siemel Naran <SiemelNaran (AT) KILL (DOT) att.net> wrote:

Quote:
"Andy Sawyer" <andys (AT) despammed (DOT) com> wrote in message

template<typename T
void shuffle_list( std::list {
std::vector<T> v( mylist.begin(), mylist.end() );
std::random_shuffle( v.begin(), v.end() );
mylist.assign( v.begin(), v.end() );
}

Good if T is small, but what if T is big? The vector of iterators idea
by
Carl Barron seems better for the general case, though it seems to use
too
much storage space.

--
+++++++++++
Siemel Naran

Where is the too much space in my algorithm? Note that in my algorithm

data.size()+temp.size() is a constant. Thst and efficiency was why I
chose list::splice() to do the rearranging,

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
nick@byu.edu
Guest
PostPosted: Mon Jun 30, 2003 4:01 pm    Post subject: Re: Random Shuffle for List Reply with quote
Siemel Naran wrote:

Quote:
"Andy Sawyer" <andys (AT) despammed (DOT) com> wrote in message

template<typename T
void shuffle_list( std::list {
std::vector<T> v( mylist.begin(), mylist.end() );
std::random_shuffle( v.begin(), v.end() );
mylist.assign( v.begin(), v.end() );
}

Good if T is small, but what if T is big? The vector of iterators
idea by
Carl Barron seems better for the general case, though it seems to
use too
much storage space.

You can save storage space by using a sliding window of only i
iterators. You then have to do something like n/i passes in
alternating directions. Overlap may make this go back to O(n^2)
however--I'm not sure--anyone know?


Nick


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Dave Harris
Guest
PostPosted: Mon Jun 30, 2003 6:29 pm    Post subject: Re: Random Shuffle for List Reply with quote
[email]thadeus (AT) shaw (DOT) ca[/email] (Lawrence Lim) wrote (abridged):
Quote:
Does anyone here know a random_shuffle implementation for
std::list? The standard random_shuffle does not work on
bidirectional iterators.

The O(N) copy-to-vector approach suggested by other people is
probably best.

I think there may be some O(N log N) algorithms. One idea is to
attach a random number to each item and sort using that item as
key. It still needs an extra N words of storage, but this is
non-contiguous and preallocated as part of the items, which may
be an advantage in some situations.

I think there is an O(N log N) algorithm which doesn't need extra
memory at all. Along the lines of a merge sort using a comparison
function which returns random results:

template <typename List, typename Compare>
void merge_sort( List &data, Compare comp ) {
// Left as an exercise. data.sort( comp ) might do.
}

template <typename T>
class random_compare {
bool operator()( const T &a, const T &b ) {
return (rand() & 0x1000) != 0; // Or whatever.
}
};

template <typename T, typename A>
void random_shuffle_list(std::list<T,A> &data) {
merge_sort( data, random_compare<T>() );
}

However, I haven't proven that this gives all permutations with
equal probability. Nor even tested it. It's something to
investigate if the copy-to-vector approach is too expensive in
memory.

-- Dave Harris, Nottingham, UK

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Dhruv
Guest
PostPosted: Mon Jun 30, 2003 6:34 pm    Post subject: Re: Random Shuffle for List Reply with quote
On Sat, 28 Jun 2003 19:07:54 -0400, Lawrence Lim wrote:

Quote:
Does anyone here know a random_shuffle implementation for std::list? The
standard random_shuffle does not work on bidirectional iterators.


This algorithm is not really RANDOM, but it acomplishes the task to some
extent.


template <class I>
void list_random_shuffle (I _first, I _last)
{
I _front = _first;
I _back = --_last;


while (_front != _back)
{
if (rand() {
std::swap (*_front, *_back);
++_front;
}
else if (rand() {
std::swap (*_back, *_first);
--_back;
}
else
{
std::swap (*_back, *_last);
--_back;
}
}
}



-Dhruv.







[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
nick@byu.edu
Guest
PostPosted: Tue Jul 01, 2003 7:50 am    Post subject: Re: Random Shuffle for List Reply with quote
Dhruv wrote:

Quote:
On Sat, 28 Jun 2003 19:07:54 -0400, Lawrence Lim wrote:

Does anyone here know a random_shuffle implementation for
std::list? The standard random_shuffle does not work on
bidirectional iterators.


This algorithm is not really RANDOM, but it acomplishes the task to
some extent.


template void list_random_shuffle (I _first, I _last)
{
I _front = _first;
I _back = --_last;


while (_front != _back)
{
if (rand() {
std::swap (*_front, *_back);
++_front;
}
else if (rand() {
std::swap (*_back, *_first);
--_back;
}
else
{
std::swap (*_back, *_last);
--_back;
}
}
}

I thought of something just like the above while considering a sliding
window approach. Closer analysis reveals that the above yields
extremely poor distribution--it doesn't even come close at all to
making all permutations reachable.

While it does 'mix it up' a bit, it'd probably be a misnomer to call
it a random shuffle (like you said). I guess my comment then, is
that 'to some extent' is actually "not very much at all".



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Siemel Naran
Guest
PostPosted: Wed Jul 02, 2003 1:04 am    Post subject: Re: Random Shuffle for List Reply with quote
"Carl Barron" <cbarron3 (AT) ix (DOT) netcom.com> wrote

Quote:
Siemel Naran <SiemelNaran (AT) KILL (DOT) att.net> wrote:

Good if T is small, but what if T is big? The vector of iterators idea
by
Carl Barron seems better for the general case, though it seems to use
too
much storage space.

Where is the too much space in my algorithm? Note that in my algorithm
data.size()+temp.size() is a constant. Thst and efficiency was why I
chose list::splice() to do the rearranging,

Yes, you're probably right. In your algorithm, please explain what is going
on with the following lines

temp.splice(temp.end(),data,*it);


template <class T,class A>
void random_shuffle_list(std::list<T,A> &data)
{
typedef std::list<T,A>::iterator iterator;
std::vector<iterator> index;
for(iterator it = data.begin(),it != data.end();++it)
index.push_back(it); // O(n)
std::random_shuffle(index.begin(),index.end());//O(n)
std:list<T,A> temp;
for(std::vector<iterator>::iterator it =
index.begin();it!=index.end();++it)
{
temp.splice(temp.end(),data,*it);
} // O(n)
data.swap(temp); // O(1);
}


--
+++++++++++
Siemel Naran


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Mirolyub Hristov
Guest
PostPosted: Wed Jul 02, 2003 2:37 am    Post subject: Re: Random Shuffle for List Reply with quote
Hello,

"Siemel Naran" <SiemelNaran (AT) KILL (DOT) att.net> wrote

Quote:
Good. Can you accomplish the same without using temporary storage space
temp? Storage space index is OK.

You could remove the temp list by using boost's indirect_iterator_generator:

#include <algorithm>
#include <boost/iterator_adaptors.hpp>

template<typename ForwardIter>
void forward_random_shuffle(ForwardIter first, ForwardIter last)
{
std::vector<ForwardIter> iterators;
for(ForwardIter current = first; current != last; ++current)
iterators.push_back(current);

typedef typename boost::indirect_iterator_generator<
std::vector::type indirect_iterator;
std::random_shuffle(
indirect_iterator(iterators.begin()),
indirect_iterator(iterators.end()));
}

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Display posts from previous:   
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
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


Powered by phpBB © 2001, 2006 phpBB Group
SEO toolkit © 2004-2006 webmedic.