皆さんの洞察と回答に感謝します。この回答は、実行可能なソリューションを次のように提示したJohn Kolen ( http://www.johnfkolen.com ) の功績によるものです。
トリプルの最大カバレッジのための貪欲なアルゴリズム
入力: A、B、および C が整数のセットである、トリプルのサブセット A x B x C を持つセット。
出力: n 個のトリプル (A_i、B_i、C_i) のセット。A の A_i、B の B_i、C の C_i、および Union_i A_i x B_i x C_i = X および Intersection_i A_i x B_i x C_i = 空。
アルゴリズム
アルゴリズムは 3 つの部分に分けることができます: ペア カバーの検索、トリプル カバーの検索、最後にトータル カバーの作成です。
B x C のサブセットからペアのカバーを見つけるには、B の要素から C のセットへのマップを作成する必要があります。基本的に、このデータ構造は小さなプレフィックス ツリーまたはトライであり、プレフィックスのセットの最大カバーを簡単に見つけることができます。たとえば、b_1->C_1 および b_2->C_2 の場合、b_1 と b_2 を含む最大カバーは <[b_1,b_2],C_1 交差点 C_2> になります。
最大のペアを見つけたら、最大のトリプルを構築することができます。ただし、今回は、プレフィックス (A) が一連のペア (BxC) にマップされます。前の方法を使用すると、A のすべてのサブセットと、接尾辞に対するそれらの一致するペア カバレッジを調べることができます。
貪欲なアプローチは、局所的に最適なカバーを見つけて、それをソリューション セットに追加します。現在のカバーによってキャプチャされたトリプルは考慮から除外され、ローカルで最適なカバーがシングルトンになるまでプロセスが続行されます。残りのトリプルがソリューションに追加されます。
関連するコードが添付されています。
import java.io.IOException;
import java.io.FileReader;
import java.io.BufferedReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;
class Triples {
private ArrayList<int[]> _data;
private HashMap<Integer,HashSet<Integer>> _tree;
/**
* Instantiates a container of triples read from the provided file.
* <p>
* File should contain lines of the form '[#,#,#]', where # is an
* integer. Spaces are ignored.
*
* @param filename a path to a file containing triples
*/
public Triples(String filename) {
_data = new ArrayList<int[]>();
_tree = new HashMap<Integer, HashSet<Integer>>();
readfile(filename);
}
/**
* Returns the number of triples.
*
* @return the number of triples.
*/
int size() {
return _data.size();
}
/**
* Returns a set of encoded pairs (b,c) where (first, b, c) is in the
* set of triples. The pairs are encoded as integers using b * 255 + c.
*
* @param first the first value of a triple
* @return a set of pair encondig
*/
HashSet<Integer> tree(int first) {
return _tree.get(first);
}
public class PairCover
{
public ArrayList<Integer> a;
public ArrayList<Integer> b;
PairCover()
{
a = b = null;
}
PairCover(ArrayList<Integer> ax, ArrayList<Integer> bx)
{
a = ax;
b = bx;
}
/**
* Returns the number of pairs covered by this cover.
*
* @return the number of pairs covered by this cover.
*/
public int score()
{
if (a != null && b != null)
return a.size() * b.size();
else
return 0;
}
public String toString() {
return "<"+a+","+b+">";
}
}
/**
* Compute the maximal pair covering (B,C) for a set of suffix pairs.
*
* @return pair covering where |BxC| is maximized.
*/
public PairCover maxPairCover(HashSet<Integer> set) {
// unpack the pairs
HashMap<Integer,NSet> pairs = new HashMap<Integer,NSet>();
for(Integer value : set) {
Integer a = value / 256;
Integer b = value & 255;
if (!pairs.containsKey(a))
pairs.put(a, new NSet());
pairs.get(a).add(b);
}
_mpc_best = new PairCover();
Integer[] remain_ary = pairs.keySet().toArray(new Integer[0]);
// recursively examine all subsets pair first values and find matching
// second value groups.
maxPairCoverRec(pairs,
new ArrayList<Integer>(),
new ArrayList<Integer>(Arrays.asList(remain_ary)),
null);
return _mpc_best;
}
/**
* Recursively compute the maximal pair covering (B,C) for a set of
* suffix pairs from a set of active prefixes by combining all possible
* subsets of the remaining prefixes.
* <p>
* Stores the best pair cover in _mpc_best. This "global" variable makes it
* easy to prune search.
*
* @param pairs tree-compressed set of pairs
* @param active currently active pair prefixes
* @param remain set of pair prefixes to explore
* @param set the pair suffixes shared by all the active prefixes
* @return pair covering where |BxC| is maximized.
*/
void maxPairCoverRec(HashMap<Integer,NSet> pairs,
ArrayList<Integer> active,
ArrayList<Integer> remain,
NSet set)
{
if (set != null) {
// Prune search if suffix set is empty or that there is no way
// to generate a better pair cover than the current cover.
if (set.isEmpty() ||
(active.size() + remain.size()) * set.size()
<= _mpc_best.score())
return ;
}
if (remain.isEmpty()) {
if (active.size() > 0) {
// Save the current pair cover if it's better than the current
// cover.
if (_mpc_best.score() < set.size() * active.size()) {
_mpc_best.a = (ArrayList<Integer>)(active.clone());
_mpc_best.b = (ArrayList<Integer>)(set.to_array_list());
}
}
return;
}
ArrayList<Integer> active_r = (ArrayList<Integer>)(active.clone());
ArrayList<Integer> remain_r = (ArrayList<Integer>)(remain.clone());
Integer a = remain_r.remove(0);
// Explore active sets without element a.
maxPairCoverRec(pairs, active_r, remain_r, set);
// Explore active sets with element a. Perform intersection of
// current suffix set with suffixes of a.
if (set == null) {
set = pairs.get(a);
}
else {
set = set.intersection(pairs.get(a));
}
active_r.add(a);
maxPairCoverRec(pairs, active_r, remain_r, set);
}
public class TripleCover
{
public ArrayList<Integer> a;
public ArrayList<Integer> b;
public ArrayList<Integer> c;
TripleCover()
{
a = b = c = null;
}
TripleCover(ArrayList<Integer> ax,
ArrayList<Integer> bx,
ArrayList<Integer> cx)
{
a = ax;
b = bx;
c = cx;
}
TripleCover(int ax,
int bx,
int cx)
{
a = new ArrayList<Integer>();
a.add(ax);
b = new ArrayList<Integer>();
b.add(bx);
c = new ArrayList<Integer>();
c.add(cx);
}
/**
* Returns the number of pairs covered by this cover.
*
* @return the number of pairs covered by this cover.
*/
public int score()
{
if (a != null && b != null && c != null)
return a.size() * b.size() * c.size();
else
return 0;
}
public String toString() {
return "<"+a+","+b+","+c+">";
}
}
/**
* Compute the maximal triple cover for the pairs currently stored
* in _tree.
*
* @return a triple cover with |AxBxC| maximized
*/
TripleCover maxTripleCover() {
_mtc_best = new TripleCover();
Integer[] remain_ary = _tree.keySet().toArray(new Integer[0]);
ArrayList<Integer> remain =
new ArrayList<Integer>(Arrays.asList(remain_ary));
maxTripleCoverRec(new ArrayList<Integer>(),
remain,
null);
return _mtc_best;
}
/**
* Recursively explore all subsets of values in first position and
* find the largest cover for the second and third positions.
* <p>
* Stores the best triple cover in _mtc_best. This "global" variable
* makes it easy to prune search.
*
* @param active the active values of the first position
* @param remain the additional values of the first position to explore
* @param set the current set of second/third position pairs that are shared by the active values
*/
void maxTripleCoverRec(ArrayList<Integer> active,
ArrayList<Integer> remain,
HashSet<Integer> set) {
if (set != null &&
(set.isEmpty() ||
(remain.size()>0 &&
(active.size() + remain.size()) * set.size()
<= _mtc_best.score()))){
return;
}
if (remain.isEmpty()) {
if (active.size() > 0) {
PairCover mpc = maxPairCover(set);
if (_mtc_best.score() < mpc.score() * active.size()) {
_mtc_best.a = (ArrayList<Integer>)(active.clone());
_mtc_best.b = mpc.a;
_mtc_best.c = mpc.b;
}
}
return;
}
ArrayList<Integer> active_r = (ArrayList<Integer>)(active.clone());
ArrayList<Integer> remain_r = (ArrayList<Integer>)(remain.clone());
Integer a = remain_r.remove(0);
maxTripleCoverRec(active_r, remain_r, set);
if (set == null) {
set = (HashSet<Integer>)(_tree.get(a).clone());
}
else {
set = (HashSet<Integer>)(set.clone());
set.retainAll(_tree.get(a));
}
active_r.add(a);
maxTripleCoverRec(active_r, remain_r, set);
}
/**
* Finds a covering set for the triples using a greedy approach.
* The largest cover of the current triples is found, recorded, and
* the affected triples are removed from consideration. This process
* continues until singleton covers are left.
*
* @return a list of covers
*/
ArrayList<TripleCover> greedy() {
// Since the prefix tree is modified as new covers are found,
// we make a copy
HashMap<Integer,HashSet<Integer>> old_tree = _tree;
_tree = (HashMap<Integer,HashSet<Integer>>)(_tree.clone());
ArrayList<TripleCover> solution = new ArrayList<TripleCover>();
TripleCover cover;
do {
cover = maxTripleCover(); // find best
solution.add(cover); // record it
remove(cover); // remove covered triples from tree
System.out.println("" + cover + " ==> " + cover.score());
} while (cover.score() > 1);
// Nothing left but singletons, so add them to solution
for(Integer a : _tree.keySet()) {
for(Integer pair : _tree.get(a)) {
int b = pair / 256;
int c = pair & 255;
solution.add(new TripleCover(a,b,c));
}
}
// restore prefix tree
_tree = old_tree;
return solution;
}
//************************************************************
private PairCover _mpc_best;
private TripleCover _mtc_best;
/**
* Reads triples from the specified file. Will exit if file does not
* exist.
*
* @param filename a path to a file containing triples
*/
private void readfile(String filename) {
try {
FileReader fr = new FileReader(filename);
BufferedReader reader = new BufferedReader(fr);
String line = null;
while ((line = reader.readLine()) != null) {
line = line.replace("[","").replace("]","").replace(" ","");
String[] svalues = line.split(",");
int[] values = new int[3];
values[0] = Integer.parseInt(svalues[0]);
values[1] = Integer.parseInt(svalues[1]);
values[2] = Integer.parseInt(svalues[2]);
_data.add(values);
Integer key = new Integer(values[0]);
if (!_tree.containsKey(key)) {
_tree.put(key, new HashSet<Integer>());
}
_tree.get(key).add(values[1] * 256 + values[2]);
}
} catch (IOException e) {
System.out.println("Could not open " + filename);
System.exit(1);
}
}
/**
* Removes covered triples from the prefix tree
*
* @param tc a covering
*/
private void remove(TripleCover tc) {
for(Integer a : tc.a) {
HashSet<Integer> set = _tree.get(a);
for(Integer b : tc.b) {
for(Integer c : tc.c) {
set.remove(b * 256 + c);
}
}
if (set.isEmpty()) {
_tree.remove(a);
}
}
}
}