1

セットのリストがあります： 

setlist = [s1,s2,s3...sn]

セットの全方向の比較が必要です。これは、2^n 個のセットです。

setIntersection = [s1 ∩ s2, s1 ∩ s2 ∩ s3, ....., s2 ∩ s3 ∩ s4, ...., sn-1 ∩ sn]

Javaでこれを行う最良の方法は何ですか?

たとえば、5 セットしか使用していなかったとします。5 円のベン図のすべての重なりにデータを入力できるようにしたいと考えています。

私はセットのリストでこれをやろうとしています:

List<Set<People>> lListSets = new ArrayList<Set<People>>();
for (DaysObject day : listOfDaysInJanuary) {
        lListSets.add(day.peopleOneInternet());
}
findPowerSetsAndCompare(lListSets, listOfDaysInJanuary);

次のような結果を見つけたいと思います。

January 1 (Bob, Sally, Tommy)
January 1, January 2 (Sally, Tommy)
...
so on for all possible combination of days.

基本的に私が求めているのは、セットユニオンと組み合わせたパワーセットアルゴリズムを適用する方法です。

4

1 に答える 1

4

Javaでこれを行う最良の方法は何ですか?

あなたが説明している最初の部分はパワーセットです（先週あなたの質問を編集して含めるようにしました）。次に、パワーセット内のセットの各セットの交点を取得します。

整数のような単純なべき乗セットではなく、セットのべき乗セットを実行しているため、実装はもう少し複雑になります。

エクストラクレジット

どのようにそれを行うかの例として、私はあなたの要件の基本的な実装を書きました。この例のすべてのメソッドと型は、Exampleクラスのメンバーです。

main作業コードを示すメソッドのみを含むクラスの例。Dateデモンストレーションに非推奨のコンストラクターを使用することを許していただけると確信しています。

import java.text.*;
import java.util.*;

public class Example
{
    public static void main(String[] args) {
        // create simple test harness
        Set<PeopleByDays> peepsByDay = new HashSet<PeopleByDays>();
        peepsByDay.add(new PeopleByDays(new Date(2015 - 1900, Calendar.JANUARY, 1),
            Person.BOB, Person.FRANK, Person.JIM, Person.JUDY, Person.SALLY));
        peepsByDay.add(new PeopleByDays(new Date(2015 - 1900, Calendar.JANUARY, 2),
            Person.BOB, Person.FRANK, Person.JIM, Person.JUDY, Person.TOMMY));
        peepsByDay.add(new PeopleByDays(new Date(2015 - 1900, Calendar.JANUARY, 3),
            Person.BOB, Person.FRANK, Person.JIM, Person.SALLY, Person.TOMMY));
        peepsByDay.add(new PeopleByDays(new Date(2015 - 1900, Calendar.JANUARY, 4),
            Person.BOB, Person.FRANK, Person.JUDY, Person.SALLY, Person.TOMMY));
        peepsByDay.add(new PeopleByDays(new Date(2015 - 1900, Calendar.JANUARY, 5),
            Person.BOB, Person.JIM, Person.JUDY, Person.SALLY, Person.TOMMY));

        // make powerSet, then intersect, then sort
        Set<Set<PeopleByDays>> powerPeeps = powerSet(peepsByDay);
        List<PeopleByDays> powerPeepsIntersected = intersect(powerPeeps);
        sort(powerPeepsIntersected);

        // print out results
        for (PeopleByDays peeps: powerPeepsIntersected) {
            String daysFormatted = format(peeps.getDays());
            System.out.print(daysFormatted);
            System.out.println(peeps);
        }
    }

    // all other Example members as defined in this answer
}

Personenumは、人の名前の単純な型です。ここで列挙型を使用する利点は、目的の動作に適した実装equals()を処理することです。hashCode()HashSet

    static enum Person {
        BOB, FRANK, JIM, JUDY, SALLY, TOMMY;
    }

PeopleByDaysを拡張して、日を表すオブジェクトHashSet<Person>の追加セットを収集します。DateオーバーライドretainAll()(交差) して日を結合します。オーバーライドequals()しhashSet()、外側のセットで適切に動作するようにします。

    static class PeopleByDays extends HashSet<Person> {
        private final Set<Date> days = new HashSet<Date>();

        public PeopleByDays() {
            super();
        }
        public PeopleByDays(Date day, Person... people) {
            super(Arrays.asList(people));
            this.days.add(day);
        }
        public PeopleByDays(PeopleByDays other) {
            super(other);
            this.days.addAll(other.days);
        }

        public List<Date> getDays() {
            return new ArrayList<Date>(this.days);
        }

        @Override
        public boolean retainAll(Collection<?> c) {
            if (c instanceof PeopleByDays) {
                this.days.addAll(((PeopleByDays)c).days);
            }
            return super.retainAll(c);
        }

        @Override
        public boolean equals(Object o) {
            return super.equals(o) && this.days.equals(((PeopleByDays) o).days);
        }
        @Override
        public int hashCode() {
            return super.hashCode() + this.days.hashCode();
        }
    }

powerSet()メソッド、この回答から逐語的に取られました。

    public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
        Set<Set<T>> sets = new HashSet<Set<T>>();
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<T>());
            return sets;
        }
        List<T> list = new ArrayList<T>(originalSet);
        T head = list.get(0);
        Set<T> rest = new HashSet<T>(list.subList(1, list.size()));
        for (Set<T> set: powerSet(rest)) {
            Set<T> newSet = new HashSet<T>();
            newSet.add(head);
            newSet.addAll(set);
            sets.add(newSet);
            sets.add(set);
        }
        return sets;
    }

intersect()メソッドを使用して、パワーセット内のセットの各セットの交差を作成します。

    static List<PeopleByDays> intersect(Set<Set<PeopleByDays>> powerSet) {
        List<PeopleByDays> intersected = new ArrayList<PeopleByDays>();
        for (Set<PeopleByDays> powerElement: powerSet) {
            PeopleByDays intersection = null;
            if (powerElement.isEmpty()) {
                intersection = new PeopleByDays();
            } else for (PeopleByDays peeps: powerElement) {
                if (intersection == null) {
                    intersection = new PeopleByDays(peeps);
                } else {
                    intersection.retainAll(peeps);
                }
            }
            intersected.add(intersection);
        }
        return intersected;
    }

結果の交差セットを日付でソートするsort()メソッド。

    static void sort(List<PeopleByDays> peeps) {
        Collections.sort(peeps, new Comparator<PeopleByDays>() {
            @Override
            public int compare(PeopleByDays p1, PeopleByDays p2) {
                List<Date> days1 = p1.getDays();
                List<Date> days2 = p2.getDays();
                Collections.sort(days1);
                Collections.sort(days2);
                for (int i = 0; i < days1.size() && i < days2.size(); i++) {
                    int compare = days1.get(i).compareTo(days2.get(i));
                    if (compare != 0) {
                        return compare;
                    }
                }
                return days1.size() - days2.size();
            }
        });
    }

format()メソッドを使用して、交差点ごとの日のリストをフォーマットします。

    static String format(List<Date> days) {
        if (days.isEmpty()) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        DateFormat format = new SimpleDateFormat("MMM d");
        Collections.sort(days);
        String separator = "";
        for (Date day: days) {
            sb.append(separator);
            sb.append(format.format(day));
            separator = ", ";
        }
        sb.append(" ");
        return sb.toString();
    }

そして最後にアウトプットです。

[]
Jan 1 [BOB, JUDY, FRANK, JIM, SALLY]
Jan 1, Jan 2 [BOB, JUDY, FRANK, JIM]
Jan 1, Jan 2, Jan 3 [BOB, FRANK, JIM]
Jan 1, Jan 2, Jan 3, Jan 4 [BOB, FRANK]
Jan 1, Jan 2, Jan 3, Jan 4, Jan 5 [BOB]
Jan 1, Jan 2, Jan 3, Jan 5 [BOB, JIM]
Jan 1, Jan 2, Jan 4 [BOB, JUDY, FRANK]
Jan 1, Jan 2, Jan 4, Jan 5 [BOB, JUDY]
Jan 1, Jan 2, Jan 5 [BOB, JUDY, JIM]
Jan 1, Jan 3 [BOB, FRANK, JIM, SALLY]
Jan 1, Jan 3, Jan 4 [BOB, FRANK, SALLY]
Jan 1, Jan 3, Jan 4, Jan 5 [BOB, SALLY]
Jan 1, Jan 3, Jan 5 [BOB, JIM, SALLY]
Jan 1, Jan 4 [BOB, JUDY, FRANK, SALLY]
Jan 1, Jan 4, Jan 5 [BOB, JUDY, SALLY]
Jan 1, Jan 5 [BOB, JUDY, JIM, SALLY]
Jan 2 [BOB, JUDY, TOMMY, FRANK, JIM]
Jan 2, Jan 3 [BOB, TOMMY, FRANK, JIM]
Jan 2, Jan 3, Jan 4 [BOB, TOMMY, FRANK]
Jan 2, Jan 3, Jan 4, Jan 5 [BOB, TOMMY]
Jan 2, Jan 3, Jan 5 [BOB, TOMMY, JIM]
Jan 2, Jan 4 [BOB, JUDY, TOMMY, FRANK]
Jan 2, Jan 4, Jan 5 [BOB, JUDY, TOMMY]
Jan 2, Jan 5 [BOB, JUDY, TOMMY, JIM]
Jan 3 [BOB, TOMMY, FRANK, JIM, SALLY]
Jan 3, Jan 4 [BOB, TOMMY, FRANK, SALLY]
Jan 3, Jan 4, Jan 5 [BOB, TOMMY, SALLY]
Jan 3, Jan 5 [BOB, TOMMY, JIM, SALLY]
Jan 4 [BOB, JUDY, TOMMY, FRANK, SALLY]
Jan 4, Jan 5 [BOB, JUDY, TOMMY, SALLY]
Jan 5 [BOB, JUDY, TOMMY, JIM, SALLY]

それが役立つことを願っています。意図したよりもずっと長くいじくり回しました ;) それでも、出力内の Person 名はソートされませんでした。

于 2015-01-29T01:54:37.320 に答える