Генерация случайной моноцикличной перестановки (реализация на C#)

Без рубрики   21 октября 2013  Автор статьи:  

Для генерации случайной моноциклической перестановки необходимо сгенерировать обычную перестановку. Запишем в массив числа от 1 до n, где n — длина перестановки. После этого пробежимся циклом по всем элементам массива и поменяем местами i-ый и случайный элемент местами. Обычная перестановка нужна для того, чтобы цикл в точности повторял ее последовательность. Поэтому первому элементу моноциклической перестановки мы присвоим первый элемент обычный перестановки, а затем пустим цикл, в котором будем расставлять элементы так, чтобы предыдущий элемент указывал на следующий, что в результате и даст нам моноциклическую перестановку.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Случайная_моноциклическа_перестановка
{
class Program
{
public static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static void Main(string[] args)
{
int n = int.Parse(File.ReadAllText("n.txt", Encoding.GetEncoding(1251)));
int[] arr = new int[n];
for (int i = 0; i < n - 1; i++) { arr[i] = i + 1; } Random r = new Random(); for (int i = 0; i < n - 1; i++) { swap(arr, i, r.Next(n - 1)); } arr[n - 1] = 0; int[] ans = new int[n]; ans[0] = arr[0]; for (int i = 1; i < n; i++) { ans[arr[i-1]] = arr[i]; } StringBuilder fullAns = new StringBuilder(); for (int i = 0; i < n; i++) { fullAns.Append((ans[i]+1).ToString() + " "); } File.WriteAllText("ans.txt", fullAns.ToString()); } } }

Научиться программировать

  • на Delphi

  • на Java

  • на C++