Рубрики

Выберите случайное число из потока с пробелом O (1)

Учитывая поток чисел, генерировать случайное число из потока. Вам разрешено использовать только O (1) пробел, а ввод осуществляется в виде потока, поэтому вы не можете хранить ранее просмотренные числа.

Итак, как мы генерируем случайное число из всего потока, чтобы вероятность выбора любого числа была 1 / n. с O (1) дополнительным пространством? Эта проблема является вариацией отбора проб в резервуаре . Здесь значение k равно 1.

1) Инициализируйте 'count' как 0, 'count' используется для хранения количества чисел, которые до сих пор видели в потоке.
2) Для каждого числа «х» из потока, выполните следующие
… .. a) Увеличьте «count» на 1.
… .. б) Если count равен 1, установить результат как x и вернуть результат.
… .. в) Генерация случайного числа от 0 до «count-1». Пусть сгенерированное случайное число будет i.
… .. d) Если i равно 'count — 1', обновите результат как x.

C ++

// Эффективная программа на C ++ для случайного выбора
// число из потока чисел.
#include <bits/stdc++.h>
#include <time.h>

using namespace std;

  
// Функция для случайного выбора элемента
// из потока [0], потока [1], .. потока [i-1]

int selectRandom(int x) 

    static int res; // Результирующее случайное число

    static int count = 0; // Количество посещенных номеров

                          // пока в потоке

  

    count++; // увеличиваем количество увиденных номеров

  

    // Если это первый элемент из потока,

    // верни это

    if (count == 1) 

        res = x; 

    else

    

        // Генерируем случайное число от 0 до 1

        int i = rand() % count; 

  

        // Заменить предыдущее случайное число на

        // новый номер с вероятностью 1 / счет

        if (i == count - 1) 

            res = x; 

    

    return res; 

  
// Код драйвера

int main() 

    int stream[] = {1, 2, 3, 4}; 

    int n = sizeof(stream) / sizeof(stream[0]); 

  

    // Используйте разные начальные значения для каждого прогона.

    srand(time(NULL)); 

    for (int i = 0; i < n; ++i) 

        cout << "Random number from first " << i + 1 

             << " numbers is " << selectRandom(stream[i]) << endl; 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// Эффективная программа на Си для случайного выбора числа из потока чисел.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

  
// Функция для случайного выбора элемента из stream [0], stream [1], .. stream [i-1]

int selectRandom(int x)

{

    static int res;    // Результирующее случайное число

    static int count = 0;  // Количество посещенных номеров в потоке

  

    count++;  // увеличиваем количество увиденных номеров

  

    // Если это первый элемент из потока, вернуть его

    if (count == 1)

        res = x;

    else

    {

        // Генерируем случайное число от 0 до 1

        int i = rand() % count;

  

        // Заменить предыдущее случайное число новым числом с вероятностью 1 / число

        if (i == count - 1)

            res  = x;

    }

    return res;

}

  
// Программа драйвера для проверки вышеуказанной функции.

int main()

{

    int stream[] = {1, 2, 3, 4};

    int n = sizeof(stream)/sizeof(stream[0]);

  

    // Используйте разные начальные значения для каждого прогона.

    srand(time(NULL));

    for (int i = 0; i < n; ++i)

        printf("Random number from first %d numbers is %d \n",

                                i+1, selectRandom(stream[i]));

    return 0;

}

Джава

// Эффективная Java-программа для случайного выбора числа из потока чисел.

  

import java.util.Random;

  

public class GFG 

{

    static int res = 0;    // Результирующее случайное число

    static int count = 0// Количество посещенных номеров в потоке

      

    // Метод случайного выбора элемента из stream [0], stream [1], .. stream [i-1]

    static int selectRandom(int x)

    {

        count++; // увеличиваем количество увиденных номеров

          

        // Если это первый элемент из потока, вернуть его

        if (count == 1)

            res = x;

        else

        {

             // Генерируем случайное число от 0 до 1

            Random r = new Random();

            int i = r.nextInt(count);

              

            // Заменить предыдущее случайное число новым числом с вероятностью 1 / число

            if(i == count - 1)

                res = x;

        }

        return res;

    }

      

    // Программа драйвера для проверки вышеуказанной функции.

    public static void main(String[] args)

    {

        int stream[] = {1, 2, 3, 4};

        int n = stream.length;

        for(int i = 0; i < n; i++)

            System.out.println("Random number from first " + (i+1) +

                               " numbers is " + selectRandom(stream[i]));

    }

}
// Этот код предоставлен Sumit Ghosh

python3

# Эффективная программа на python3
# для случайного выбора номера
# из потока чисел.

import random

  
# Функция случайного выбора элемента
# из потока [0], потока [1], .. потока [i-1]

def selectRandom(x):

      

    # Результирующее случайное число

    res = 0;

      

    Количество посещенных номеров

    # пока в потоке

    count = 0;

  

    # приращение количества чисел

    # видел до сих пор

    count += 1;

  

    # Если это первый элемент

    # из потока, верните его

    if (count == 1):

        res = x;

    else:

          

        # Создать случайное число

        № от 0 до 1

        i = random.randrange(count);

  

        # Заменить предыдущее случайное число

        # с новым номером с 1 / кол

        # вероятность

        if (i == count - 1):

            res = x;

    return res;

  
Код водителя

stream = [1, 2, 3, 4];

n = len(stream);

  
# Используйте другое начальное значение
# за каждый прогон.

for i in range (n):

    print("Random number from first"

         (i + 1), "numbers is"

          selectRandom(stream[i]));

  
# Этот код предоставлен mits

C #

// Эффективная программа на C # для случайного выбора
// выбираем число из потока чисел.

using System;

  

class GFG 

{

    // Результирующее случайное число

    static int res = 0; 

      

    // Количество посещенных номеров

    // пока в потоке

    static int count = 0; 

      

    // Метод случайного выбора

    // элемент из потока [0],

    // stream [1], .. stream [i-1]

    static int selectRandom(int x)

    {

        // увеличить счетчик

        // числа увиденные до сих пор

        count++; 

          

        // Если это первый

        // элемент из потока,

        // верни это

        if (count == 1)

            res = x;

        else

        {

            // Генерируем случайное число

            // от 0 до 1

            Random r = new Random();

            int i = r.Next(count);

              

            // Заменить предыдущий случайный

            // номер с новым номером

            // с вероятностью 1 / счет

            if(i == count - 1)

                res = x;

        }

        return res;

    }

      
// Код драйвера

public static void Main()

{

        int[] stream = {1, 2, 3, 4};

        int n = stream.Length;

        for(int i = 0; i < n; i++)

            Console.WriteLine("Random number from "

                              "first {0} numbers is {1}" ,

                          i + 1, selectRandom(stream[i]));

    }

}

  
// Этот код предоставлен mits

PHP

<?php
// Эффективная PHP-программа для случайного выбора
// выбираем число из потока чисел.

  
// Функция для случайного выбора элемента
// из потока [0], потока [1], .. потока [i-1]

function selectRandom($x)

{

      

    // Результирующее случайное число

    $res;

      

    // Количество посещенных номеров

    // в потоке

    $count = 0;

  

    // увеличиваем количество увиденных чисел

    // слишком далеко

    $count++;

  

    // Если это первый элемент

    // из потока, вернуть его

    if ($count == 1)

        $res = $x;

    else

    {

          

        // Генерируем случайное число из

        // 0 к счету - 1

        $i = rand() % $count;

  

        // Заменить предыдущее случайное число

        // с новым номером с 1 / кол

        // вероятность

        if (i == $count - 1)

            $res = $x;

    }

    return $res;

}

  
// Программа драйвера для проверки вышеуказанной функции.

    $stream = array(1, 2, 3, 4);

    $n = sizeof($stream)/sizeof($stream[0]);

  

    // Используем другое начальное значение для

    // каждый прогон.

    srand(time(NULL));

      

    for ($i = 0; $i < $n; ++$i)

        echo "Random number from first "

                   $i+1, "numbers is " ,

        selectRandom($stream[$i]), "\n" ;

  
// Этот код предоставлен нитин митталь.
?>


Выход:

Random number from first 1 numbers is 1
Random number from first 2 numbers is 1
Random number from first 3 numbers is 3
Random number from first 4 numbers is 4

Вспомогательное пространство: O (1)

Как это работает
Нам нужно доказать, что каждый элемент выбран с вероятностью 1 / n, где n — это количество элементов, которые были просмотрены до сих пор. Для каждого нового элемента потока x мы выбираем случайное число от 0 до 'count -1', если выбранное число равно 'count-1', мы заменяем предыдущий результат на x.

Чтобы упростить доказательство, давайте сначала рассмотрим последний элемент, последний элемент заменяет ранее сохраненный результат с вероятностью 1 / n. Таким образом, вероятность получения последнего элемента в результате равна 1 / n.

Давайте теперь поговорим о втором последнем элементе. Когда второй последний элемент обрабатывается первый раз, вероятность того, что он заменил предыдущий результат, равна 1 / (n-1). Вероятность того, что предыдущий результат останется при рассмотрении n-го элемента, равна (n-1) / n. Таким образом, вероятность того, что второй последний элемент выбран в последней итерации, равна [1 / (n-1)] * [(n-1) / n], что равно 1 / n.

Точно так же мы можем доказать для третьего последнего элемента и других.

Ссылки:
Отбор проб из водохранилища

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Выберите случайное число из потока с пробелом O (1)

0.00 (0%) 0 votes