Computer Science, asked by vishwanth134082846, 1 year ago

Select a number randomly with probability proportional to its magnitude from the given array of n elements
consider an experiment, selecting an element from the list A randomly with probability proportional to its magnitude. assume we are doing the same experiment for 100 times with replacement, in each experiment you will print a number that is selected randomly from A.

Ex 1: A = [0 5 27 6 13 28 100 45 10 79]
let f(x) denote the number of times x getting selected in 100 experiments.
f(100) > f(79) > f(45) > f(28) > f(27) > f(13) > f(10) > f(6) > f(5) > f(0)


note: code needed in python without using numpy

Answers

Answered by BushrajavediqbalKhan
16

Explanation:

import random

A = [0,5,27,6,13,28,100,45,10,79]

def propotional_sampling(A):

   sum=0

   for i in range(len(A)):

       sum = sum + A[i]

   d_dash=[]

   for j in range(len(A)):

       d_dash[j].append((A[j]/sum))

   #cumulative sum

   d_bar =[]

   d_bar[0]= 0

   for k in range(len(A)):

       d_bar[k] = d_bar[k] + d_dash[k]

   r = random.uniform(0.0,1.0)

   number=0

   for p in range(len(d_bar)):

       if(r<=d_bar[p]):

           number=d_bar[p]

   return number

def sampling_based_on_magnitued():

   for i in range(1,100):

       number = propotional_sampling(A)

       print(number)

Below mention solution is also helpful

import random

from itertools import accumulate

from bisect import bisect

A = [0,5,27,6,13,28,100,45,10,79]

def propotional_sampling(A, n=100):

   # calculate cumulative sum from A:

   cum_sum = [*accumulate(A)]

   # cum_sum = [0, 5, 32, 38, 51, 79, 179, 224, 234, 313]

   out = []

   for _ in range(n):

       i = random.random()                     # i = [0.0, 1.0)

       idx = bisect(cum_sum, i*cum_sum[-1])    # get index to list A

       out.append(A[idx])

   return out

Similar questions