約数全列挙

約数を全列挙する方法について、2通り記載しておきます。

① 単純なアルゴリズム

割って0になることを1~Nまで順番に試していきます。

<ソース>

import java.util.ArrayList;
import java.util.List;

/**
 * 約数全列挙
 */
public class yakusu {

    public static void main(String[] args) {

       final int N = 1989;

       List<Integer> yakusu = new ArrayList<Integer>();

       for (int t = 1; t <= N; t++) {
           if (N % t == 0) {
               yakusu.add(t);
           }
       }
       System.out.println(yakusu);
    }
}

<実行結果>

[1, 3, 9, 13, 17, 39, 51, 117, 153, 221, 663, 1989]

②約数の性質を利用して

上記の場合 1989を3で割り切れることが分かれば、1989/3 = 663 と663でも割り切れます。そこで

<ソース>

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 約数全列挙
 */
public class yakusu {

    public static void main(String[] args) {

       final int N = 1989;

       List<Integer> yakusu = new ArrayList<Integer>();

       for (int t = 1; t * t <= N; t++) {
           if (N % t == 0) {
               yakusu.add(t);
               if (t * t != N) {
                   yakusu.add(N / t);
               }
           }
       }
       Collections.sort(yakusu);
       System.out.println(yakusu);
    }
}

こんな風にも書けます。

n!の全列挙(順列)

Javaだと全列挙するメソッドがないらしい。

仕方ないので自作する機会が多いのでn!全列挙を作成しました。

件数が少ない時の最適解など全列挙して全部求めることもあるかな~って思います。

<ソース>

public class Main {

    private static void buildPerm(int[] seed, int[] perm, boolean[] used, int index) {
        if (index == seed.length) {
            System.out.println(java.util.Arrays.toString(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;
        }
    }

    public static void main(String[] args) {
        int[] seed = new int[]{1, 2, 3, 4};
        int[] perm = new int[seed.length];
        boolean[] used = new boolean[seed.length];
        buildPerm(seed, perm, used, 0);

    }
}

<実行結果>

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

bit全探索

ビット全探索とは、二進数とビットを用いて、ある集合の部分集合を全列挙(全探索)する便利なアルゴリズムです。

<ソース>

public class Main {

    // bit全探索
    public static void main(String[] args) {
        String[] 要素 = {"A","B","C", "D"};
        int 要素数 = 要素.length;
        StringBuffer sb = new StringBuffer();

        for (int i=0; i<(Math.pow(2,要素数)); i++) {
            sb.setLength(0);
            for (int j=0; j<要素数; j++) {
                int bit = 1&i>>j;
                System.out.print(bit);

                if (bit == 1) {
                    sb.append(要素[j]);
                }
            }
            System.out.print(" -> ");
            System.out.println(sb.toString());
        }
    }
}

<実行結果>

0000 -> 
1000 -> A
0100 -> B
1100 -> AB
0010 -> C
1010 -> AC
0110 -> BC
1110 -> ABC
0001 -> D
1001 -> AD
0101 -> BD
1101 -> ABD
0011 -> CD
1011 -> ACD
0111 -> BCD
1111 -> ABCD