@Udit: Here is the proof: At step k, node k is selected with probability
1/k. On the (k+1)st step, node k is replaced with probability 1/(k+1). Thus
it is retained with probability 1 - 1/(k+1) = k/(k+1). On subsequent steps,
node k is retained with probabilities (k+1)/(k+2), (k+2)/(k+3), ...,
(n-1)/n. Thus, node k is selected on the kth step and then retained until
the end of the list with probability 1/k * k/(k+1) * (k+1)/(k+2) * ... *
(n-1) / n. Each denominator cancels with the succeeding numerator, so the
product collapses to 1/n.
Dave
On Friday, December 28, 2012 10:46:17 AM UTC-6, Udit Agarwal wrote:
> @Dave: U said that the node p returned will be assigned to some kth
> node with probability 1/k. then the probability for p to be assigned
> to 1,2,3... nodes would be like 1/1, 1/2, 1/3, and so on.. the how is
> the node p is assigned with uniform probability.
>
> On Fri, Dec 28, 2012 at 7:35 PM, Dave <dave_an...@juno.com <javascript:>>
> 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
> >
> > --
> >
> >
>
>
>
> --
> Udit Agarwal
> B.Tech. ( Information Technology ) , 7th Semester,
> Indian Institute of Information Technology
> Allahabad - 211012, India
> Email : udit...@gmail.com <javascript:>
> Mobile: +91-9411656264
>
--
