Вопрос про случайное перемешивание массива

[Debauchee]

Всем, доброго времени суток!

Дико извиняюсь за тупой вопрос.
Есть одномерный массив из N элементов. Надо производить перестановку местами случайных пар элементов чтобы массив считался полностью перемешен.
Вопрос в том, сколько раз надо переставлять местами элементы в этих самых случайных парах, исходя из длины массива?
Будьте так добры, напомните как это решается, хоть как называется решение. В голову лезут какие-то мутные обрывки про сочетание, нормальное распределение, мат.ожидание и еще что-то, что ни разу не пригодилось за последние 30 с лишним лет.

Заранее благодарю!

[Аватар]

Обычно N достаточно
https://ru.wikipedia.org/wiki/%D0%A2...82%D1%81%D0%B0

[Serge_Bliznykov]

точно так.
тут на форуме это обсуждалось.

позволю себе процитировать себя же:

по поводу "тасования" карт:
но мне для решения таких задач ГОРАЗДО больше нравится вариант с перемешиванием. ( можно тут посмотреть) - он очень быст, прост и не требует наличия и манипулирования динамическими массивами!
Единственное, если подходить к вопросу серьёзно, необходимо учитывать, что распределение получается неравномерным. смотри пост №11 (с) kogemrka или, статью, на которую он ссылается:
http://mazanu.com/2008/11/blog-post_20.html

ну посмотрите реализацию - ТУТ

[Debauchee]

Спасибо за ответы!

Аватар, статью прочитал. Оказывается, все не так, как себе нафантазировал

На работе начальство захотело тест профпригодности менеджеров, да еще, чтобы он был в Экселе. Придумали около 300 вопросов с пятью вариантами ответов и критерии их интерпретации, осталось только все это "засунуть" в Эксель на VBA.
Собственно тасовать надо вопросы (индексы массива с вопросами) внутри каждого теста.
Вобщем-то, перестановку я уже написал, но возникли сомнения, что некоторые элементы массива останутся на исходном месте. Поэтому "для верности" и сделал 1E6 перестановок для массива вопросов в 289 элементов. Потом задумался, а не перебор ли это...

Public Function permutationArrat(ByRef arr As Variant) As Integer
    Dim r1 As Integer, r2 As Integer, ub As Integer
    Dim i As Long
    Dim temp As Variant

    ub = UBound(arr) + 1

    Randomize
    For i = 1 To 1000000# Step 1
        r1 = 0
        r2 = 0
        Do
            r1 = Int((ub * Rnd) + 1) - 1
            r2 = Int((ub * Rnd) + 1) - 1
        Loop While (r1 = r2)

        temp = arr(r2)
        arr(r2) = arr(r1)
        arr(r1) = temp
    Next i
    permutationArrat = ub
End Function

Private Sub test()	' проверка работы функции
    Dim arr As Variant
    Dim n As Integer

    arr = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)	' тестовый массив из 10 элементов
    Debug.Print Join(arr, " ")
    n = permutationArrat(arr)

    Debug.Print Join(arr, " ")
End Sub

[Serge_Bliznykov]

Потом задумался, а не перебор ли это...

перебор.
достаточно всего ОДИН раз пройтись по массив, правильно переставляя случайные элементы.

[Smitt&Wesson]

Сообщение от Аватар

Обычно N достаточно
https://ru.wikipedia.org/wiki/%D0%A2...82%D1%81%D0%B0

Это в идеале. На самом деле N + 1. Для нечётных массивов, при N, центральный элемент, в худшем случае остаётся на месте. В лучшем, смещается на одну позицию вправо или влево.

[Serge_Bliznykov]

Smitt&Wesson, извините, но Вы не правы.

я не знаю, читали ли Вы статью и правильно ли поняли ли её смысл,
но суть случайного перемешивания:

Современный алгоритм[править | править вики-текст]
Современный вариант алгоритма тасования Фишера–Йетса, предназначенный для использования в компьютерах, был представлен Ричардом Дурштенфельдом (Richard Durstenfeld) в 1964-м году в журнале Communications of the ACM том 7, выпуск 7, под названием "Algorithm 235: Random permutation",[2] и был популяризован Дональдом Кнутом во втором томе его книги Искусство программирования как "Алгоритм P".[3] Ни Дуршенфельд, ни Кнут в первом издании книги не упомянули об алгоритме Фишера и Йетса, и, похоже, не были осведомлены о нём. Во втором издании книги Искусство программирования, однако, это упущение было исправлено.[4]

Алгоритм, описанный Дуршенфельдом, отличается от алгоритма Фишера и Йетса в небольших, но существенных деталях. Чтобы компьютерная реализация алгоритма не тратила бесполезно время на перебор оставшихся чисел на шаге 3, у Дуршенфельда на каждой итерации выбираемые числа переносились в конец списка путем перестановки с последним невыбранным числом. Эта модификация сокращала временную сложность алгоритма до O(n), по сравнению с O(n2) для исходного алгоритма.[5] Это изменение приводит к следующему алгоритму.

Для тасования массива a из n элементов (индексы 0..n-1):
для всех i от n − 1 до 1 выполнить
j ← случайное число 0 ≤ j ≤ i
обменять местами a[j] и a[i]

Грубо говоря - берём I-й элемент массива. Получаем СЛУЧАЙНОЕ число, НОВУЮ позицию этого элемента. Меняем эти два элемента местами.
Берём следующий элемент массива и повторяем действия.
Позицию, куда поставить элемент - мы получаем случайным образом, причём ПРАВИЛЬНО.
С чего это вдруг центральный элемент останется на своём месте?!!

я в сообщении #3 выложил код на Паскале. Вы его запустите - проверьте (если нет Паскаля на компьютере, можно воспользоваться онлайн).

p.s. думаю, что автор темы уже утратил к ней интерес, судя по его активности...