Помогите придумать охуенный алгоритм перебора пар элементов (в моем случае строки) из списка в случайном порядке.
Парой назовем структуру, имеющую два поля - first и second, при этом при сравнении пар будем считать, что они не упорядочены (1, 2) == (1, 2) и (1, 2) == (2, 1)
Ожидается, что размер списка будет в районе 40000 элементов, что дает нам 799980000 пар n*(n-1) / 2, поэтому хранить все возможные пары не вариант.
Промежуточные результаты могут быть сохранены, а затем загружены для продолжения работы, при этом между сохранением и загрузкой количество элементов списка может меняться.
Пойму на следующем: идея, псевдокод, Python, C#, C++, C
Без нормального ТЗ получается ХЗ. Ты сначала мысли научись грамотно излагать. Я из твоего объяснения нихуя не понял чего тебе надо.
Посмотри в сторону алгоритмов, которые могут генерировать рандомные числа без повторений, мне кажется, такие есть. А дальше ты просто генеришь число от 0 до 799980000 - 1 и берешь соответствующую пару.
Питономакака другого решения пока не видит.
Есть список, например: {1, 2, 3}
Из него нужно выбрать все пары:
(1, 2)
(1, 3)
(2, 3)
Но при этом в случайном порядке, при этом оба элемента должны быть сгенерированы случайным образом, например:
(2, 1)
(2, 3)
(1, 3)
Также, так как пользователь не будет за один присест не переберет пары (в моей задаче от пользователя нельзя избавиться), то перебранные пары каким-то образом нужно сохранять, а затем загружать при следующем старте.
Пока пользователь не пользуется программой, количество элементов, как и сами элементы, может измениться, что также должно учитываться в программе.
Т.е. новые элементы также должны участвовать в переборе, а удаленные, соответственно, нет.
Метод пузырька
Что-то достаточно близкое, но при этом этот алгоритм требует уже готовое конечное множество элементов, в моем случае такими элементами будут сами пары, которые хранить в памяти не желательно
>Пока пользователь не пользуется программой, количество элементов, как и сами элементы, может измениться, что также должно учитываться в программе.
>Т.е. новые элементы также должны участвовать в переборе, а удаленные, соответственно, нет.
какой пользователь, какие элементы, какая блоха, какой заяц.
ты как это блять вообще представляешь?
что такое промежуточные результаты, для продолжения какой работы, тут же нет никакой работы. какой вообще имеет смысл (не в смысле целеполагания, а в смысле семантики) "перебор", у которого поменялись элементы которые он перебирает. что это вообще?
Чел, ну домашку первого курса для ПТУ и сам можешь сделать. Ну слишком изи же. Не позорься.
Не совсем подходит под твоё условие, но:
Если у тебя всё-таки есть ограничение сверху на размер списка N, можешь свести задачу к равновероятной генерации пар i, j: 0 <= i, j < N и i < j.
Если бы не второе условие, можно было бы свести пару i, j к числу i * N + j (то есть генерируешь 0 <= a < N^2, i = a % N, j = a // N).
Как сохранить второе условие, не ебу. Можешь крутить шарманку, пока не выпадут i < j, в среднем долго крутить не придётся.
Если без повторений, генеришь случайную перестановку всех чисел от 0 до N^2, ну ты понел.
а тебе обязательно все C^2_40000 перебирать?
Сорри, у меня в голове насрано
Хотя хуй знает, зачем тебе эти случайные пары, которые ещё и запоминаются, и меняются. Что за алгоритм-то?
Ах да, и еще, ты блять даже количество пар не смог посчитать правильно, ты видимо совсем ебанутый. Сам сказал "порядок важен" но всё-равно делишь на 2.
Пиздец....
По хорошему нужно перебрать все возможные пары, но можно решить и приблизительно, чтобы было перебрано ~80% пар, главное, чтобы не было повторяющихся
Препод сделал покак мне надо это съест
> то перебранные пары каким-то образом нужно сохранять, а затем загружать при следующем старте.
так нужно сохрнаять или нет, ты уж определись
Двойной цикл и всё. Это блять даже не алгоритм
Я ж написал, что при сравнении используем их как не упорядоченные, поэтому все правильно
>Двойной цикл и всё.
Ну да, было бы все так просто, если нужно было бы получить их в строгом порядке, чего мне не нужно.
Ну и напиши блять двойной цикл. Ты ебанутый?
for i=1:N
for j=i+1:N
end
end
Сначала ты пишешь "мне это нужно", потом пишешь "мне это не нужно". Ты видимо даже не в состоянии понять, что от тебя попросил препод... пиздец.
1 из списка случайно выбираешь один элемент
2 сватаешь его с последним элементом
3 перебираешь все варианты
4 повторяешь для массива размера n-1
Это если элементы уникальны. Если неуникальны, то можно подумать в сторону сортировки и затем использование немного модифицированного алгоритма выше
Во-первых,
> for i=1:N
Поссал на лицо N-1
Во-вторых,
Я блять написал, что мне эти пары нужны не в строгом порядке, а в случайном
Иди по циклу в строгом порядке, но записывай в рандомные места,
Нет, не должен
А памяти хватит?
Пиши в рандомную позицию в файле.
Рандомишь лист и циклом перебираешь
Если нужно больше рандома, то рандомишь и индексы. Чтобы они не повторялись можешь их (индексы) куда-нибудь записывать и потом проверку делать на несоответствие.
Эта вся хуйня жирная, но она вроде как в любом случае такой будет
>>238874229
Здесь проблема в том, что пары всегда будут получаться в виде:
(случайный элемент, последний элемент), но мне нужно чтобы оба элемента были случайными
>Поссал на лицо
Ты себе на лицо нассал, ибо нумерацию с первого элемента делал, я же не си-дебил.
>Я блять написал, что мне эти пары нужны не в строгом порядке, а в случайном
У тебя каждому числу от 1 до N(N-1)/2 однозначно соответствует пара элементов, которую по этому номеру легко восстановить(это так просто, что ты сам можешь догадаться как). А дальше просто делаешь циклом rand, уменьшая диапазон рандомных чисел и перебираешь просто числа из ряда.
Берешь range 1,n
Шафлим его. Вроде random.shufle
Сайклимся по списку
For i in random.shuffle(range1, n):
For j in random.shuffle(range1, n):
Print i, j
Рандомный пары будут в смысле равномерного распределения
Единственное диагональные пары офк будут повторятся 1,1 2,2
Массив длинны н решит проблему
Надеюсь понятно
Та же проблема: >>238874486
Я уже пробовал стопицот вариантов разных алгоритмов, которые находил/придумывал, но нихуя не работает, такое ощущение, что это решается только через хранение в памяти
Ты рандомишь два индекса, какая та же самая проблема?
Индексы записывай в файл и проверяй, чтобы не совпадали
что такое "не работает", у тебя же настолько ебанутая задача, что очевидно к ней нет ни одного приемочного теста
Ах да, заметь, то, что я описал тут >>238874491 вообще не требует памяти.
Опа
Пишов нахуй!
Писал с телефона. Разметка поехала.
По скорости ассимптотика квадратичная, по памяти линейная. Укладывается в условия?
Тыт написал т какую-то шизофазию
ОН ВСЕ ДЕЛАЕТ ЗА ТЕБЯ
ЧИЛЛИШ
Нет, давай иначе.
>лабу1
Охуеть лаба рандомно миллион строк пейрить без повторений и без памяти
Бля, ссу себе на лицо, охуенное решение, спасибо анон
Всех тебе благ
Да нет, вполне себе работает. Возьми 4 элемента, и нарисуй на листочке матрицу с парами, убери ненужные (оставишь только верхний треугольник) у тебя будет 6 пар. И внимательно подумай, как из рандомного числа от 1 до 6 однозначно получать какую-нибудь пару из верхнего треугольника.
Это же просто.
а потом еще научиться генерить не повторяющиеся рандомные числа, да?
Все, что будет написано ниже поста, на который этот пост отвечает - хуйня, ОП ушел спатики
А человеку, который подсказал охуенный алгортитм - всего самого пиздатого из того, что он желает в этой жизни
что такое "случайный порядок"?
кто, блядь, так задачу ставит?
Вот они какие програмисты 300к, ни за хуй бабки получают.