Javaで「ある金額になるコインの組み合わせ」

Java

お題:

ある金額になるコインの組み合わせ数とその組み合わせを全て答え下さい。

条件）
・コインの種類は自由に設定できるようにする。
・順序が違うだけのものは一つの組み合わせとする。
　（例：16の組み合わせで、[1, 5, 10]と[10, 5, 1]は同じ）

やってみた。
おかしなコードになっている理由は後ほど。

使い方

イテレータ的なものが返ってくるので、next()で順番に結果を取り出す。

    @Test
    public void testCoinCombinationIterator10() {
        int amount = 10; // 総金額10円

        // コインの種類。 intの配列で重複していないこと
        int[] coins = {1, 5, 10, 50, 100, 500};

        // 金額とコインの種類を指定してCoinCombinationIteratorを生成
        CoinCombinationIterator iterator = new CoinCombinationIterator(amount, coins);

        // 結果をすべて取得
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        while (iterator.hasNext()) {
            List<Integer> aResult = iterator.next();
            results.add(aResult);
        }

        assertEquals("10円を両替る硬貨の組み合わせは4通り", 4, results.size());
        assertEquals("1つ目は[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]", 
                Arrays.asList(1, 1, 1, 1, 1, 1, 1, 1, 1, 1), results.get(0));
        assertEquals("2つ目は[1, 1, 1, 1, 1, 5]", 
                Arrays.asList(1, 1, 1, 1, 1, 5), results.get(1));
        assertEquals("3つ目は[5, 5]", 
                Arrays.asList(5, 5), results.get(2));
        assertEquals("4つ目は[10]", 
                Arrays.asList(10), results.get(3));
    }

特徴

  • それなりに早いと思う。
    • うちのMac miniでも1000円まで両替できるので十分実用的(？)
    • でもぜんぜん高速化の余地アリ(メモ化とか)
  • 外部イテレータになっているので欲しい分だけ取れる。
    • 見つかった順に100個だけ表示とかならすぐ終わる。*1
  • 最大メモリ使用量はあんまり増えない(はず)
    • -Xms16m -Xmx16mでも動く。*2
    • 但し上の例のように結果を溜めると増えて行く。
  • スタックオーバーフローしない(たぶん)
  • 概ねJavaでやる意味があんまり無い

ソースコード

package sample.coinchange;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class CoinCombinations {
    /** 処理の本体。両替の組み合わせを計算する。
        直接再帰呼び出しせずトランポリン用のオブジェクトを戻す。 */
    public static ResultCont combinations(Arg arg) {
        if (arg == null) {
            // 計算終了
            return ResultCont.end();
        } else if (arg.amount == 0) {
            // 結果を一つ返しつつ一つ上の階層の続きに戻る
            return ResultCont.withResult(arg.getPath(), nextArg(arg.parent));
        } else if (arg.coinTypes.isEmpty()) {
            // 上の階層の続きに戻る
            return ResultCont.withoutResult(nextArg(arg.parent));
        } else {
            int coin = arg.coinTypes.value;
            if (arg.amount < coin) {
                // 同階層の次のコインに進む
                return ResultCont.withoutResult(nextArg(arg));
            } else {
                // 下の階層に進む。
                return ResultCont.withoutResult(new Arg(arg.amount - coin, arg.coinTypes, arg));
            }
        }
    }
    // 次にチェックする引数を生成する。
    public static Arg nextArg(Arg arg) {
        if (arg == null) return null;
        return new Arg(arg.amount, arg.coinTypes.next, arg.parent);
    }

    /** 引数をまとめてチェーン可能にしたもの */
    public static class Arg {
        /** 金額 */
        public final int amount;
        /** 使用可能なコインの種類のリスト */
        public final IntList coinTypes;
        /** 一つ上の状態 */
        public final Arg parent;

        public Arg(int amount, IntList coinTypes) {
            this.amount = amount;
            this.coinTypes = coinTypes;
            this.parent = null;
        }
        public Arg(int amount, IntList coinTypes, Arg parent) {
            this.amount = amount;
            this.coinTypes = coinTypes;
            this.parent = parent;
        }
        // Argを遡り、選ばれたコインのリストを取得する
        public List<Integer> getPath() {
            LinkedList<Integer> path = new LinkedList<Integer>();
            for (Arg node = this; node.parent != null; node = node.parent) {
                // 一つ上のcoinTypesの先頭が選ばれたコインのはず
                path.addFirst(node.parent.coinTypes.value);
            }
            return path;
        }
    }

    /** トランポリン用の継続処理。ついでに途中で結果が見つかったときはそれを保持もする。*/
    public static class ResultCont {
        /** 値が見つかった場合は値。無い場合はnull */
        public final List<Integer> result;
        /** 次の処理のための引数 */
        public final Arg arg;
        private ResultCont(List<Integer> result, Arg arg) {
            this.result = result;
            this.arg = arg;
        }
        public final boolean hasResult() {
            return result != null;
        }
        public final List<Integer> result() {
            return result;
        }
        public final boolean hasNext() {
            return arg != null;
        }
        /** 継続処理を呼び出す */
        public final ResultCont next() {
            if (arg == null) {
                throw new IllegalStateException();
            }
            return combinations(arg);
        }
        /** 次の処理が無い場合の継続を生成 */
        public static ResultCont end() {
            return new ResultCont(null, null);
        }
        /** 中間結果ありの継続を生成 */
        public static ResultCont withResult(List<Integer> result, Arg arg) {
            return new ResultCont(result, arg);
        }
        /** 中間結果なしの継続を生成 */
        public static ResultCont withoutResult(Arg arg) {
            return new ResultCont(null, arg);
        }
    }

    /** いわゆるリスト。int専用。 */
    public static class IntList {
        public final int value;
        public final IntList next;
        private IntList(int value, IntList next) {
            this.value = value;
            this.next = next;
        }
        // thisの先頭にvalueを付けたリストを戻す。cons
        public final IntList newList(int value) {
            return new IntList(value, this);
        }
        // intの配列から逆順にしつつIntListを生成
        public static IntList fromArray(int... array) {
            IntList coin = IntList.empty();
            for (int i = array.length - 1; i >= 0; i--) {
                coin = coin.newList(array[i]);
            }
            return coin;
        }
        // 空のリストを表す特別なインスタンス
        private static final IntList EMPTY = new IntList(0, null);
        public static IntList empty() {
            return EMPTY;
        }
        public final boolean isEmpty() {
            return this == EMPTY;
        }
    }

    /** 正しい組み合わせだけを戻すためのラッパークラス */
    public static class CoinCombinationIterator {
        private ResultCont resultCont;
        /**
         * @param amount 送金額
         * @param coinTypes コインの種類。intの配列で重複していないこと
         */
        public CoinCombinationIterator(int amount, int[] coinTypes) {
            Arg arg = new Arg(amount, IntList.fromArray(coinTypes));
            resultCont = combinations(arg);
            if (!resultCont.hasResult()) {
                seek();
            }
        }
        // 次の正しい組み合わせまで進める
        private void seek() {
            while(resultCont.hasNext()) {
                resultCont = resultCont.next();
                if (resultCont.hasResult()) {
                    break;
                }
            }
        }
        public boolean hasNext() {
            return resultCont.hasResult();
        }
        // 正しい組み合わせを一つ戻す
        public List<Integer> next() {
            List<Integer> result = resultCont.result();
            seek();
            return result;
        }
    }
}

説明

思いつく一番シンプルな実装はこんなんだと思う。

    /**
     * @param amount 金額
     * @param coinTypes コインの種類。IntegerのListで重複が無いこと
     */
    public List<List<Integer>> combinations(int amount, List<Integer> coinTypes) {
        List<List<Integer>> results = new LinkedList<List<Integer>>();
        if (amount == 0) {
            results.add(Collections.<Integer>emptyList());
            return results;
        }
        for (int i = 0, c = coinTypes.size(); i < c; i++) {
            Integer coin = coinTypes.get(i);
            if (amount < coin) continue;

            // コインいっこ分差っぴいた金額に対する結果を得る
            List<List<Integer>> subresults = combinations(amount - coin, coinTypes.subList(i, c));
            // 結果の一つ一つの頭にさっきのコインを付けたものを元の金額の結果とする
            for (List<Integer> subresult: subresults) {
                LinkedList<Integer> result = new LinkedList<Integer>(subresult);
                result.addFirst(coin);
                results.add(result);
            }
        }
        return results;
    }

コインを一個選んで、総金額から引いた残りを再帰的に取得する。
取得したら結果の頭に選んだコインを付け足して戻す。
重複が出ないようにsubList()で使う硬貨を限定している。


戻ってきたものの頭にいちいち追加するのは重そうなので、「現在までに選んだコインの一覧」をパラメータで渡して、それを元に結果を生成すればどうだろう？

    public List<List<Integer>> combinations(int amount, List<Integer> types) {
        return _combinations(amount, types, Collections.<Integer>emptyList());
    }
    /**
     * @param amount 金額
     * @param coinTypes コインの種類。IntegerのListで重複が無いこと
     * @param path 現在までに選んだコインの一覧
     */
    public List<List<Integer>> _combinations(int amount, List<Integer> types, List<Integer> path) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        if (amount == 0) {
            results.add(path); // 残金額が0→現在までに選んだコインが正しい組み合わせ
            return results;
        }
        for (int i = 0, c = types.size(); i < c; i++) {
            Integer coin = types.get(i);
            if (amount < coin) continue;

            // コインの列に追加して渡す
            List<Integer> newPath = new ArrayList<Integer>(path);
            newPath.add(coin);

            results.addAll(_combinations(amount - coin, types.subList(i, c), newPath));
        }
        return results;
    }

ループが一つ減って4倍ぐらい早くなる。


再帰を使うのはいいが、これだと10000円ぐらいでスタックオーバーフローしそうだ。
とりあえず末尾再帰の形にしたい。
が、中のループの部分で枝分かれしているのでちょっと難しい。樹状再帰とかいうらしい。
アキュムレータを使うだけではうまくいかない。


引数のスタックを自分で作ってしまえばなんとかなるかも。

    public static class Arg {
        /** 金額 */
        public final int amount;
        /** 使用可能なコインの種類 */
        public final List<Integer> coinTypes;
        /** 現在までに使ったコイン */
        public final List<Integer> path;
        /** 一つ上の状態 */
        public final Arg parent;

        public Arg(int amount, List<Integer> coinTypes, List<Integer> path, Arg parent) {
            this.amount = amount;
            this.coinTypes = coinTypes;
            this.path = path;
            this.parent = parent;
        }
        public String toString() {
            return String.format("{amount=%d, coinTypes=%s, path=%s}", amount, coinTypes, path);
        }
    }

これを使って_combinations()を書き直す。

    public List<List<Integer>> combinations(int amount, List<Integer> types) {
        return _combinations(amount, types, Collections.<Integer>emptyList());
    }
    private static Arg nextArg(Arg arg) {
        if (arg == null) return null;
        return new Arg(
                arg.amount, arg.coinTypes.subList(1, arg.coinTypes.size()),
                arg.path, arg.parent);
    }
    public List<List<Integer>> _combinations(Arg arg, List<List<Integer>> acc) {
        if (arg == null) {
            // finish!
            return acc;
        } else if (arg.amount == 0) {
            // found!
            List<List<Integer>> newAcc = new LinkedList<List<Integer>>(acc);
            newAcc.add(arg.path);
            // up
            return _combinations(nextArg(arg.parent), newAcc);
        } else if (arg.coinTypes.isEmpty()) {
            // up
            return _combinations(nextArg(arg.parent), acc);
        } else {
            Integer coin = arg.coinTypes.get(0);
            if (arg.amount < coin) {
                // next
                return _combinations(nextArg(arg), acc);
            } else {
                // down
                List<Integer> newPath = new LinkedList<Integer>(arg.path);
                newPath.add(coin); 

                return _combinations(
                    new Arg(arg.amount - coin, arg.coinTypes, newPath, arg),
                    acc);
            }
        }
    }

全ての再帰呼び出し部分がreturnの直前になった！
但しJavaの場合勝手に最適化とかしてくれないので、スタックオーバーフロー対策的にはむしろ悪化している。


仕方が無いので自前で再帰呼び出し部分にワンクッション置いてトランポリンする。

    /** トランポリン用の継続処理。*/
    public static class ResultCont {
        /** 次の処理のための引数 */
        public final Arg arg;
        /**　今までの結果を保持 */
        public final List<List<Integer>> acc;

        private ResultCont(Arg arg, List<List<Integer>> acc) {
            this.arg = arg;
            this.acc = acc;
        }
        public final boolean hasNext() {
            return arg != null;
        }
        /** 継続処理を呼び出す */
        public final ResultCont next() {
            if (arg == null) {
                throw new IllegalStateException();
            }
            return _combinations(arg, acc);
        }
        /** 処理終了をあらわすResultContを生成 */
        public static ResultCont end(List<List<Integer>> acc) {
            return new ResultCont(null, acc);
        }
        /** 継続処理をおこなうResultContを生成 */
        public static ResultCont cont(Arg arg, List<List<Integer>> acc) {
            return new ResultCont(arg, acc);
        }
    }
    // 全ての処理が終わるまで呼び直して結果を取得
    public List<List<Integer>> combinations(int amount, List<Integer> coinTypes) {
        Arg arg = new Arg(amount, coinTypes, Collections.<Integer>emptyList(), null);
        ResultCont resultCont = _combinations(arg, Collections.<List<Integer>>emptyList());
        while (resultCont.hasNext()) {
            resultCont = resultCont.next();
        }
        return resultCont.acc;
    }
    private static Arg nextArg(Arg arg) {
        if (arg == null) return null;
        return new Arg(
                arg.amount, arg.coinTypes.subList(1, arg.coinTypes.size()),
                arg.path, arg.parent);
    }
    public static ResultCont _combinations(Arg arg, List<List<Integer>> acc) {
        if (arg == null) {
            // finish!
            return ResultCont.end(acc);
        } else if (arg.amount == 0) {
            // found!
            List<List<Integer>> newAcc = new LinkedList<List<Integer>>(acc);
            newAcc.add(arg.path);
            // up
            return ResultCont.cont(nextArg(arg.parent), newAcc);
        } else if (arg.coinTypes.isEmpty()) {
            // up
            return ResultCont.cont(nextArg(arg.parent), acc);
        } else {
            Integer coin = arg.coinTypes.get(0);
            if (arg.amount < coin) {
                // next
                return ResultCont.cont(nextArg(arg), acc);
            } else {
                // down
                List<Integer> newPath = new LinkedList<Integer>(arg.path);
                newPath.add(coin); 

                return ResultCont.cont(
                    new Arg(arg.amount - coin, arg.coinTypes, newPath, arg),
                    acc);
            }
        }
    }

全ての再帰呼び出し部分で、直接呼び出す代わりにResultContオブジェクトを戻しておき、_combinations()を呼び出した側で呼び直すことでスタックの増加を防止できる。


あとは、ResultContを都度戻すんなら結果をaccに蓄積せずそっちに渡してしまおう、という変更と、パフォーマンス向上のために自前でリストクラス作ってしまおう、という変更を追加して、最初に載せたコードが出来上がる。

今後の課題

ツリー内で計算にかなり重複があるので、メモ化すれば超速くなるのではないかと思う。
別のPathからメモった内容を再利用する方法というかデータ構造がすぐに思いつかないので思いついたら書く。

(追記)やや高速化版

amountが500以下の全ての組み合わせをキャッシュし、結果を再利用するようにした。
メモリを食わない & 大きい数に対しても有効なキャッシュはちょっとムリっぽい。
1000までなら数秒で全ての組み合わせを生成できるけど、10000だと300時間ぐらい掛かりそう。
あまり真似されたくないコード。

package sample.coinchange;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class CoinCombinations {

    private static class CacheUtils {
        private static final int CACHE_LIMIT = 500;
        private static final int ARG_CACHE_SIZE = CACHE_LIMIT * 5;
        // Argのキャッシュ
        private static Map<Arg, Arg> flyweightCache =
            new HashMap<Arg, Arg>(CacheUtils.ARG_CACHE_SIZE, 1.0f);
        // ArgをFlyweight化する
        private static Arg intern(Arg arg) {
            Arg cached = flyweightCache.get(arg);
            if (cached == null) {
                cached = arg;
                flyweightCache.put(cached, cached);
            }
            return cached;
        }
        // amountが500以下のArgをFlyweight化する。
        public static Arg getArg(int amount, IntList coinType) {
            if (amount < CacheUtils.CACHE_LIMIT) {
                return intern(new Arg(amount, coinType));
            } else {
                return new Arg(amount, coinType);
            }
        }

        // 見つかった正しい組み合わせをキャッシュする。
        // ArgLinkを遡って親および同階層の一つ前の状態に正解をセットして行く
        // ((500,[500])の結果は(500,[100,500])にも含まれるはず)
        public static void cacheHit(ArgLink argLink, IntList base) {
            if (argLink.arg.amount > CACHE_LIMIT) {
                return;
            }
            IntList result = base;
            for (ArgLink node = argLink; node != null; node = node.parent) {
                if (node.arg.amount > CACHE_LIMIT) {
                    return;
                }
                result = result.newList(node.arg.coinTypes.value);
                for (ArgLink sister = node; sister != null; sister = sister.sister) {
                    sister.arg.putResult(result);
                }
            }
        }
        // 正しい組み合わせが見つからなかったという結果をキャッシュする
        private static void cacheFailure(ArgLink argLink) {
            if (argLink == null) {
                return;
            }
            if (argLink.arg.amount > CACHE_LIMIT) {
                return;
            }
            argLink.arg.isFailed = true;
        }
        // 成功・失敗問わず、キャッシュされた結果があるかを確認する。
        private static boolean isCached(Arg arg) {
            if (arg.amount > CACHE_LIMIT) return false;
            return arg.isFailed || arg.resultCache != null;
        }
        // キャッシュされた結果が「失敗」かどうかを戻す
        private static boolean isFailed(Arg arg) {
            return arg.isFailed;
        }
        // キャッシュされた正解を戻す
        private static List<IntList> getCached(Arg arg) {
            if (arg.resultCache == null) {
                throw new IllegalStateException("Attempt to get cache for uncached target.");
            }
            return arg.resultCache;
        }
    }

    /** 処理の本体。両替の組み合わせを計算する。直接再帰呼び出しせずトランポリン用のオブジェクトを戻す。 */
    public static ResultCont combinations(ArgLink argLink) {
        if (argLink == null) {
            // 計算終了
            return ResultCont.end();
        } else if (argLink.arg.amount == 0) {
            // 結果を生成
            ResultHolder resultHolder = new ResultHolder(argLink.parent, Arrays.asList(IntList.empty()));
            // 結果をキャッシュに追加
            CacheUtils.cacheHit(argLink.parent, IntList.empty());
            // 結果を一つ返しつつ一つ上の階層の続きに戻る
            return ResultCont.withResults(resultHolder, ArgLink.next(argLink.parent));
        } else if (argLink.arg.coinTypes.isEmpty()) {
            // 上の階層の続きに戻る
            return ResultCont.withoutResult(ArgLink.next(argLink.parent));
        } else {
            // キャッシュを確認
            if (CacheUtils.isCached(argLink.arg)) {
                if (CacheUtils.isFailed(argLink.arg)) {
                    // 失敗したという結果をキャッシュに追加
                    CacheUtils.cacheFailure(argLink.parent);
                    return ResultCont.withoutResult(ArgLink.next(argLink.parent));
                } else {
                    List<IntList> cached = CacheUtils.getCached(argLink.arg);
                    for (IntList result : cached) {
                        // 結果をキャッシュに追加
                        CacheUtils.cacheHit(argLink.parent, result);
                    }
                    ResultHolder results = new ResultHolder(argLink.parent, cached);
                    return ResultCont.withResults(results, ArgLink.next(argLink.parent));
                }
            }
            
            int coin = argLink.arg.coinTypes.value;
            // 同階層の次のコイン
            if (argLink.arg.amount < coin) {
                // 失敗したという結果をキャッシュに追加
                CacheUtils.cacheFailure(argLink);
                // 次のコインにすすむ
                return ResultCont.withoutResult(ArgLink.next(argLink));
            } else {
                // 下の階層に進む。
                return ResultCont.withoutResult(
                    new ArgLink(argLink.arg.amount - coin, argLink.arg.coinTypes, argLink));
            }
        }
    }


    /** 正しい組み合わせだけを戻すためのラッパークラス */
    public static class CoinCombinationIterator {
        private ResultCont resultCont;
        /**
         * @param amount 送金額
         * @param coinTypes コインの種類。intの配列で重複していないこと
         */
        public CoinCombinationIterator(int amount, int[] coinTypes) {
            ArgLink arg = new ArgLink(amount, IntList.fromArray(coinTypes));
            resultCont = combinations(arg);
            if (!resultCont.hasResult()) {
                seek();
            }
        }
        // 次の正しい組み合わせまで進める
        private void seek() {
            while(resultCont.hasNext()) {
                resultCont = resultCont.next();
                if (resultCont.hasResult() && !resultCont.results().isEmpty()) {
                    break;
                }
            }
        }
        public boolean hasNext() {
            return resultCont.hasResult();
        }
        // 正しい組み合わせを一つ戻す。List<Integer>に変換。
        public ResultHolder next() {
            ResultHolder results = resultCont.results();
            seek();
            return results;
        }
    }
    // 正解を一時的に蓄える入れ物。
    public static class ResultHolder {
        private final ArgLink argLink;
        private final List<IntList> branches;
        private ResultHolder(ArgLink arg, List<IntList> branches) {
            if (arg == null || branches == null) {
                throw new IllegalArgumentException("args should not be null.");
            }
            this.argLink = arg;
            this.branches = branches;
        }
        public List<List<Integer>> getResults() {
            List<List<Integer>> results = new ArrayList<List<Integer>>();
            for (IntList branch: branches) {
                LinkedList<Integer> result = branch.toLinkedList();
                for (ArgLink node = argLink; node != null; node = node.parent) {
                    result.addFirst(node.arg.coinTypes.value);
                }
                results.add(result);
            }
            return results;
        }
        public int getCount() {
            return branches.size();
        }
        public boolean isEmpty() {
            return branches.isEmpty();
        }
    }
    /** トランポリン用の継続処理。ついでに途中で結果が見つかったときはそれを保持もする。*/
    public static class ResultCont {
        /** 値が見つかった場合は値。無い場合はnull */
        public final ResultHolder results;
        /** 次の処理のための引数 */
        public final ArgLink arg;
        private ResultCont(ResultHolder results, ArgLink arg) {
            this.arg = arg;
            this.results = results;
        }
        public final boolean hasResult() {
            return results != null;
        }
        public final ResultHolder results() {
            return results;
        }
        public final boolean hasNext() {
            return arg != null;
        }
        /** 継続処理を呼び出す */
        public final ResultCont next() {
            if (arg == null) {
                throw new IllegalStateException();
            }
            return combinations(arg);
        }
        /** 次の処理が無い場合の継続を生成 */
        public static ResultCont end() {
            return new ResultCont(null, null);
        }
        /** 中間結果ありの継続を生成 */
        public static ResultCont withResults(ResultHolder results, ArgLink arg) {
            return new ResultCont(results, arg);
        }
        /** 中間結果なしの継続を生成 */
        public static ResultCont withoutResult(ArgLink arg) {
            return new ResultCont(null, arg);
        }
    }
    /** 引数をまとめたもの。また、結果のキャッシュにも使用する。 */
    public static class Arg {
        /** 金額 */
        public final int amount;
        /** 使用可能なコインの種類のリスト */
        public final IntList coinTypes;
        private Arg(int amount, IntList coinTypes) {
            if (coinTypes == null) {
                throw new IllegalArgumentException("coinTypes should not be null.");
            }
            this.amount = amount;
            this.coinTypes = coinTypes;
        }
        /** ハッシュコード設定済みフラグ */
        private boolean hashCodeSet = false;
        /** ハッシュコード */
        private int hashCode;
        @Override
        public int hashCode() {
            if (!hashCodeSet) {
                final int prime = 31;
                int result = 1;
                result = prime * result + amount;
                result = prime * result
                        + ((coinTypes == null) ? 0 : coinTypes.hashCode());
                hashCode = result;
                hashCodeSet = true;
            }
            return hashCode;
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Arg other = (Arg) obj;
            if (amount != other.amount)
                return false;
            if (coinTypes == null) {
                if (other.coinTypes != null)
                    return false;
            } else if (!coinTypes.equals(other.coinTypes))
                return false;
            return true;
        }

        // 結果のキャッシュを行う。
        /** これ以下で正しい組み合わせが見つからなかった場合にtrueをセットする */
        public boolean isFailed;
        /** これ以下で見つかった正しい組み合わせを蓄積する*/
        public List<IntList> resultCache;
        /** この引数に対する多しい組み合わせを追加する*/
        public void putResult(IntList result) {
            if (resultCache == null) {
                resultCache = new ArrayList<IntList>();
            }
            resultCache.add(result);
        }
    }
    /** 引数をチェーン可能にしたもの。 */
    public static class ArgLink {
        public final Arg arg;
        /** 一つ上の状態 */
        public final ArgLink parent;
        /** 同じ階層の一つ前の状態 */
        public final ArgLink sister;

        public ArgLink(int amount, IntList coinTypes, ArgLink parent, ArgLink sister) {
            arg = CacheUtils.getArg(amount, coinTypes);
            this.parent = parent;
            this.sister = sister;
        }
        public ArgLink(int amount, IntList coinTypes, ArgLink parent) {
            this(amount, coinTypes, parent, null);
        }
        public ArgLink(int amount, IntList coinTypes) {
            this(amount, coinTypes, null, null);
        }

        public static ArgLink next(ArgLink argLink) {
            if (argLink == null) {
                return null;
            } else {
                return new ArgLink(argLink.arg.amount, argLink.arg.coinTypes.next, argLink.parent, argLink);
            }
        }
    }


    /** いわゆるリスト。int専用。 */
    public static class IntList {
        public final int value;
        public final IntList next;
        private IntList(int value, IntList next) {
            this.value = value;
            this.next = next;
        }
        // thisの先頭にvalueを付けたリストを戻す。cons
        public final IntList newList(int value) {
            return new IntList(value, this);
        }
        // 逆順にしつつListを生成
        public LinkedList<Integer> toLinkedList() {
            LinkedList<Integer> mutableList = new LinkedList<Integer>();
            IntList current = this;
            while(!current.isEmpty()) {
                mutableList.addLast(current.value);
                current = current.next;
            }
            return mutableList;
        }
        // intの配列から逆順にしつつIntListを生成
        public static IntList fromArray(int... array) {
            IntList coin = IntList.empty();
            for (int i = array.length - 1; i >= 0; i--) {
                coin = coin.newList(array[i]);
            }
            return coin;
        }
        // 空のリストを表す特別なインスタンス
        private static final IntList EMPTY = new IntList(0, null);
        public static IntList empty() {
            return EMPTY;
        }
        public final boolean isEmpty() {
            return this == EMPTY;
        }

        @Override
        public String toString() {
            return toLinkedList().toString();
        }
        /** ハッシュコード設定済みフラグ */
        private boolean hashCodeSet = false;
        /** ハッシュコード */
        private int hashCode;
        @Override
        public int hashCode() {
            if (!hashCodeSet) {
                final int prime = 31;
                int result = 1;
                result = prime * result + ((next == null) ? 0 : next.hashCode());
                result = prime * result + value;
                hashCode = result;
                hashCodeSet = true;
            }
            return hashCode;
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            IntList other = (IntList) obj;
            if (value != other.value)
                return false;
            if (next == null) {
                if (other.next != null)
                    return false;
            } else if (!next.equals(other.next))
                return false;
            return true;
        }
    }
}

結果は順番にResultHolderというオブジェクトで戻されるので、getResults()でさらに結果を取り出す。

        int amount = 10; // 総金額10円
        int[] coins = {1, 5, 10, 50, 100, 500};

        // 金額とコインの種類を指定してCoinCombinationIteratorを生成
        CoinCombinationIterator iterator = new CoinCombinationIterator(amount, coins);

        // 結果をすべて取得
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        while (iterator.hasNext()) {
            ResultHolder resultHolder = iterator.next();
            results.addAll(resultHolder.getResults());
        }

結果の生成にメモリを食わないようなデータ構造を考えようとしたけど、結果をツリーにすると結局ツリーの探索処理が必要になったりしてあんまり高速にならないし難しい。

*1:http://d.hatena.ne.jp/route150/20110814/1313323411に「入力が10000とかだと総数は何十億もあるけど、見つかった順に１００個だけ表示とかならすぐ終わる」とあって、なにそれ流石Haskellスゲーと思ったけど自分のコードもだった。

*2:http://d.hatena.ne.jp/kmizushima/20110819/1313768331に「-Xms16m -Xmx16mでJVMを実行してもOutOfMemoryErrorは発生しませんでした。」とあって、なにそれ流石Scalaスゲーと思ったけど自分のコードもだった。