考虑以下形式的排列列表(顺序相关组合)：
(1 2 3)
(1 2 4)
(5 2 3)
(5 2 4)
我需要为这个置换群找到最小数量的生成集。例如，给定上面的排列，
(1 2 3,4)
(5 2 3,4)
不是最佳解决方案。最优解为(1,5 2 3,4)。
你会注意到，这个解决方案包含集合A={1，5}B={2}和C={3,4}。原始排列列表是这些集合的有序笛卡尔乘积：A X B X C。
我想将排列列表划分为尽可能少的组，这些组表示为集合A、B和C，其乘积包含列表中的所有排列。最终的答案通常是，但并不总是，集合列表的列表，因为不可能总是将排列列表减少到生成集合的单个列表。也就是说，通常情况下，集合A、B和C的乘积说明了列表中的一些排列，但集合D、E和F需要说明列表中的其他排列，依此类推
我解决这个问题的粗略尝试包括检查列表中两个排列槽中的任何一个是否匹配，并递归地合并它们。如果是这样的话，我合并了这两个组合，即
(1 2 3)
(1 2 4)
产生
(1 2 3,4)
不幸的是，这种组合的合并顺序是不关联的。理想的解决方案是以这样一种方式合并这些组合，即最终的集合列表将包含尽可能多的排列。
为了证明关联性的问题，以这个例子为例，它不能减少到少于两个生成集列表：
(1 2 4)
(1 2 3)
(1 2 5)
(5 2 3)
(5 2 4)
假设你要根据以下规则递归地合并它们，"如果任何两列匹配，我会保留这些列。然后合并第三列中的两个集合，以产生新的集合。合并这两行后，我会丢弃两个原始行，这样它们就不会被重新合并或重复计数。"这些合并的顺序很重要。给定上面的排列列表，如果我合并(1 2 3)和(1 2 4)，我得到(1 2，4)。现在，我该如何进行下一次合并以优化生成集？假设我看(1 2 5)，发现它在两列上匹配(1 2 3，4)，我执行合并并得到(1 2，4，5)。一切似乎都很好。然而，我随后将(5 2 3)和(5 2 4)合并，得到(5 2，4)。我比较了(5 2 3，4)和(1 2 3，5)。我没有两列匹配，所以我停止合并。我会把输出减少到(5 2 3，4)和(1 2 3，4,5)。
现在假设我按照不同的顺序合并。我将(1 2 3)和(1 2 4)合并生成(1 2 3,4)。然后我将(5 2 3)和(5 2 4)合并，生成(5 2，4)。我发现这两种产品很相配。然后，我将(1 2 3，4)和(5 2 3，4-)合并生成(1，5 2 3 4)。发电机组的最终列表是(1,5 2 3,4)和(1 2 5)。因此，您可以看到合并顺序产生了两个不同的答案：(1，5，2，4)和(1，2，5)与(5，2 3，4)以及(1，3，4，5)。
在这种情况下，我可能会选择其中一个答案，因为每个答案中都会出现相同数量(2)的生成集列表。然而，(1，5 2 3，4)和(1 2 5)是稍微优选的，因为(1，50 2，4)包含尽可能多的组合。然而，假设我们有一个900个组合的列表。自下而上的问题解决方案的合并顺序将导致您以非最优的方式减少问题，其中优化是集合列表中可能的最小计数。如果不仔细查看每一条可能的合并路径，很难知道合并顺序是什么，这并不比我也尝试过的强力查找匹配的方法更有效。
我也尝试过暴力的方法。为什么暴力方法的效率是不可接受的？该方法首先查找所有列中唯一整数的列表。然后，它生成这些整数的每一个可能组合的幂集。它对列/集合A、列/集合B和列/集合C执行此操作。然后，它按大小(从大到小)对这些集合进行排序，计算其他列中每个集合与其他集合的笛卡尔乘积，然后循环通过这些笛卡尔乘积，这些笛卡尔积由它们的生成集进行键控，以检查笛卡尔乘积是否与输入中的排列列表匹配。这大约是O(n^3)，其中n=输入列表中的组合数。如果我能在O(n^2)中做到这一点，与现在相比，这将是一场胜利。
就内存方面的考虑而言。让我们假设每个槽的域是整数1-12。三个插槽中不同组合的数量为12/3.你看到了超过7900万个原始组合。那是在谷歌的Guava Collection API(我强烈推荐BTW)将它们划分为集合之前。我们可能会以某种方式懒散地生成集合，我感觉谷歌确实这样做了，但内存限制仍然很大。
我真的在寻找一种算法来解决这个问题。然而，如果有一个Java库或方法可以以最小的痛苦来处理这个问题，我也会支持的。谢谢
感谢大家的真知灼见和回答。我想把这个答案归功于约翰·科伦(http://www.johnfkolen.com)谁提出了一个可行的解决方案如下：
三元组最大覆盖的贪婪算法
输入：三元组的子集为A x B x C的集合，其中A、B和C整数集。
输出：一组n个三元组(A_i，B_i，C_i)，其中A_i在A中，B_i在B、 且Union_i A_i x B_i x C_i＝x且Intersection_i A_i x B_i x C_i=空。
算法
该算法可分为三个部分：查找对覆盖、查找三重覆盖，最后构建一个全覆盖。
从B x C的子集中寻找对的覆盖包括从B的元素到C的集合。本质上是一个小前缀树或trie，这些数据结构使得查找一组前缀的最大覆盖非常容易。对于例如，如果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);
}
}
}
}