魔方分割数 in Java DouKaku?

魔方分割数

1 .. N^2までの数をN個の数字の和が等しいN個のグループに分けたいと思います。

たとえば、N=3のときは、
(1) { 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }
(2) { 1, 6, 8 }, { 2, 4, 9 }, { 3, 5, 7 }
の2通りの方法があります。

ここで指定されたNに対して、何通りのグループ分けの方法があるかを数えるプログラムを作ってください。
(何通りかという値だけが出力されればよいのですが、予め計算してある結果を返すのはダメですよ。)
また、N=5を指定したときの実行時間もあわせて教えてください。

なお、数え上げるときの注意として、

・{ 1, 5, 9 } と { 1, 9, 5 }は同じもの

・{ 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }と
　{ 1, 5, 9 }, { 3, 4, 8 }, { 2, 6, 7 }は同じもの
とすることに注意してください。

post comment

Posted feedbacks - Java

Pen4 2.4Gで実行して、

4の場合: 392 : 31(ms)
5の場合: 3245664 : 224157(ms)

と、なりました。簡単に枝狩りをしただけの、総当りです。

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

public class Answer108 {
    private final int size_;
    private final int maxNumber_;
    private final int average_;

    private int count_ = 0;

    public Answer108(int size) {
        size_ = size;
        maxNumber_ = size * size;
        average_ = size * (maxNumber_ + 1) / 2;

        countPair();
    }

    private void countPair() {
        if (size_ <= 1) return;
        List<List<Integer>> array = new ArrayList<List<Integer>>();
        for (int index = 0; index < size_; index++) {
            array.add(new ArrayList<Integer>());
        }
        array.get(0).add(1);
        countPair(array, 2);
    }
    private void countPair(List<List<Integer>> array, int nextNumber) {
        if (nextNumber <= maxNumber_) {
            for (int index = 0; index < size_; index++) {
                List<Integer> list = array.get(index);
                int size = list.size();
                if (size == size_) continue;
                if (size == size_ - 1) {
                    if (sum(list) + nextNumber != average_) continue;
                } else {
                    int rest = 0;
                    for (int lastIndex = 0; lastIndex < size_ - size - 1; lastIndex++) {
                        rest += maxNumber_ - lastIndex;
                    }
                    if (sum(list) + nextNumber + rest < average_) continue;
                }

                if (index >= nextNumber) continue;
                list.add(nextNumber);
                countPair(array, nextNumber + 1);
                list.remove(Integer.valueOf(nextNumber));
                if (list.size() == 0) break;
            }
        } else {
            //System.out.println(toString(array));
            count_++;
        }
    }
    private int sum(List<Integer> array) {
        int sum = 0;
        for (int num: array) {
            sum += num;
        }
        return sum;
    }

    public int getCount() {
        return count_;
    }


    public static String toString(List<List<Integer>> array) {
        String[] strs = new String[array.size()];
        for (int index = 0; index < strs.length; index++) {
            strs[index] = array.get(index).toString();
        }
        return Arrays.toString(strs);
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        Answer108 ans = new Answer108(5);
        System.out.println(ans.getCount());
        long end = System.currentTimeMillis();
        System.out.println("elapse: " + (end - start) + "(ms)");
    }
}

DouKaku?

魔方分割数

Posted feedbacks - Java

Index

Feed

Other

Link

Pathtraq