Что-то я не понял сложности вопроса. Ну например на php самый простой способ, это создать массив и n последовательных элементов и потом его перемешать (не совсем понял принцип прохода по вершинам во втором цикле, но предложенный вариант сработает):



На выходе в $arr нужная последовательность.

P.S. на любом другом языке думаю всё ровно так же... на питоне точно... в С++ смотрю есть метод random_shuffle, не знаю то же ли делает, но думаю то же.
В чём сложность то? :)

Aleksandr SharahovПрограмёр,

Я так и сделал сначала, но это не гарантирует,
что полученная будет содержать ровно 1 цикл.
Во втором решении я это учел.

а... ну да... я бы сказал так, может получиться так, что мы получим несколько незамкнутых графов (когда в graph[x] будет записано само значение x)

суть - надо убедиться, что номер каждого элемента не соответствует его значению. Если соответствует - перемешать вручную (ну то есть вызвать random, убедиться, что выпало значение отличное от значения меняемого элемента и поменять местами этот элемент и элемент под выпавшим номером).

Мне что-то показалось что твой вариант по теории вероятности даст неодинаковые вероятности для разных элементов оказаться на некотором месте. Но похоже я ошибся) сижу, считаю

Рэт-нагфикAleksandr SharahovПрограмёр,

Я так и сделал сначала, но это не гарантирует,
что полученная будет содержать ровно 1 цикл.
Во втором решении я это учел.
ну вы блин даете
Как это "не гарантирует"?
Номера вершин: 1, 2, 3, 4, 5
Перемешали: 4, 1, 5, 3, 2
Вот вам и граф с одним циклом: 4 - 1 - 5 - 3 - 2 - 4
Вы уже такую хрень пишете, что прямо не знаю

Рандомное перемешивание не гарантирует, что все элементы окажутся не на своих местах. Потому возможен вариант 4 - 1 - 3 - 2 - 5. В таком случае получается незамкнутый граф (и никакого цикла там не будет). Надо убедиться, что ни одно число не осталось на своём месте. Впрочем я об этом уже написал ))

Рэт-нагфикAleksandr Sharahov,

вот даже не знаю что и сказать.
Есть граф, кольцо из вершин 1-2-3-4-5-1
Берем любую случайную перестановку из пяти чисел 1,2,3,4,5
и получаем "новый" граф, с пятью вершинами, просто пере-называя вершины.
По "форме" это будет новый граф, но по сути, есно, тот же самый.

Что значит "переназываем вершины"? У вершин графа нету названия, есть только номера. В данном случае число, записанное в элементе массива указывает связь между данной вершиной, и той, номер которой записан. То есть graph[2] = 4 - значит, что вторая вершина связана с четвёртой.

а теперь представим, мы запустили алгоритм СЛУЧАЙНОЙ перестановки чисел в массиве, и на выход (вероятность мала, но всё же) получили тот же ряд - 1,2,3,4,5. Это значит, что первая вершина связана с первой (сама с собой), вторая со второй и т.д. В итоге получаем граф без рёбер (то есть ни одна вершина не связана с какой либо другой).


P.S. из слов "переназываем", я понимаю, что ты представляешь себе запись не так как автор. Потому в принципе ты тоже прав. Ты себе представляешь, что первый элемент массива связан со вторым, второй с третьим и т.д. Потому, перераспределив номера в массиве по новой мы получаем граф с теми же параметрами, но с другим списком связей. Автору же нужно, что бы в каждом элементе лежал не его собственный номер, а именно номер той вершины, с которой существует связь (опять же, если в элемента 2 лежит число 4, значит из 2 можно проследовать в 4).