Home > Algorithm > Sinh hoán vị ngẫu nhiên

Sinh hoán vị ngẫu nhiên

1. Đặt bài toán

Sinh ngẫu nhiên cho mảng nguyên a một hoán vị của 1..n

2. Thuật toán

– Xuất phát từ hoán vị đơn vị a = (1,2,…,n), thực hiện đổi chỗ a[0] với một phần tử a[j], trong đó j = random(n)

– Có thể lặp lại thao tác trên nhiều lần để tăng sự xáo trộn ngẫu nhiên

3. Code C# :

/// <summary>
 /// Sinh hoán vị đều
 /// </summary>
 /// <param name="n">Số phần tử cần sinh</param>
 /// <returns>Mảng n số nguyên là một hoán vị của 1..n</returns>
 public static int[] GenRandomPermutation(int n)
 {
    Random r = new Random();
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
    {
       a[i] = i + 1;
    }
    for (int i = 0; i < n; i++)
    {
       int j = r.Next(n);
       int t = a[0];
       a[0] = a[j];
       a[j] = t;
    }
    return a;
 }
Advertisements
Categories: Algorithm
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: