Require code to shuffle a list

[raydona]

Hi,
I created a general list, having as a data member a pointer to the first node, and then linking all other nodes to the first node. My simulation program requires the list to be shuffled. I wonder if anyone can suggest (or even provide the code) how I might rearrange the contents of the list in a random fashion?
I would be extremely grateful for all help.

 

[cpjust]

If you use an STL container like a list or vector you can use the random_shuffle() function.

If you look at the <algorithm> header file at the random_shuffle() function, you might get some ideas that could help. Then again, it's pretty hard even for me to read, and probably relies mostly on iterators.

 

[uolj]

The technique in random_shuffle only works when the container allows random access iterators. Basically, the std::list and your own hand made linked list will be very inefficient using the algorithm used by random_shuffle (in fact, random_shuffle won't work on an std::list because the performance would be too poor).

One solution is to copy your data into a vector and do the random shuffle on that vector, then copy back into the list. It would be easier of course if you just used a different type of container in the first place that supported random access, but whether you should do that or not depends on the rest of your requirements.

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>

int main()
{
    // This may be required to seed random_shuffle
    // depending on your implementation.
    std::srand(static_cast<unsigned>(std::time(0)));

    std::vector<int> v;
    for (int i = 0; i < 52; ++i)
    {
        // Or you could push_back items from your list.
        v.push_back(i);
    }

    std::random_shuffle(v.begin(), v.end());

    for (std::vector<int>::size_type j = 0; j < v.size(); ++j)
    {
        // Or you could add items back to your list.
        std::cout << v[j] << ' ';
    }
    std::cout << std::endl;
}

 

[kai2005]

Hello raydona,
I have developed a class in Java with name DLList, which means, it is a double linked List, and it is also a circled List. In this Class I have also implemented the function for shuffle all elements in list. When you want the source code I can send you, please tell me your email adresse.

 

[kai2005]

/**
 * this is a member function in Class DLList
 * with function clone() you will have an
 * another DLList object, which have the same
 * elements as the original
 * when the originale DLList is empty, then 
 * the cloned DLList must also empty, then we 
 * need not do anything
 * otherwise, we bring an element from the cloned DLList
 * to the originale and in randomwise.
 * of course, you must first delete all elements in the
 * originale DLList
 * This is implemented in Java Language, but prinzip is 
 * there.
 */
public final synchronized void shuffle()
{
  Random r = new Random();
  DLList another (DLList)clone();
  removeAllElements();
  while(another.isEmpty() == false)
  {
    int size = another.size();
    int index = r.nextInt(size);
    Object o = another.elementAt(index);
    another.removeElementAt(index);
    addElement(o);
  }
}
[code]

 

[kai2005]

Sorry, something wrong typed, so do it again.

/**
 * this is a member function in Class DLList
 * with function clone() you will have an
 * another DLList object, which have the same
 * elements as the original
 * when the originale DLList is empty, then
 * the cloned DLList must also empty, then we
 * need not do anything
 * otherwise, we bring an element from the cloned DLList
 * to the originale and in randomwise.
 * of course, you must first delete all elements in the
 * originale DLList
 * This is implemented in Java Language, but prinzip is
 * there.
 */
public final synchronized void shuffle()
{
  Random r = new Random();
  DLList another = (DLList)clone();
  removeAllElements();
  while(another.isEmpty() == false)
  {
    int size = another.size();
    int index = r.nextInt(size);
    Object o = another.elementAt(index);
    another.removeElementAt(index);
    addElement(o);
  }
}

 

[cpjust]

I'm not sure how helpful that Java example would be since this is a C++ forum.

If you don't want to use standard STL containers, one way you could probably do it is like this:
Create a randomize() function that takes an int array, and the size of the array, then populates the array with unique random ints from 0 to (array size - 1).
You can then create a new list which is the same size as your old one, then copy the data into the new list in the order listed in your randomized array.

 

[uolj]

That is basically the algorithm used by random_shuffle, however it will be inefficient on a linked list.

Each time you look up the element in "another", it is a linear search for that index. Since you do this linear search once for each element in the list, the complexity of the algorithm is poorer than if you had random access through an array or vector.

Unless you know the list will always be very small, I'd still suggest using a vector as the shuffling algorithm will be much faster on large sets of data and on small sets of data the difference won't be very noticeable.

 

[kai2005]

my personal view-aspect: I know this is a C++ forum, so it is better to post code in C++. I will try to do so later. And I think, a programer should not think something in such Language, but just in logic, and the language is just a medien, to implement the logic process, to simulate the real world aspect.