プログラミング

【Java】配列の順列の作り方のプログラムを理解し、ABC145のCを解く。

 

こんにちは、ともです。

競技プログラミングの勉強をしていて、順列の組み合わせを利用するケースがありました。

C++等には順列の組み合わせを求めるような機能があるようですが、Javaには存在しません。調べるといくつかの記事でJavaで順列の組み合わせを出力するようなコードが紹介されていました。

その実装の考え方が、普段自分がコードを書く際の発想になかったので考え方をメモ。（というか再帰処理が苦手なだけ）

参考にさせていただく記事

順列 (permutation) を作成するというこちらの記事。よく、まくまくJavaノートにはお世話になります。

順列の求める考え方

順列を求めたい配列をseed値として、そこから要素をpermに詰めていく。

例えば、という配列があった場合、その順列というのは

,,,,,

であるが、[index]を決めるという処理を再起処理で求める。そして[index]を何に決めるかというのを管理するiも管理する。

まずは[index]を決めるという実装の骨格を書く。

index==0の場合をまずは考えてみる。順列の[0]が1, 2, 3の場合が一度目のfor文で求まる。index+1することにより、次の再起ではを決めようとする。

3要素分格納したところで再起処理を終える。

public class Permutation {
    public static void main(String... args) {
        int[] seed = new int[]{1, 2, 3};
        int[] param = new int[seed.length];
        create(seed, param, 0);
    }

    private static void create(int[] seed, int[] param, int index) {
        if(index==param.length){
            System.out.println(Arrays.toString(param));
            return;
        }

        for(int i=0; i<seed.length;++i) {
            param[index] = seed[i];
            create(seed, param, index + 1);
        }
    }
}

しかし、上記のコードでは、すでにparamに詰めた値を別のindexに詰めてしまう。そこですでに詰めた要素はどこか管理する配列を用意し、今から詰めようとしている値がすでに格納されているか判定する。

public class Permutation {
    public static void main(String... args) {
        int[] seed = new int[]{1, 2, 3};
        boolean[] used = new boolean;
        int[] param = new int[seed.length];
        create(seed, param, used, 0);
    }

    private static void create(int[] seed, int[] param, boolean[] used, int index) {
        if(index==param.length){
            System.out.println(Arrays.toString(param));
            return;
        }

        for(int i=0; i<seed.length;++i) {
            if(used[i])continue;
            param[index] = seed[i];
            used[i] = true;
            create(seed, param, used,index + 1);
            used[i] = false;
        }
    }
}

usedというboolean[]で詰めが完了しているか管理する。

この順列生成メソッドをもって、ABC145のCを解く。

ABC145のC

総当たりで求まるので、この順列生成メソッドで生成したすべての組み合わせを処理する。

単純に前述のコードをそのまま使っただけなので汚いが、順列生成→総当たりの流れで問題を解くことはできた。

https://atcoder.jp/contests/abc145/submissions/22955168

import java.util.Scanner;

public class Main{
    public static void main(String... args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] xyi = new int[n];

        for(int i=0;i<n;++i) {
            xyi[i][0] = scan.nextInt();
            xyi[i] = scan.nextInt();
        }

        int pattern = 1;
        for(int i=1; i<=n; ++i)pattern*=i;

        boolean[] used = new boolean[n];
        int[][] param = new int[xyi.length];
        System.out.println(create(xyi, param, used, 0)/pattern);
    }

    private static double create(int[][] seed, int[][] param, boolean[] used, int index) {
        if(index==param.length){
            double dis = 0;
            for(int i=0; i<param.length-1;++i) {
                dis += Math.sqrt(Math.pow(param[i][0] - param[i+1][0],2)+Math.pow(param[i]-param[i+1],2));
            }
            return dis;
        }

        double sum = 0;
        for(int i=0; i<seed.length;++i) {
            if(used[i])continue;
            param[index] = seed[i];
            used[i] = true;
            sum += create(seed, param, used,index + 1);
            used[i] = false;
        }
        return sum;
    }
}
関連記事はこちら