Рубрики

Перемешать данный массив с помощью алгоритма перемешивания Фишера-Йейтса

Для данного массива напишите программу для генерации случайной перестановки элементов массива. Этот вопрос также задается как «перетасовать колоду карт» или «рандомизировать данный массив». Здесь shuffle означает, что каждая перестановка элемента массива должна быть одинаково вероятной.


Пусть заданный массив будет arr [] . Простое решение — создать вспомогательный массив temp [], который изначально является копией arr [] . Произвольно выберите элемент из temp [] , скопируйте случайно выбранный элемент в arr [0] и удалите выбранный элемент из temp [] . Повторите тот же процесс n раз и продолжайте копировать элементы в arr [1], arr [2],…. Временная сложность этого решения будет O (n ^ 2).

Алгоритм Фишера-Йейтса работает в O (n) время сложности. Здесь предполагается, что нам дана функция rand (), которая генерирует случайное число за O (1) раз.
Идея состоит в том, чтобы начать с последнего элемента, заменить его случайно выбранным элементом из всего массива (включая последний). Теперь рассмотрим массив от 0 до n-2 (размер уменьшен на 1) и повторяем процесс, пока мы не дойдем до первого элемента.

Ниже приводится подробный алгоритм

To shuffle an array a of n elements (indices 0..n-1):
  for i from n - 1 downto 1 do
       j = random integer with 0 <= j <= i
       exchange a[j] and a[i]

Ниже приведена реализация этого алгоритма.

C ++

// C ++ Программа для перемешивания заданного массива
#include<bits/stdc++.h> 
#include <stdlib.h> 
#include <time.h> 

using namespace std; 

  
// Утилита для замены целых чисел

void swap (int *a, int *b) 

    int temp = *a; 

    *a = *b; 

    *b = temp; 

  
// Вспомогательная функция для печати массива

void printArray (int arr[], int n) 

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

        cout << arr[i] << " "

    cout << "\n"

  
// Функция для генерации случайного
// перестановка arr []

void randomize (int arr[], int n) 

    // Используем другое начальное значение, чтобы

    // мы не получаем одинаковый результат каждый раз

    // мы запускаем эту программу

    srand (time(NULL)); 

  

    // Начинаем с последнего элемента и меняем местами

    // по одному. Нам не нужно бежать за

    // первый элемент, поэтому я> 0

    for (int i = n - 1; i > 0; i--) 

    

        // Выбрать случайный индекс от 0 до i

        int j = rand() % (i + 1); 

  

        // Поменять местами arr [i] с элементом

        // по случайному индексу

        swap(&arr[i], &arr[j]); 

    

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

int main() 

    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8}; 

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

    randomize (arr, n); 

    printArray(arr, n); 

  

    return 0; 

  
// Этот код предоставлен
// ратбхупендра

С

// C Программа для перемешивания заданного массива

  
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

  
// Утилита для замены целых чисел

void swap (int *a, int *b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

  
// Вспомогательная функция для печати массива

void printArray (int arr[], int n)

{

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

        printf("%d ", arr[i]);

    printf("\n");

}

  
// Функция для генерации случайной перестановки arr []

void randomize ( int arr[], int n )

{

    // Используем другое начальное значение, чтобы мы не получали то же самое

    // результат каждый раз, когда мы запускаем эту программу

    srand ( time(NULL) );

  

    // Начать с последнего элемента и поменять местами один за другим. Мы не

    // нужно запустить для первого элемента, поэтому я> 0

    for (int i = n-1; i > 0; i--)

    {

        // Выбрать случайный индекс от 0 до i

        int j = rand() % (i+1);

  

        // Поменяйте местами arr [i] с элементом со случайным индексом

        swap(&arr[i], &arr[j]);

    }

}

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

int main()

{

    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};

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

    randomize (arr, n);

    printArray(arr, n);

  

    return 0;

}

Джава

// Java-программа для перемешивания заданного массива

import java.util.Random;

import java.util.Arrays;

public class ShuffleRand 

{

    // Функция для генерации случайной перестановки arr []

    static void randomize( int arr[], int n)

    {

        // Создание объекта для класса Random

        Random r = new Random();

          

        // Начать с последнего элемента и поменять местами один за другим. Мы не

        // нужно запустить для первого элемента, поэтому я> 0

        for (int i = n-1; i > 0; i--) {

              

            // Выбрать случайный индекс от 0 до i

            int j = r.nextInt(i+1);

              

            // Поменяйте местами arr [i] с элементом со случайным индексом

            int temp = arr[i];

            arr[i] = arr[j];

            arr[j] = temp;

        }

        // Печатает случайный массив

        System.out.println(Arrays.toString(arr));

    }

      

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

    public static void main(String[] args) 

    {

          

         int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};

         int n = arr.length;

         randomize (arr, n);

    }

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

питон

# Программа Python для перемешивания заданного массива

import random

  
# Функция для генерации случайной перестановки arr []

def randomize (arr, n):

    # Начните с последнего элемента и поменяйте местами один за другим. Мы не

    # нужно запустить для первого элемента, поэтому я> 0

    for i in range(n-1,0,-1):

        # Выберите случайный индекс от 0 до i

        j = random.randint(0,i+1)

  

        # Поменяйте местами arr [i] с элементом со случайным индексом

        arr[i],arr[j] = arr[j],arr[i]

    return arr

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

arr = [1, 2, 3, 4, 5, 6, 7, 8]

n = len(arr)

print(randomize(arr, n))

  

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

C #

// C # код для количества цифр
// в произведении двух чисел

using System;

  

class GFG


// Функция для генерации
// случайная перестановка arr []

    static void randomize(int []arr, int n)

    {

        // Создание объекта

        // для случайного класса

        Random r = new Random();

          

        // Начинаем с последнего элемента и

        // поменять местами одну за другой. Нам не нужно

        // запустить для первого элемента

        // вот почему я> 0

        for (int i = n - 1; i > 0; i--) 

        {

              

            // Выбрать случайный индекс

            // от 0 до i

            int j = r.Next(0, i+1);

              

            // Поменяйте местами arr [i] с

            // элемент со случайным индексом

            int temp = arr[i];

            arr[i] = arr[j];

            arr[j] = temp;

        }

        // Печатает случайный массив

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

        Console.Write(arr[i] + " ");

    }

      

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

static void Main()

{

    int[] arr = {1, 2, 3, 4, 

                 5, 6, 7, 8};

    int n = arr.Length;

    randomize (arr, n);

}
}

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

PHP

<?php
// PHP программа для перемешивания
// данный массив

  
// Функция для генерации
// случайная перестановка arr []

function randomize ($arr, $n)

{

    // Начать с последнего элемента

    // и меняем местами один за другим. Мы

    // не нужно бежать за

    // первый элемент, поэтому я> 0

    for($i = $n - 1; $i >= 0; $i--)

    {

        // Выбрать случайный индекс

        // от 0 до i

        $j = rand(0, $i+1);

  

        // Поменяйте местами arr [i] с

        // элемент со случайным индексом

        $tmp = $arr[$i];

        $arr[$i] = $arr[$j];

        $arr[$j] = $tmp;

    }

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

    echo $arr[$i]." ";

}

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

$arr = array(1, 2, 3, 4, 

             5, 6, 7, 8);

$n = count($arr);

randomize($arr, $n);

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


Выход :

7 8 4 6 3 1 2 5

Вышеупомянутая функция предполагает, что rand () генерирует случайное число.

Сложность времени: O (n), предполагая, что функция rand () занимает O (1) время.

Как это работает?
Вероятность того, что i-й элемент (включая последний) переместится в последнюю позицию, равен 1 / n, потому что мы случайным образом выбираем элемент в первой итерации.

Вероятность того, что i-й элемент перейдет во вторую последнюю позицию, можно доказать как 1 / n, разделив его на два случая.
Случай 1: i = n-1 (индекс последнего элемента) :
Вероятность того, что последний элемент попадет во вторую последнюю позицию, равна = (вероятность того, что последний элемент не останется в своей исходной позиции) x (вероятность того, что индекс, выбранный на предыдущем шаге, будет выбран снова, чтобы последний элемент был заменен)
Таким образом, вероятность = ((n-1) / n) x (1 / (n-1)) = 1 / n
Случай 2: 0 <i <n-1 (индекс не последнего) :
Вероятность попадания i-го элемента во вторую позицию = (вероятность того, что i-й элемент не выбран на предыдущей итерации) x (вероятность того, что i-й элемент выбран на этой итерации)
Таким образом, вероятность = ((n-1) / n) x (1 / (n-1)) = 1 / n

Мы можем легко обобщить приведенное выше доказательство для любой другой позиции.

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

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

Перемешать данный массив с помощью алгоритма перемешивания Фишера-Йейтса

0.00 (0%) 0 votes