整数型の配列をランダムに並べ替える方法

100ます計算の問題を作る、というプログラムを作ってみようと考えています。
問題となる数列は、1から9までの数字をランダムに並べ替えた物になるはずです。

さて、この「ランダムに並べ替えた数字」というのは、どういったアルゴリズムで作成するのが最適なのでしょうか？

個人的に思いついたのは、以下のような方法です。
１．整数型の配列変数(要素が9個)を作成し、それぞれ1から9まで数字を入れておきます。
２．乱数を使って、「x番目とy番目の数字を入れ替え」という風に、何度も入れ替えを行います。

これだと非常に単純なのですが、正直言って素人の考えなので、最適なのかどうか疑問なのです。

もっと最適な方法があれば教えて頂きたいです。

No.7 ベストアンサー 回答者： UKY 回答日時： 2006/09/29 12:03

質問文にある方法でも実用上は問題ないと思いますが、アルゴリズムの理論の上では、「最適」な方法とは言えません。

数列をランダムに並べ替えるアルゴリズムについては、このページが参考になります。
http://ray.sakura.ne.jp/tips/shaffle.html
http://www.hyuki.com/d/200510.html#i20051020190000

この回答へのお礼

ありがとうございます。おかげで完成しそうです。
本当にどうもありがとうございました。

お礼日時：2006/09/30 01:04

No.8 回答者： MrBan 回答日時： 2006/09/29 12:06

> _Boolはその通りですが、_Trueや_Falseというのはありません。

# ご指摘多謝。ISO/IEC9899:1999確認しました。ないですね。
# 独自拡張(の定数マクロ)だったのか…orz

自作する場合は、#6さんの実装例に、実際には多重定義の
ガード追加(__bool_true_false_are_defined)ですね。

No.6 回答者： jacta 回答日時： 2006/09/29 11:42

議論する意図はありませんが、#3の内容に関して...

> > 最新のCだと、bool,true,falseが使えたと思います。
> 最新のC(通称C99)だと、_Bool, _True, _False です。

_Boolはその通りですが、_Trueや_Falseというのはありません。
C99では、bool、true、falseは<stdbool.h>というヘッダで定義されるマクロです。（boolもtypedef名ではなくマクロです）

> とはいえ、未対応のコンパイラ(VCとかbccとか)が多いと思いますが。最新のgccとかなら使えるはず。

これはその通りなのですが、上述の通りヘッダで定義されるマクロですので、<stdbool.h>を自作することで対応してもよいと思います（むしろ、その方が望ましい）。
一応定義例を挙げておきます。

/* <stdbool.h> */
#define bool char
#define true 1
#define false 0
#define __bool_true_false_are_defined 1

No.5 回答者： a-saitoh 回答日時： 2006/09/29 11:38

あなたの発想で正しいです。

ただ、乱数でｘとyを発生させて置き換え漏れを起こさないようにしようとすると、繰り返し回数を多くしないといけないです。
各要素について1回づつ、入れ替えると良いでしょう。つまり、
for(x=1;x<=9;x++) {
　y=乱数発生(１～９）
　swap(x番目とｙ番目)
}
これで、12345678から987654321まで、すべての順列が等確率で発生します。乱数発生も9回ですみます。swapのオーバーヘッドを指摘している人も居ますが、乱数発生の手間を比べれば無視できるものです。

この回答へのお礼

確立を均等にする事は考え付きませんでした。ご指摘ありがとうございます。
無事プログラムは完成しそうです。ありがとうございました。

お礼日時：2006/09/30 01:03

No.4 回答者： dennou2000 回答日時： 2006/09/29 10:43

順番に並んでいない重複のない数列を作るという点では乱数を使うしかないと思います。

基本方針は乱数を発生させて、１～９（１００マスだとすると本来は０～９）の数字の
配列をＸ軸分とＹ軸分作成するという考えでいいと思います。

ただ、
　＞２．乱数を使って、「x番目とy番目の数字を入れ替え」という風に、何度も入れ替え
　＞を行います。
というのは、
1)入れ換えの分のオーバヘッドが大きい(退避変数含めて３回、変数間の移動が発生する）
2)乱数値のシノニム(同値)がでた時、無駄になる。(乱数なので可能性はあります。）
という点で好ましくないかと思います。

わたしの考えたのは、０～９のベースとなる配列から乱数でランダムに取り出して、
Ｘ軸用の数値の配列と、Ｙ軸用の数値の配列に順次設定していくというやり方です。
詳細は、
１）constの０～９の数値の配列を準備する。(配列Ｚ)
２）取り出し済みのフラグの配列を準備する。初期状態：全て未取り出し(配列Ｆ)
３）０～９の範囲を取る乱数を発生させて、その数値番目の配列Ｚ上の要素を
　　Ｘ軸用の数値の配列（配列Ｘ）に順次設定していく。
　　同時に、配列Ｚから取り出した事を示すフラグを配列Ｆに立てる。
４）３）を繰り返す。但し、配列Ｆに取り出し済みフラグが立っていたらリトライする。

結果的にNo.2さんと同じ考え方です。違うのは乱数値をそのまま使ってない事です。

ソースはこんな感じです。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>

#define TRUE 1
#define FALSE 0


int rand0and9(int init){

　　if(init==TRUE) {
　　　　srand((unsigned int)time(0));
　　　　return 0;
　　}
　　else return (int)((10.0 * rand() / (RAND_MAX + 1.0)));
　　// 下位にあるビットは乱数として質が悪い。そのため上位にあるビットを利用する。
}

int main(void)
{
　　const int Base[] = {0,1,2,3,4,5,6,7,8,9,};

　　int take[10];
　　int lines[2][10];
　　int indexLine,indexElement,index;

　　rand0and9(TRUE); // 乱数の初期化
　　for(indexLine=0;indexLine<2;indexLine++) { // ループ２回でＸ軸、Ｙ軸分
　　　　memset(take,0,sizeof(take));
　　　　for(indexElement=0;indexElement<10;indexElement++) { // 一つの軸分
　　　　　　index=rand0and9(FALSE); // 取り出し先を乱数で決定
　　　　　　while(take[index]==TRUE) index=rand0and9(FALSE); //未取出しがあるまでリトライ
　　　　　　lines[indexLine][indexElement] = Base[index];
　　　　　　take[index]=TRUE; // 取出した箇所にフラグを立てる
　　　　}
　　}

　　/* 確認ためのプリント */
　　for(indexLine=0;indexLine<2;indexLine++) {
　　　　printf("%s:　",indexLine==0?"Ｘ軸":"Ｙ軸");
　　　　for(indexElement=0;indexElement<10;indexElement++) {
　　　　　　printf("%d　",lines[indexLine][indexElement]);
　　　　}
　　　　printf("\n");
　　}
}

この回答へのお礼

「乱数の質」って初めて知りました。勉強が足りんです。ありがとうございました。

お礼日時：2006/09/30 01:02

No.3 回答者： MrBan 回答日時： 2006/09/29 10:34

補足。

1～9とかなら#2さんの方法でもいいのですが、
大きな数になる場合は後半で異常に時間がかかるので(既出の数字が出続けることになる)、すべての値が必要なら避けた方がよい。
逆に、いくつかだけ使うなら全部のシャッフルが無駄になるので、
既出チェックが早いかもしれない。(この場合も、
既出チェックを配列に入れると予め全部の容量が必要になるので、
大サイズなら、ビットにするなり、ある程度の単位で動的に確保するなりした方がいいかも)
というトレードオフがあります。

> 最新のCだと、bool,true,falseが使えたと思います。
最新のC(通称C99)だと、_Bool, _True, _False です。
とはいえ、未対応のコンパイラ(VCとかbccとか)が多いと思いますが。最新のgccとかなら使えるはず。
ちなみに、bool,true,falseはC++の予約語でしょう。

No.2 回答者： Trick--o-- 回答日時： 2006/09/29 09:41

・１～９の乱数を発生

・既出ならやり直し
では駄目なのですか？

int x[9],y[9];
BOOL bx[9],by[9];
int i,n;
for(i = 0; i < 9; i++){
　bx[i] = FALSE;
　by[i] = FALSE;
}
i = 0;
while(i < 9)
{
　n = rand()%9;
　if(bx[n] == FALSE) {
　　x[i] = n+1;
　　bx[n] = TRUE;
　　i++;
　}
}
i = 0;
while(i < 9)
{
　n = rand()%9;
　if(by[n] == FALSE) {
　　y[i] = n+1;
　　by[n] = TRUE;
　　i++;
　}
}

BOOL,TRUE,FALSEは環境に応じて変えてください。
最新のCだと、bool,true,falseが使えたと思います。

この回答へのお礼

ありがとうございます。取りあえず自分で作ってみました。
ただ、UKYさんの投稿された記事を最終的に採用させてもらいました。
コードをそのまま書いて頂けると本当に助かります。ありがとうございました。

お礼日時：2006/09/30 01:00

No.1 回答者： MrBan 回答日時： 2006/09/29 08:19

(C++なら)言語標準ライブラリSTLのstd::random_shuffleを使うのが綺麗で簡単。

# 基本的な考え方は、定時のアルゴリズムで十分かと。

この回答への補足

すみません、言語を書き忘れました。
実はCなんです。おそらく、自分で書かないといけないんだろうなと思います。
自分でももう少し調べてみます。

補足日時：2006/09/29 09:01