こんにちは、ともです。
競技プログラミングの勉強をしていて、順列の組み合わせを利用するケースがありました。
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;
}
}