【第6回】数学問題：順列を作る

問題
ヒント
答え

問題

｛1,2,3,4｝の数値配列の全ての組み合わせの順列を作成するプログラムを作りなさい。

答えはこちら

ヒント

ヒント１：順列とは

順列は、『異なるn個のものからr個選んで「一列に並べる」』場合の数のことをいいます。

今回は1.2.3.4なので、
4個のものから４個選んで全ての組み合わせパターンの一列を作るということです。

ヒント２：全ての組み合わせパターン

全ての組み合わせパターンは４の階乗で求められます。

４X３X２X１　＝　24通りです。

ヒント３：ロジックの考え方

①｛1.2.3.4｝を格納する配列の変数を用意すること
②既に配列のi番目の要素に対して値を詰めたか、
詰めていないかを判定する真偽値の①と同じ長さの配列を用意すること

③if分岐：１行分の順列を作成できていない場合
for文：配列の長さ分処理を繰り返す
if分岐：配列i番目の要素がまだ値を詰められていない場合
①の配列変数にi番目の数値を代入する
配列i番目をfalse（値を詰めた）にする
i+1番目の配列要素に対して順列作成メソッドを行う（③からの処理を行う）
配列i番目のtrue（値を詰めていない）に戻す
③else：１行分の順列を作成した場合
その１行分の順列をコンソール表示する

答えはこちら

答え

package javalogic;

public class JavaLogic6 {


    public static void main(String[] args) {
        int n = 4;	// n個の文字の中で
        int r = 4;	// r個を選んで組み合わせ
        int[] arr = {1, 2, 3, 4};
        int[] output = new int[n];				// 順列を保存する配列
        boolean[] visited = new boolean[n];		//重複した値を選ばないためにチェックする値

        //順列の個数
        int count = 1;
        //もし4つの数字を組み合わせるとしたら可能な個数は'４＊３＊２＊１'だから4から1まで全部掛ける。
        for(int i=arr.length; i>0; i--) count = count * i;
        System.out.println("count: "+count);
        System.out.println("==============");
        
        perm(arr, output, visited, 0, n, r);
    }

    static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
    	//depthは数字が入る欄の番号
    	//depthが４なら全ての数字が入っているのだから、出力してリターン
    	if (depth == r) {
            print(output);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visited[i] != true) {		//空いている欄はflaseなのでif文を実行して
                visited[i] = true;			//if文を一度実行したらtrueに変える
                output[depth] = arr[i];		//output配列に値を入れる
                perm(arr, output, visited, depth + 1, n, r);	//depthを1個ずつ増やしながら繰り返し
                visited[i] = false;			//リターンされる前に溜まっている直近の関数のi値をfalseに変える
            }
        }
    }

    // 配列を出力
    static void print(int[] arr) {
    	for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
    	}
        System.out.println();
    }
}

package javalogic;

public class JavaLogic6 {

public static void main(String[] args) {

int n = 4; // n個の文字の中で

int r = 4; // r個を選んで組み合わせ

int[] arr = {1, 2, 3, 4};

int[] output = new int[n]; // 順列を保存する配列

boolean[] visited = new boolean[n]; //重複した値を選ばないためにチェックする値

//順列の個数

int count = 1;

//もし4つの数字を組み合わせるとしたら可能な個数は'４＊３＊２＊１'だから4から1まで全部掛ける。

for(int i=arr.length; i>0; i--) count = count * i;

System.out.println("count: "+count);

System.out.println("==============");

perm(arr, output, visited, 0, n, r);

}

static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {

//depthは数字が入る欄の番号

//depthが４なら全ての数字が入っているのだから、出力してリターン

if (depth == r) {

print(output);

return;

}

for (int i = 0; i < n; i++) {

if (visited[i] != true) { //空いている欄はflaseなのでif文を実行して

visited[i] = true; //if文を一度実行したらtrueに変える

output[depth] = arr[i]; //output配列に値を入れる

perm(arr, output, visited, depth + 1, n, r); //depthを1個ずつ増やしながら繰り返し

visited[i] = false; //リターンされる前に溜まっている直近の関数のi値をfalseに変える

}

// 配列を出力

static void print(int[] arr) {

for (int i = 0; i < arr.length; i++) {

System.out.print(arr[i] + " ");

}

System.out.println();

}