java - 用于确定其乘积包含所有必需排列的发电机组的有效算法是什么？

Question

考虑以下形式的排列（顺序相关组合）列表：

(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)

假设您要按照以下规则递归地合并这些列，“如果任何两列匹配，我将通过保持这些列的原样进行合并。然后，我将第三列中的两个集合合并生成新的集合。这两行合并后，我把原来的两行去掉，这样就不会重新合并，也不会重复计算。给定上面的置换列表，如果我合并（1234）和（1234），我得到（1234）。现在，如何进行下一次合并以优化发电机组假设我查看（125）并看到它在两列上匹配（123,4），我执行合并并获取（123,4,5）。一切似乎都很好。然而，我然后合并（5 2 3）和（5 2 4），结果是（5 2 3,4）我比较了（5 2 3,4）和（1 2 3,4,5）。我没有两列匹配项，因此停止合并我会把输出减少到（523,4）和（1234,5）。
现在假设我以不同的顺序合并我将（1234）和（1234）合并生成（1234）。然后我合并（523）和（524）产生（523,4）。我看到这两种产品很相配。然后合并（1234）和（534）生成（1234）发电机组的最终清单为（1,5 2 3,4）和（1 2 5）所以你看到合并顺序产生了两个不同的答案：（1,5,2,3,4）和（12,5）对（5,2,3,4）和（12,3,4,5）。
在这种情况下，我可能会满足于任何一个答案，因为相同数量（2）的发电机组列表出现在每个答案。然而，（1,5,2,3,4）和（1,2,5）略为可取，因为（1,5,2,3,4）包含尽可能多的组合。但是，假设我们有一个900个组合的列表。自下而上的问题解决方案的合并顺序将使您以非最优的方式减少问题，其中优化是集合列表中可能的最小计数如果不仔细观察每一条可能的合并路径，很难知道合并顺序是什么，这比我也尝试过的暴力查找匹配的方法效率要低得多。
我也尝试过暴力的方法。为什么暴力方法的效率是不可接受的？该方法首先在所有列中查找唯一整数的列表。然后，它生成这些整数的每个可能组合的幂集。它对column/set a、column/set b和column/set c执行此操作。然后按大小（从大到小）对这些集合进行排序，计算其他列中每个集合的笛卡尔积，然后循环这些笛卡尔积，它们由它们的生成集设置键，以检查笛卡尔积是否与来自输入的置换列表匹配这大约是o（n^3），其中n=输入列表中的组合数。如果我能在o（n^2）中做到这一点，与现在相比将是一场胜利。
至于记忆方面的考虑。假设每个时隙的域是整数1-12三个插槽中不同组合的数目是12！/3个你看到的是超过7900万个原始组合。那是在它们被google的番石榴收集api（我强烈推荐btw）分割成一组之前。我们可能会以某种方式懒洋洋地生成集合，我感觉到Google做了，但是内存限制仍然很大。
我真的在找一个算法来解决这个问题然而，如果有一个Java库或方法可以以最小的痛苦来处理这个问题，我也会支持它。谢谢。

Answer 1

谢谢大家的见解和回答。我想把这个答案归功于John Kolen（http://www.johnfkolen.com），他提出了如下可行的解决方案：
三元最大覆盖的贪心算法
输入：一个三元组的集合，有子集A x B x C，其中A、B和C是
整数集。
输出：一组n个三元组（A_i，B_i，C_i），其中A_i in A，B_i in
b，c中的c_i，以及union_i x b_i x c_i=x和intersection_i x b_i x c_i=empty。
算法
该算法可分为三个部分：查找对覆盖、查找
三重覆盖，最后构造一个总覆盖。
从B x C的子集中寻找成对覆盖涉及从
b到c的集合的元素。基本上是一个小前缀树，或者trie，这个数据
结构使得很容易找到一组前缀的最大覆盖。为了
实例，如果B11-> CY1和BY2-> CY2，则涉及BY1的极大覆盖
b_2将小于[b_1，b_2]，C_1交叉点C_2>。
一旦我们找到最大对，就有可能构造最大值。
三胞胎。然而，这一次，前缀（A）映射到一组对（BxC）。
通过使用前面的方法，可以找到
以及它们在后缀上的匹配对覆盖。
贪婪方法找到局部最优覆盖并将其添加到解中
准备好了当前封面捕捉到的三胞胎被排除在考虑范围之外，
这个过程一直持续到当地最好的封面是单张。这个
剩下的三倍加入溶液中。
附上相关代码。

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);
        }
    }
    }

}