Javaでプリキュア冪集合(DX3)

ネタ Java

お題:

べき集合ということは、各要素について選ぶか／選ばないかの組み合わせを全通り数え上げたものってことで、つまり二分木をトラバースする問題だな。
「『ある金額になるコインの組み合わせ』 に挑戦 - コードの恵み」を真似してTree iteratorで実装してみる。

べき集合のイテレータを戻すクラス

Guava r0.8を使用しています。

import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Set;

import com.google.common.base.Function;
import com.google.common.base.Predicate;
import com.google.common.collect.Iterators;

public final class PowerSetUtils {
    // 状態を表すオブジェクト
    public static class Node<T> {
        // 選択された要素の一覧
        public final Set<T> selected;
        // 未選択の要素の候補の一覧
        public final Set<T> rest;

        public Node(Set<T> selected, Set<T> rest) {
            this.selected = selected;
            this.rest = rest;
        }
    }

    // 途中の状態も含めて全てのノードを戻すイテレータ
    public static class PowerSetIterator<T> implements Iterator<Node<T>> {
        // 状態を保持するスタック
        private final LinkedList<Node<T>> stack = new LinkedList<Node<T>>();

        public PowerSetIterator(Collection<T> values) {
            // 初期状態は、全て未選択
            stack.push(new Node<T>(Collections.<T>emptySet(), new LinkedHashSet<T>(values)));
        }
        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }
    
        @Override
        public Node<T> next() {
            Node<T> node = stack.pop();
            if (!node.rest.isEmpty()) {
                // 未選択の候補を一つ取り出す
                T item = node.rest.iterator().next();
                
                // 選択済み要素に候補を追加したもの
                Set<T> selected = new LinkedHashSet<T>(node.selected);
                selected.add(item);

                // 未選択のリストから候補一つを取り除いた残り
                Set<T> rest = new LinkedHashSet<T>(node.rest);
                rest.remove(item);

                // 状態を追加: 候補を選択しなかった場合
                stack.push(new Node<T>(node.selected, rest));
                // 状態を追加: 候補を選択した場合
                stack.push(new Node<T>(selected, rest));
            }
            return node;
        }
    
        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    // 状態のイテレータから、最終結果のイテレータを生成する。
    public static <T> Iterator<Set<T>> powerSetIterator(Collection<T> values) {
        Iterator<Node<T>> iterator = new PowerSetIterator<T>(values);
        // 条件: 候補を全部使い切っている
        Predicate<Node<T>> predicate = new Predicate<Node<T>>() {
            @Override
            public boolean apply(Node<T> entry) {
                return entry.rest.isEmpty();
            }
        };
        // 結果の抽出: 選択された要素の一覧を取り出す
        Function<Node<T>, Set<T>> tran = new Function<Node<T>, Set<T>>() {
            @Override
            public Set<T> apply(Node<T> entry) {
                return entry.selected;
            }
            
        };
        return Iterators.transform(Iterators.filter(iterator, predicate), tran);
    }
}

実行

DX3で登場するプリキュア一覧

public enum Precure {
    キュアブラック,
    キュアホワイト,
    シャイニールミナス,

    キュアブルーム,
    キュアイーグレット,

    キュアドリーム,
    キュアルージュ,
    キュアレモネード,
    キュアミント,
    キュアアクア,
    ミルキィローズ,

    キュアピーチ,
    キュアベリー,
    キュアパイン,
    キュアパッション,

    キュアブロッサム,
    キュアマリン,
    キュアサンシャイン,
    キュアムーンライト,

    キュアメロディ,
    キュアリズム;
}

各組み合わせを「、」区切りにして出力。StringUtilsはCommons Langのものデス。

    public static void printPowerSetPrecure(PrintStream ps) throws IOException {
        Iterator<Set<Precure>> iterator = powerSetIterator(Arrays.asList(Precure.values()));
        while(iterator.hasNext()) {
            Set<Precure> precures = iterator.next();
            ps.println(StringUtils.join(precures, "、"));
        }
        ps.flush();
    }
    public static void main(String[] args) {
        try {
            printPowerSetPrecure(System.out);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }