【C言語】重複しない乱数の生成方法

2023年9月13日

この記事では、C言語で重複しない乱数を生成する方法とその応用例について解説します。

目次から探す

重複しない乱数の生成アルゴリズム

乱数を生成する際、重複しない乱数を生成する方法があります。

以下では、いくつかのアルゴリズムを紹介します。

フィッシャー・イェーツのシャッフルアルゴリズム

フィッシャー・イェーツのシャッフルアルゴリズムは、配列の要素をランダムに並び替えるアルゴリズムです。

以下にサンプルコードを示します。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void shuffle(int arr[], int n) {
    srand(time(NULL));
    for (int i = n - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    shuffle(arr, n);
    printf("シャッフル後の配列: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

上記のコードでは、shuffle関数を使って配列の要素をシャッフルしています。

srand関数を使って乱数のシードを設定し、rand関数を使って乱数を生成しています。

ビットマップ法

ビットマップ法は、乱数の値をビットマップとして扱い、生成済みの乱数を管理する方法です。

以下にサンプルコードを示します。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_NUM 100
int main() {
    int bitmap[MAX_NUM] = {0};
    int n = 10; // 生成する乱数の個数
    srand(time(NULL));
    printf("生成された乱数: ");
    for (int i = 0; i < n; i++) {
        int num = rand() % MAX_NUM;
        while (bitmap[num] == 1) {
            num = rand() % MAX_NUM;
        }
        bitmap[num] = 1;
        printf("%d ", num);
    }
    printf("\n");
    return 0;
}

上記のコードでは、bitmap配列を使って生成済みの乱数を管理しています。

rand関数を使って乱数を生成し、生成済みの乱数であるかをbitmap配列で確認しています。

リスト法

リスト法は、生成済みの乱数をリストで管理する方法です。

以下にサンプルコードを示します。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct Node {
    int data;
    struct Node* next;
} Node;
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
void insertNode(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}
int main() {
    Node* head = NULL;
    int n = 10; // 生成する乱数の個数
    srand(time(NULL));
    printf("生成された乱数: ");
    while (n > 0) {
        int num = rand() % 100;
        Node* temp = head;
        int isDuplicate = 0;
        while (temp != NULL) {
            if (temp->data == num) {
                isDuplicate = 1;
                break;
            }
            temp = temp->next;
        }
        if (!isDuplicate) {
            insertNode(&head, num);
            printf("%d ", num);
            n--;
        }
    }
    printf("\n");
    return 0;
}

上記のコードでは、リストを使って生成済みの乱数を管理しています。

insertNode関数を使ってリストに乱数を追加し、重複していないかを確認しています。

次のページ重複しない乱数の生成の応用例