(メモ)順列全探索

## はじめに
paizaの問題を解く中で、**順列全探索**を使う機会があったので考え方をメモしておきます。
## 今回の問題
https://paiza.jp/works/mondai/b_rank_new_level_up_problems/b_rank_new_level_up_problems__struck_out

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

## 順列全探索とは

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

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

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

### 具体的に
```java
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より後ろの要素を昇順に並べ替え、②に戻る。**

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

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

### おまけ
今回挙げた問題の、私の解答コードです。
```java
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;
    }
}
```