Veresk

*Lazarus *public
А как будет няшнее победить массив? Вот есть массив A[1..N], Его надо заполнить числами от 1 до N рандомно и не повторяясь.
1. Заполнять через random[N] и проверять, не генерилось ли такое число ранее.
2. Забить массив числами 1..N, а потом переставлять их местами в случайном порядке, пока не надоест.

#1923805
from Psi+, 26 days ago

← All messages

Replies (39)

Post a reply (xmpp)

@wyldrodney:
В ruby использовал бы 2, так как есть метод shuffle. Писал бы сам — первый вариант, так как это проще чем shuffle.
#1923805/1
from web, 26 days ago
@HeX:
с точки зрения машинного времени первое должно быть быстрее, но второе вроде как результативнее.
#1923805/2
from web, 26 days ago
@HeX:
@HeX а нет стоп
#1923805/3
from web, 26 days ago, in reply to /2
@HeX:
в первом сравнение с каждым элементом, я сего не учел. Бери второй метод, он полущ
#1923805/4
from web, 26 days ago
@HeX:
@HeX но сложнее в реализации
#1923805/5
from web, 26 days ago, in reply to /4
@Veresk:
@HeX первое будет генерить последнюю позицию долго и упорно, пока не совпадёт единственное число
#1923805/6
from Psi+, 26 days ago, in reply to /3
@Veresk:
@HeX второе проще, меньше сущностей
#1923805/7
from Psi+, 26 days ago, in reply to /5
@HeX:
@Veresk верно. Но писать проще именно первое, сравнение в цикле, никаких сложностей, но слоу при работе
#1923805/8
from talkonaut-iphone_5.91_3f08b601, 26 days ago, in reply to /7
@Veresk:
@HeX а во втором надо учеть то, что итоговый массив может быть и больше и меньше начального, тогда там могут появляться повторы
#1923805/9
from Psi+, 26 days ago, in reply to /8
@HeX:
@Veresk динамический массив от n до m? Так и бери числа от n до m, и таскай их до потери сознания, никаких тебе повторов
#1923805/10
from talkonaut-iphone_5.91_3f08b601, 26 days ago, in reply to /9
@HeX:
@HeX пока чят, мне пора идти:( удачи в написании ;)
#1923805/11
from talkonaut-iphone_5.91_3f08b601, 26 days ago, in reply to /10
@torgash:
первый случай будет более общим с учетом того, что чисел может быть и не ровно N, а даже 10^(+-)15 N
#1923805/12
from TalkGadgetA244D1F5, 26 days ago
@wyldrodney:
Погоди, что значит "рандомно и не повторяясь"? 1,2,3...n чем не вариант?
#1923805/13
from web, 26 days ago
@torgash:
а вообще-то это делается так: задаешь еще один массив из чисел 1...N, в котором при каждом рандомном выборе записываешь в позицию число N+1 и берешь N+1 как условие пропуска позиции. Рандому, соответственно, нужно будет давать команду, чтобы он не рандомил до посинения, а, единожды наткнувшись на N+1, прошелся по индексам в поисках ближайшего нераспределенного числа.
#1923805/14
from TalkGadgetA244D1F5, 26 days ago
@wyldrodney:
@torgash Спорим на монетку что ему не нужен массив, а нужны просто рандомные числа несколько раз подряд?)
#1923805/15
from web, 26 days ago, in reply to /14
@torgash:
@wyldrodney не, ну если ему надо забить n-мерный массив строго числами от 1 до n, то ему реально проще забить его числами от 1 до n, а потом чуток переделать алгоритм сортировки и поменять местами два рандомных элемента n или 2n раз, в зависимости от нужной степени разброса
#1923805/16
from TalkGadgetA244D1F5, 26 days ago, in reply to /15
@torgash:
но описанный мной выше вариант существенно упрощает рандому задачу и делает все в один проход
#1923805/17
from TalkGadgetA244D1F5, 26 days ago
@Veresk:
не прально, господа! В общем случае задача выглядит так: есть массив A[N]. Надо получить последовательность M, такую что:

M — случайные.
Все значения M находятся во множестве N.
Если M меньше или равно N, то повторов в последовательности M быть не должно.
Если M больше N, то должно быть задействовано всё множество N, плюс некоторое количество повторов.
#1923805/18
from Psi+, 26 days ago
@wyldrodney:
@Veresk Клавиатуру тебе в жопу и томиком Кнута по ебалу!
#1923805/19
from web, 26 days ago, in reply to /18
@AKa:
сначала заполнить, потом перемешать, не будут повторяться очевидно, а очередной индекс для копирования/перемешивания всегда будет годный, и понадобится всего один проход по массиву для смешивания.
#1923805/20
from iro, 26 days ago
@torgash:
заполнить изначально тоже нужно рандомом, если M<=N. В этом и загвоздка: массив[m] заполнится только числами 1...m и не затронет множество N целиком.
#1923805/21
from TalkGadgetA244D1F5, 26 days ago
@AKa:
@AKa алсо если не нужны повторяющиеся и не особо нужны все числа от 1 до N, то можно в каждом новом к предыдущему прибавлять рандомное
#1923805/22
from iro, 26 days ago, in reply to /20
@AKa:
@AKa а я не помню, в паскалике при рандоме ноль выпадает или нет, вроде выпадает.
#1923805/23
from iro, 26 days ago, in reply to /22
@Veresk:
@AKa выпадает, но есть же n+1 ))
#1923805/24
from Psi+, 26 days ago, in reply to /23
@AKa:
@Veresk угу
#1923805/25
from iro, 26 days ago, in reply to /24
@AKa:
пишем код блять
new(m, len); (вроде так создают, не помню)
for i:=0 to len-1 do m[i]:=i;
randomize;
for i:=0 to len-1 do begin
r:=random(len);
buf:=m[len]
m[len]:=m[i];
m[i]:=buf
end;
#1923805/26
from iro, 26 days ago
@AKa:
@AKa тьфу, не m[len] а m[r]
#1923805/27
from iro, 26 days ago, in reply to /26
@AKa:
@AKa а, и ещё random(len-1)
#1923805/28
from iro, 26 days ago, in reply to /27
@torgash:
для случая m<=n, кстати, можно сделать так: взять массив [n], заполнить его 1...n, перетасовать и взять от него первые m элементов, скопировав их в массив [m]. Профит!
#1923805/29
from TalkGadgetA244D1F5, 26 days ago
@AKa:
@torgash тогда в результате не будет 1..N
#1923805/30
from iro, 26 days ago, in reply to /29
@torgash:
@AKa и не должно быть, поскольку для массива размером меньше чем N достаточно чтобы не было повторов, а весь диапазон N в него не уместить.
#1923805/31
from TalkGadgetA244D1F5, 26 days ago, in reply to /30
@AKa:
@torgash а мне показалось что должно быть строго от 1 но вперемешку
#1923805/32
from iro, 26 days ago, in reply to /31
@Veresk:
нихуя не работает, повторы идут чилел: pastebin.com
#1923805/33
from Psi+, 26 days ago
@AKa:
@Veresk выводи buf
#1923805/34
from iro, 26 days ago, in reply to /33
@Veresk:
@AKa

buf = 1
quest = 6
buf = 2
quest = 5
buf = 3
quest = 10
buf = 4
quest = 2
buf = 4
quest = 7
buf = 1
quest = 7
buf = 4
quest = 6
buf = 8
quest = 3
buf = 9
quest = 4
buf = 8
quest = 8
#1923805/35
from Psi+, 26 days ago, in reply to /34
@AKa:
@AKa а, ну у тебя же выводится значение которое уже перезаписано, то есть существует вероятность что у тебя одно и то же значение будет перемещено два раза. поэтому оно и выводится с повторами.
#1923805/36
from iro, 26 days ago, in reply to /34
@AKa:
@AKa а если вывести массив после данных?
кстати, а random(len)+1 не вылазит за пределы?
#1923805/37
from iro, 26 days ago, in reply to /36
@Veresk:
@AKa всё понял, я мудак
#1923805/38
from Psi+, 26 days ago, in reply to /36
@Veresk:
@AKa нет, он не может вылезти, random(2) выдаёт 0 и 1
#1923805/39
from Psi+, 26 days ago, in reply to /37

Subscribe

Replies (39)

Messages