CODEWITHSUNDEEP
c++
Tien Nguyen
Tien Nguyen

Reputation: 51

Randomly shuffling a linked list

I'm currently working on a project and the last piece of functionality I have to write is to shuffle a linked list using the rand function.

I'm very confused on how it works.

Could someone clarify on how exactly I could implement this?

I've looked at my past code examples and what I did to shuffle an array but the arrays and linked lists are pretty different.

Edit: For further clarifications my Professor is making us shuffle using a linked list because he is 'awesome' like that.

Upvotes: 0

Views: 3727

Answers (4)

doron
doron

Reputation: 28872

The big difference between an array and a linked list is that when you use an array you can directly access a given element using pointer arithmetic which is how the operator[] works.

That however does not preclude you writing your own operator[] or similar where you walk the list and count out the nth element of the list. Once you got this far, removing the element and placing it into a new list is quite simple.

The big difference is where the complexity is O(n) for an array it becomes O(n^2) for a linked list.

Upvotes: 0

CiaPan
CiaPan

Reputation: 9570

You can always add another level of indirection... ;)
(see Fundamental theorem of software engineering in Wikipedia)

Just create an array of pointers, sized to the list's length, unlink items from the list and put their pointers to the array, then shuffle the array and re-construct the list.

EDIT

If you must use lists you might use an approach similar to merge-sort:

  • split the list into halves,
  • shuffle both sublists recursively,
  • merge them, picking randomly next item from one or the other sublist.

Upvotes: 3

HolyBlackCat
HolyBlackCat

Reputation: 96071

You can try iterate over list several times and swap adjacent nodes with certain probablity. Something like this:

const float swapchance = 0.25;
const int itercount = 100;

struct node
{
    int val;
    node *next;
};

node *fisrt;

{ // Creating example list
    node *ptr = 0;
    for (int i = 0; i < 20; i++)
    {
        node *tmp = new node;
        tmp.val = i;
        tmp.next = ptr;
        ptr = tmp;
    }
}

// Shuffling
for (int i = 0; i < itercount; i++)
{
    node *ptr = first;
    node *prev = 0;
    while (ptr && ptr->next)
    {
        if (std::rand() % 1000 / 1000.0 < swapchance)
        {
            prev->next = ptr->next;
            node *t = ptr->next->next;
            ptr->next->next = ptr;
            ptr->next = t;
        }
        prev = ptr;
        ptr = ptr->next;
    }
}

Upvotes: 0

Neil Kirk
Neil Kirk

Reputation: 21763

I don't know if it gives a reasonable random distribution :D

bool randcomp(int, int)
{
    return (rand()%2) != 0;
}


mylist.sort(randcomp);

Upvotes: 0

Related Questions