Thread: Randomizing link list.

  1. #1
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335

    Randomizing link list.

    I'm not sure how to apporach this problem. If i have a link list with the following elements

    123

    how do i randomize it so each time the function is run it will return either 123, 321, 132 312 etc.

    and so for example the function is ran twice and it returns the new randomized list 321 and then 132 how do i keep a reference to the previous returned values so i dont get any duplicate randomized values..hmm

    Any hints?

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    If it's random, then it's entirely possible you're going to get the same sequence. Before you do this, why don't you figure out something easier. Like how to reverse a list.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    yes, i understand how to reverse something now. The real problem was not being able to print out the result because of scope/updating the variables of the updated list after the reverse function runs.


    then it's entirely possible you're going to get the same sequence
    you are right, I'm guessing it's not possible then?

    Could i possibly buffer the results somewhere and then compare if its already been added there otherwise....
    but the only problem with that is :

    123

    if i attempt to run the random function, and it returns a duplicate result already in the buffer then the formula i'm working with will fail. Because i have a while condition that basses it the total possibilties which is noofpos*noofpos i.e.:

    Code:
    while (i < noofpossibilities)
    random();
    if the result is not already in the buffer
    add it to the new random linklist
    else
    i++;
    so when i increment i again, i could possibly end up with another duplicate record already in the buffer therefore skipping another possible random link list elements.

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    You're looking for a permutation algorithm. It's not terribly difficult to print out all of the unique permutations of a sequence, but it's a great exercise in algorithm design, so I won't give you the answer. I will, however, give you a hint. Pay careful attention to how the numbers move around. You'll notice a distinct swap-shift behavior that's really easy to simulate with a linked list.
    My best code is written with the delete key.

  5. #5
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    To get a unique random number each time you call the function (until you run our of permutations anyway) you can calculate each permutation, then store each one in an array or linked list or whatever. Then randomize that list. Then when that function is called just pull the first one off the list and return it. When the function is called again it will pull the second number off the list, etc.

    Think of it more like a deck of cards. you have 52 unique cards and you want to get a random one each time you pull from the deck. What do you do? You shuffle the deck. So create your "deck", shuffle it, then deal as necessary.
    If you understand what you're doing, you're not learning anything.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Link List Insert prob
    By Bebs in forum C Programming
    Replies: 8
    Last Post: 12-03-2008, 10:28 PM
  2. reading data from a file - link list
    By peter_hii in forum C++ Programming
    Replies: 7
    Last Post: 10-25-2006, 09:11 AM
  3. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 10:33 PM
  4. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 10:16 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM