@Doom: Yes. It is necessary to go through the entire list. The code could
look like this:
int* p = head;
int k = 1;
while( head )
{
head = head -> next;
k++;
if( k * (double)rand() < RAND_MAX )
p = head;
}
Dave
On Sunday, December 30, 2012 12:40:28 PM UTC-6, Doom wrote:
> Hi Dave
>
> Please help me with some additional clarification regarding the
> implementation of this algo. How do we make use of random number generator?
>
> And is it necessary to traverse the list until the end?
>
>
> On Friday, 28 December 2012 19:35:07 UTC+5:30, Dave wrote:
>>
>> @Sanjeev: Set a pointer p to the first node. Traverse the list. When at
>> the kth node, set p to the kth node with probability 1/k. When you reach
>> the end of the list, return p, which will point to a random node with
>> uniform probability.
>>
>> Dave
>>
>> On Thursday, December 27, 2012 11:18:20 PM UTC-6, Sanjeev wrote:
>>
>>> i mean the length of the linked list is not known to us.
>>> @udit how can we do this in single traversal ? i think we need to
>>> traverse the linked list twice in your case.
>>> Please reply if i am wrong ?
>>>
>>> On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal <udit...@gmail.com>wrote:
>>>
>>>> If the length of the linked is infinite then the above algo would do
>>>> the needful.
>>>> In case you have a finite length linked list, then you can normalize
>>>> the random value using following:
>>>> Suppose length of linked list is: l
>>>> random number is: r; and r > l
>>>> then new random number would be: r1 = r%l;
>>>> now again use the above algo using new random number r1;
>>>>
>>>> On Thu, Dec 27, 2012 at 4:12 PM, Vineeth <vineet...@gmail.com> wrote:
>>>> > You said : "Given a linked list of infinite length"
>>>> >
>>>> > On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
>>>> > <naveenshukla...@gmail.com> wrote:
>>>> >> But suppose a random number generate a value 5 and your linked list
>>>> has only
>>>> >> four elements. In that case what would be the answer ???
>>>> >>
>>>> >>
>>>> >> On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri <
>>>> hpre...@gmail.com>
>>>> >> wrote:
>>>> >>>
>>>> >>> Well my algo will be Something like this
>>>> >>>
>>>> >>> 1> Get a Random number. Perhaps You can have the function like
>>>> Randon(List
>>>> >>> *head, int Randomnumber)
>>>> >>>
>>>> >>> 2> Use the function argument Randomnumber to loop the list.
>>>> >>> i.e. for(int count=0;count<=Randomnumber;count++ ){
>>>> >>> head = head -> next;
>>>> >>> }
>>>> >>>
>>>> >>> 3> print (head->value);
>>>> >>>
>>>> >>> 4> return ;
>>>> >>>
>>>> >>> Now as we are using byvalue when we return the value of head
>>>> remains the
>>>> >>> same old head value. So everytime we call we are traversing the
>>>> same old
>>>> >>> list.
>>>> >>>
>>>> >>> The Random variable can be taken inside the function itself if the
>>>> user
>>>> >>> is not taking the random value.
>>>> >>> i.e. int Randomnumber = random(); and now the user can calll
>>>> Simple
>>>> >>> Random(head);
>>>> >>>
>>>> >>>
>>>> >>>
>>>> >>> On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
>>>> >>> <naveenshukla...@gmail.com> wrote:
>>>> >>>>
>>>> >>>> random node
>>>> >>>
>>>> >>>
>>>> >>> --
>>>> >>>
>>>> >>>
>>>> >>
>>>> >>
>>>> >>
>>>> >>
>>>> >> --
>>>> >> With Best Wishes
>>>> >>
>>>> >> From:
>>>> >>
>>>> >> Naveen Shukla
>>>> >> IIIT Allahabad
>>>> >> B.Tech IT 4th year
>>>> >> Mob No: 07860896972
>>>> >> E-mail naveenshukla...@gmail.com
>>>> >>
>>>> >> --
>>>> >>
>>>> >>
>>>> >
>>>> > --
>>>> >
>>>> >
>>>>
>>>>
>>>>
>>>> --
>>>> Udit Agarwal
>>>> B.Tech. ( Information Technology ) , 7th Semester,
>>>> Indian Institute of Information Technology
>>>> Allahabad - 211012, India
>>>> Email : udit...@gmail.com
>>>> Mobile: +91-9411656264
>>>>
>>>> --
>>>>
>>>>
>>>>
>>>
>>>
>>> --
>>> With Best Wishes
>>>
>>> From:
>>>
>>> Naveen Shukla
>>> IIIT Allahabad
>>> B.Tech IT 4th year
>>> Mob No: 07860896972
>>> E-mail naveenshukla...@gmail.com
>>>
>>
--
