(メモ)順列全探索

はじめに

paizaの問題を解く中で、順列全探索を使う機会があったので考え方をメモしておきます。

今回の問題

ストラックアウトで最大何点取れるか?という問題。
詳細は省きますが、倒す順番によって得点が変わることから、順列全探索ですべての倒す順番を算出する必要がありました。

順列全探索とは

順列全探索は、与えられた要素のすべての順列を列挙する方法です。アルゴリズムとしては、最初に昇順に並べ、次に辞書順で順列を生成し、すべての順列を順番に計算していきます。

処理の流れ

ネットでコードを探したのですが、そのままでは理解が難しかったので設計に落とし込んでみました。

①配列numbersを昇順にする。
②numbersが降順でない場合、以降の処理を行う。
　降順の場合、処理を終了する。
③numbersの後端から順に、隣り合う2要素が昇順になっている箇所を探す。
　2要素の小さい側をiとする。
　numbersが完全に降順の場合、②に戻る。
④numbersの後端から順に、iより大きい要素を探す。
　その要素をjとし、iと交換する。
⑤iより後ろの要素を昇順に並べ替え、②に戻る。

具体的に

numbers = {1,2,3,4,5,6,7,8,9}

ストラックアウトを模した配列です。
要素数は9個、並べ替えパターンは9!通りですね。
順列全探索は、
「昇順から降順にソートする過程において、すべての場合の数を経由する」 ことを利用した処理だと認識していただければと思います。

①配列numbersを昇順にする。
ここがスタートラインです。
今回の場合、すでに昇順なので関係なし。

②numbersが降順でない場合、以降の処理を行う。
　降順の場合、処理を終了する。
書き方がややこしくて申し訳ないですが、今回は③~⑤をメソッドとする前提のため、このような書き方になっています。
①、②は並べ替え後の配列を利用して処理を行うmainメソッドという前提です。
＞降順の場合、処理を終了する。
これは、全ての組み合わせが終わったことを意味しています。
昇順→降順の過程で全ての組み合わせを作り出すので、完全に降順になった時が最後の組み合わせということですね。

③numbersの後端から順に、隣り合う2要素が昇順になっている箇所を探す。
　2要素の小さい側をiとする。
　numbersが完全に降順の場合、②に戻る。
④numbersの後端から順に、iより大きい要素を探す。
　その要素をjとし、iと交換する。
⑤iより後ろの要素を昇順に並べ替え、②に戻る。

ここが切り出した順列全探索メソッドです。
基本的に「こういうもの」として覚えていただければと思います笑
重要なのは⑤の処理です。
この処理によって、単なるソートではなく、全ての組み合わせを作り出すことができるわけです。

おわり

③~⑤の処理について具体的に説明できる方、ぜひコメントをお願いします笑
順列全探索、今後かなり役立ちそうだと感じました!

おまけ

今回挙げた問題の、私の解答コードです。

import java.util.*;

public class Main {
    
        static List<Integer>numberList = new ArrayList<Integer>();
        
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //{1,2,3,4,5,6,7,8,9}
        for(int i = 1; i < 10;i++){
            numberList.add(i);
        }
        
        //各数字を倒した場合の得点
        int[]hitPoint = new int[9];
        for(int i = 0;i < 9;i++){
            hitPoint[i] = sc.nextInt();
        }
        
        //ストラックアウトの状況を示す
        boolean[][]hit = new boolean[3][3];
        
        //倒した数字によって出来たビンゴの数ごとの得点
        int[][]bingoPoint = new int[9][4];
        sc.nextLine();
        for(int i = 0;i < 9;i++){
            String[]input = sc.nextLine().split(" ");
            for(int j = 0; j < input.length;j++){
                bingoPoint[i][j] = Integer.parseInt(input[j]);
            }
        }
        
        //最終得点
        int maxPoint = 0;
        
        //すべての並びに対して処理を行う
        do{
            //初期化処理
            hit = new boolean[3][3];
            
            //ストラックアウト
            int sumPoint = 0;
        for(int i = 0; i < 9;i++){
            //今回の数字
            int tI = numberList.get(i);
            int tJ = numberList.get(i)-1;
            //ヒット処理
            hit[tJ / 3][tJ % 3] = true;
            
            //ビンゴ判定
            int bingoCnt = -1;
            //縦
            boolean yBingo = true;
            for(int j = 0;j < 3;j++){
                if(!hit[j][tJ % 3]){
                    yBingo = false;
                    break;
                }
            }
            if(yBingo){
                bingoCnt++;
            }
            //横
            boolean xBingo = true;
            for(int j = 0;j < 3;j++){
                if(!hit[tJ / 3][j]){
                    xBingo = false;
                    break;
                }
            }
            if(xBingo){
                bingoCnt++;
            }
            //斜め(奇数の場合のみ)
            if(tI % 2 != 0){
                switch(tI){
                    case 1:
                        if(hit[1][1] && hit[2][2]){
                            bingoCnt++;
                        }
                        break;
                    case 3:
                        if(hit[1][1] && hit[2][0]){
                            bingoCnt++;
                        }
                        break;
                    case 5:
                        if(hit[0][0] && hit[2][2]){
                            bingoCnt++;
                        }
                        if(hit[0][2] && hit[2][0]){
                            bingoCnt++;
                        }
                        break;
                    case 7:
                        if(hit[1][1] && hit[0][2]){
                            bingoCnt++;
                        }
                        break;
                    case 9:
                        if(hit[1][1] && hit[0][0]){
                            bingoCnt++;
                        }
                        break;
                }
            }
            //今回ヒットのヒット得点とビンゴ得点を加算
            if(bingoCnt != -1){
                sumPoint += hitPoint[tJ] + bingoPoint[tJ][bingoCnt];
            }else{
                sumPoint += hitPoint[tJ];
            }
        }
            maxPoint = Math.max(maxPoint,sumPoint);
        }while(nextPermutation(numberList));
        
        System.out.println(maxPoint);
    }
    
    //順列全探索用メソッド。
    //完全に降順になった場合、falseを返す。
    public static boolean nextPermutation(List<Integer> numbers){
        int i = numbers.size() - 2;
        while(i >= 0 && numbers.get(i) >= numbers.get(i + 1)){
            i--;
        }
        if(i == -1){
            return false;
        }
        int j = numbers.size() - 1;
        while(numbers.get(j) <= numbers.get(i)){
            j--;
        }
        Collections.swap(numbers, i, j);
        Collections.reverse(numbers.subList(i + 1, numbers.size()));
        return true;
    }
}