Thank you for the code snippet.
What I don't understand is
if( (double)rand() / RAND_MAX < 1 / k )
Here, Why do we use less than inequality?
Why won't Udit's solution of just using the minimum random number work?
On Tuesday, 1 January 2013 20:57:47 UTC+5:30, Dave wrote:
>
> @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
>>>>
>>>
--
