Операция перемешивания значений

@shurezz · Регистрация: 18.11.2010

Студворк — интернет-сервис помощи студентам

Есть массив из n элементов, содержащих значения от 1 до n. Как можно перемешать их в рандомном порядке (напр. 1 2 3 4 5 -> 2 5 1 3 4).
Пробую делать это так:

Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Dim m() As Integer
Const n As Integer = 100  ' количество элементов массива
 
Private Sub Перемешивание()
Dim i as Integer, j As Integer
Dim Temp As integer
 
On Error GoTo Err
  
   n = Val(InputBox('___'))  
   ReDim m(1 To n)
 
   Randomize
   For i = 1 to n 
  
   Temp = Rnd * n  1 + 1 ' Целое число от 1 до n
1: Temp = Temp + 1
 
   If Temp = n + 1 Then Temp = 1
 
   For j = 1 To n
      If Temp = m(j) Then GoTo 1
   Next j
   
   m(i) = Temp
   Next i
 
Err:
End Sub

Но это слишком медленно. При массиве из 1000 чисел занимает 0.3-0.6 с, а при n = 2000 около 3-5 секунд (Celeron 2.8 256mb).

Посоветуйте что-нибудь.
Заранее спасибо.

11.01.2011, 17:02

Поиск в Сети на строку 'shuffle array' должен дать нужные ссылки.

@palva · 11.01.2011, 17:29

Я так и не разобрался в вашем алгоритме.

Могу предложить следующий алгоритм для перемешивания:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = 10    ' Задайте здесь и в следующей строчке нужное значение
Dim a(10) ' Нулевой индекс не используем
' Начальное заполнение
For i = 1 To n
  a(i) = i
Next
' Перемешивание
Randomize
For i = 10 To 2 Step -1
  j = Int(Rnd*i) + 1
  If i<>j Then
    t = a(i)
    a(i) = a(j)
    a(j) = t
  End If
Next

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

@Alexey Spirin · 11.01.2011, 20:48

Перебор массива в случайном порядке
http://vbrussian.com/Examples.asp?ID=93

@shurezz · 13.01.2011, 09:35 **[ТС]**

Alexey Spirin - спасибо
Посмотрел скрипт. Очень полезная вещь, но при количестве чисел до 100 мой код если и уступает, то крайне немного, а порой и выигрывает по скорости. При n > 1000 тем не менее лучше использовать Ваш исходник.
Спасибо.

@palva · 24.01.2011, 17:14

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
' Для быстрого перемешивания можно позаимстовать
' перемешивание из криптоалгоритма RC4
' (Следующий текст написан на VBScript)
'
Const n = 100  ' Размер массива (в RC4 равен 256)
ReDim a(n - 1) ' Используется также нулевой индекс
' Начальное заполнение последовательностью 0...n-1
For i = 0 To n - 1
 a(i) = i
Next
' В качестве Randomize заполняем произвольным образом
' целый массив kep длины n. (Это секретный ключ алгоритма RC4)
' Можно обойтись и без дополнительного массива, если в
' соответствующем месте алгоритма вместо элемента массива
' поставить какую нибудь простенькую функцию, зависящую
' от индекса. Например, если массив заполнен как 0, 1, 2,
' 3, 0, 1, 2, 3 и т. д., то функция будет следующей:
' kep(i) = i Mod 4
' В данном примере мы заполним массив именно по этому
' алгоритму:
ReDim kep(n - 1)
For i = 0 To n - 1
  kep(i) = i Mod 4
Next
' Теперь сам алгоритм перемешивания:
j = 0  
For i = 0 To n-1
  j = (j + a(i) + kep(i)) Mod n
  If i<>j Then
    temp = a(i)
    a(i) = a(j)
    a(j) = temp
  End If
Next
' Перемешивание выполнено, но это не всё.
' В алгоритме RC4 массив a(256) используется в качестве
' внутреннего состояния некоторого датчика п.с.ч.,
' вырабатывающего криптографическую гамму - случайные байты,
' которые XORятся с за- (или рас)шифровываемым текстом.
' Этот датчик можно использовать и для других целей,
' например для тасования колоды карт. Период датчика существенно
' зависит от ключа (массива kep). Как показывают исследования,
' бывают очень плохие ключи. Но если ключ взят случайно, то период
' очень большой. Ну, может быть, и не n!*n*n - теоретическая верхняя
' граница периода, но во всяком случае больше чем у функции rnd.
' Для взвода датчика делается:
i=0
j=0
' Теперь выработка случайного байта осуществляется так:
i = (i+1) Mod n
j = (j+a(i)) Mod n
If i<>j Then
  temp=a(i)
  a(i)=a(j)
  a(j)=temp
End If
r = a((a(i)+a(j)) Mod n)
' Если учесть, что n=256 и поэтому Mod n можно заменить на And 255
' то получается очень быстрый датчик, который работает
' заведомо быстрее чем rnd. Правда, он вырабатывает байты, а не Single.

24.01.2011, 19:01

Алгоритм такой же...
вот функция

Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Private Function mRND(mVar As Variant) As Variant
On Error Resume Next
    Dim i As Integer
    Dim index As Integer
    Dim mTMP As Variant
    If IsArray(mVar) Then
        Randomize
        For i = UBound(mVar) To LBound(mVar) Step -1
            index = Int((i - LBound(mVar) + 1) * Rnd + LBound(mVar))
            mTMP = mVar(index)
            mVar(index) = mVar(i)
            mVar(i) = mTMP
        Next i
    End If
mRND = mVar
End Function

Новые блоги и статьи Все статьи Все блоги /
Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .
Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .

Comanche
	11.01.2011, 17:02
	Поиск в Сети на строку 'shuffle array' должен дать нужные ссылки.

@Alexey Spirin 2 / 2 / 1 Регистрация: 18.10.2007 Сообщений: 1,748
	11.01.2011, 20:48
	Перебор массива в случайном порядке http://vbrussian.com/Examples.asp?ID=93 0

@shurezz 1 / 1 / 0 Регистрация: 18.11.2010 Сообщений: 139
	13.01.2011, 09:35 [ТС]
	Alexey Spirin - спасибо Посмотрел скрипт. Очень полезная вещь, но при количестве чисел до 100 мой код если и уступает, то крайне немного, а порой и выигрывает по скорости. При n > 1000 тем не менее лучше использовать Ваш исходник. Спасибо. 0