0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

Javaで順列(階乗通り・n!通りの列挙・全探索)

Last updated at Posted at 2020-11-23

n!通りを列挙したいときに、
Javaではc++でいうnext_permutationのようなものがないので
自作する必要があります。

実装

import java.util.Arrays;

public class Main {
    private static void permutation(int[] seed) {
        int[] perm = new int[seed.length];
        boolean[] used = new boolean[seed.length];
        buildPerm(seed, perm, used, 0);
    }

    private static void buildPerm(int[] seed, int[] perm, boolean[] used, int index) {
        if (index == seed.length) {
            procPerm(perm);
            return;
        }

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

    private static void procPerm(int[] perm) {
        System.out.println(Arrays.toString(perm));
    }

    public static void main(String[] args) throws Exception {
        permutation(new int[] { 1, 2, 3 });
    }
}

実行結果

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

例題

ABC183C

実装例

import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

    private static long t[][];
    private static int n;
    private static int k;
    private static int ans = 0;

    private static void permutation(int[] seed) {
        int[] perm = new int[seed.length];
        boolean[] used = new boolean[seed.length];
        buildPerm(seed, perm, used, 0);
    }

    private static void buildPerm(int[] seed, int[] perm, boolean[] used, int index) {
        if (index == seed.length) {
            procPerm(perm);
            return;
        }

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

    private static void procPerm(int[] perm) {
        // System.out.println(Arrays.toString(perm));

        // 都市1から出発
        int start = 0;

        // 経路の移動時間の合計
        long sum = 0;

        // 都市1から出発してすべての都市を経由する経路の合計の計算
        for (int i = 0; i < perm.length; i++) {
            sum += t[start][perm[i]];
            start = perm[i];
        }

        // 最後の都市から都市1に戻る経路を合計
        sum += t[start][0];

        // 移動時間=kの場合ans++
        if (sum == k) {
            ans++;
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        k = sc.nextInt();
        t = new long[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                t[i][j] = sc.nextLong();
            }
        }

        // すべての都市をちょうど1度ずつ訪問する順列を生成
        // ex) 4都市の場合(開始終了は都市1固定のため除く)
        // [2, 3, 4], [2, 4, 3]
        // [3, 2, 4], [3, 4, 2]
        // [4, 2, 3], [4, 3, 2]
        permutation(IntStream.range(1, n).toArray());

        System.out.println(ans);

        sc.close();
    }
}

参考

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?