Javaで学ぶアルゴリズム 第4弾：ランダムな順列

#Javaで学ぶアルゴリズム < ランダムな順列 >

はじめに

Javaは授業で触れただけで全くの初心者であり，何もわかっていない．なので，基本的なアルゴリズムをJavaで実装し，アルゴリズムの理解を深めるとともに，Javaにも慣れていきたい．
その第4弾としてランダムな順列を扱う．

ランダムな順列

順列とは並びである．ここでは，$1$～$N$までの値をランダムに並べた順列を生成するアルゴリズムについて，最悪のアルゴリズムとそれの改良版を学び，最適な順列生成についての理解を深める．

最悪のアルゴリズム

以下に方法を示す．これは，$N^2$オーダーの繰り返しを行う効率の悪い方法である．ここでは，$1$～$6$の値を例に扱う．

この方法では，範囲内の乱数を得て，リストにないものを取り入れていくという無作為な抽出のような方法であり，上図にも書いているように，無駄な操作が増えることが予想される．

ソースコード

random_permutation1.java

//2020/12/16
//@Yuya Shimizu
//-----------------------------------
//*     ランダムな順列（非効率）    *
//-----------------------------------

import java.awt.*;
import java.awt.event.*;

//パネルの設定
class random_Panel1 extends Panel{
    //乱数生成関数
    int irnd(int n){        //1～nの乱数
        return (int)(Math.random()*n+1);
    }

    //ランダムな順列を生成して表示する関数
    public void paint(Graphics g){
        final int N = 20;   //最大値20
        int[] a = new int[N+1];
        int i,j,flag;

        a[1] = irnd(N); //step1

        //step2
        for (i=2; i<=N; i++){
            do {
                a[i] = irnd(N); //step3
                flag = 0;
                for (j=1; j<i; j++){
                    if (a[i] == a[j]){
                        flag = 1; break;
                    }
                }
            }while (flag==1);
        }

        String s = "";

        for (i=1; i<=N; i++)
            s = s + a[i] + ",";
        g.drawString(s, 10, 20);
    }
}

//フレームの設定
class random_Frame1 extends Frame{
    public random_Frame1(){
        setSize(400, 100);//400×100の大きさでフレームを作成
        //×ボタンを押したら終了
        addWindowListener(new WindowAdapter(){
            public void windowClosing(WindowEvent e){
                System.exit(0);
            }
        });
        Panel p=new random_Panel1();//パネルオブジェクトpに先ほど設定したパネルを指定
        add(p); //フレームにそのパネルを貼り付け
    }
}

//クラス
public class random_permutation1{
    //メイン関数
    public static void main(String[] args){
        Frame w=new random_Frame1();
        w.show();
    }
}

出力

改良版アルゴリズム

以下に方法を示す．これは，$N^2$オーダーを$2N$オーダーにできる効率的に改良された方法である．

この方法であれば，もうすでに取り入れたものは範囲として省かれ，最悪のアルゴリズムのように無駄な操作はなくなると予想される．このことからも改良されていると分かる．

ソースコード

random_permutation2.java

//2020/12/16
//@Yuya Shimizu
//-----------------------------------
//*     ランダムな順列（改良版）    *
//-----------------------------------

import java.awt.*;
import java.awt.event.*;

//パネルの設定
class random_Panel2 extends Panel{
    //乱数生成関数
    int irnd(int n){        //1～nの乱数
        return (int)(Math.random()*n+1);
    }
    //ランダムな順列を生成して表示する関数
    public void paint(Graphics g){
        final int N = 20;   //最大値20
        int[] a = new int[N+1];
        int i,j,d;

        //step1
        for (i=1; i<=N; i++)
            a[i] = i;

        //step2以降
        for (i=N; i>1; i--){
            j = irnd(i-1);
            d = a[i];
            a[i] = a[j];
            a[j] = d;
        }

        String s = "";

        for (i=1; i<=N; i++)
            s = s + a[i] + ",";
        g.drawString(s, 10, 20);
    }
}

//フレームの設定
class random_Frame2 extends Frame{
    public random_Frame2(){
        setSize(400, 100);//400×100の大きさでフレームを作成
        //×ボタンを押したら終了
        addWindowListener(new WindowAdapter(){
            public void windowClosing(WindowEvent e){
                System.exit(0);
            }
        });
        Panel p=new random_Panel2();//パネルオブジェクトpに先ほど設定したパネルを指定
        add(p); //フレームにそのパネルを貼り付け
    }
}

//クラス
public class random_permutation2{
    //メイン関数
    public static void main(String[] args){
        Frame w=new random_Frame2();
        w.show();
    }
}

出力

感想

今回はたった20個のデータを扱うようなプログラムであったため，最悪のアルゴリズムと改良版のアルゴリズムとの違いを体験することはできなかった．しかしながら，最悪となり得るアルゴリズムを学ぶことができたため，順列を生成する際には，この方法を避けることは意識できると思う．

参考文献

Javaによるはじめてのアルゴリズム入門　　河西 朝雄　著　技術評論社