8

这是我能想到的最好的提问方式，详情如下。我花了一个小时才弄清楚如何提出这个问题！

假设我有 5 种（或更多）类型的文本文件——它们是由科学仪器生成的，每种都有一定的结果。让我们将这些“类型”称为 A、B、C、D、E。文本文件的实际名称并没有透露这一点，因此用户不能轻易地通过名称看到它们是什么。如果它更容易，我们可以考虑一个“字符串”列表。{我不知道如何处理复制类型，但我稍后会担心）

我希望为用户提供将文本文件组合成一个综合文件的选项，但挑战是，组合某些类型没有意义（出于我认为不值得进入的原因）。

我已经构建了兼容性矩阵和示例矩阵

        A   B   C   D   E
   A    1   1   1   1   0
   B    1   1   1   0   0
   C    1   1   1   1   0
   D    1   0   1   1   1
   E    0   0   0   1   1

所以，这就是说我可以将 A 与 B、C、D 结合，但不能将 E（等等）结合起来。

现在，如果用户从文件列表中选择类型为“A、B 和 C”的文件（显然没有输入），我想检查选择并说“是的，ABC 是合法合并”并执行合并。

如果用户选择 A、B、C、D，我想说，不，你不能这样做，因为 D 与 B 不兼容 - 但是，你可以做 A、B、C 或 A、C、D （因为 D 不应该在 B 的位置）。

还在我这儿？

我在代码中创建了上面的矩阵，并进入了一个循环结构，在那里我开始有点糊涂，我想我可能会在发现自己失去家和家人之前寻求一些帮助。关于我如何尝试做出选择，我有一个相当大的评论部分。请记住，“A”可能是“狗”，“B”可能是“猫”等。

internal class CompatibilityCheck
{
    private List<string> FileTypes;

    public CompatibilityCheck()
    {
        //Strings are unique types for text files
        FileTypes = new List<string> {"A", "B", "C", "D", "E"};
        int[,] CompatibilityMatrix =
            {
                {1, 1, 1, 1, 0},
                {1, 1, 1, 0, 0},
                {1, 1, 1, 1, 0},
                {1, 0, 1, 1, 1},
                {0, 0, 0, 1, 1}
            };

        /* Scenario 1 */
        //List of file names from user = ALL LEGAL
        var userSelection = new List<string> {"A", "B", "C"};
        /* Go through each item in userSelection and make arrays of "legal" file combinations?
         * start with A and find the compatible matches, B and C.  Check that B and C are okay. 
        * Answer should look like this as A, B and C can be combined */

        /* Scenario 2 */
        // List of file names from user = NOT ALL LEGAL => D and B are incompatible
        var userSelection2 = new List<string> {"A", "B", "C", "D"};
        /* In my head, I go through each item in userSelction2
         * Take A and build "A,B,C,D" as it is compatible
         *  check B with C(yes) and D(no) - remove D.
         *      end [ A,B,C ]
         *          
         * Start with B and build B,A,C
         *  check A with C(yes) 
         *      end [ B,A,C ]
         *          
         * Start with C and build C,A,B
         *  check A with B(yes)
         *      end [C,A,B]
         *      
         * Start with D and build D,A,C
         *  check A with C(yes)
         *      end [D,A,C]
         *      
         * take the nth string and compare to n+1, n+2 ... n+(length-n)
         *  
         * the unique string sets woudld be  A , B , C and A , C , D  
         */
    }
}

我希望这很清楚。那么完成这样一项任务的最佳方法是什么？递归，LINQ“魔术”，矩阵数学？

[编辑：] 我刚刚想到的一个可能更容易实现的想法可能是显示文件列表，当用户选择它们时，我可以“停用”其他不兼容的选项。想象一个列表框或类似的地方，您选择“A”类型，如果上面的矩阵正在播放，则类型“E”文件将显示为灰色。我想知道这是否会减轻我的压力......？

4

2 回答 2

2

您正在查看一个集团问题- 特别是最大集团问题。

您可以使用一些算法来解决这个问题，但还没有比指数时间更好的算法。

您的编辑听起来像是一个更好的主意-随着您的进行，限制选择应该更容易。

于 2012-10-31T11:46:44.760 回答
2

我没有太多时间看这个或重构我的代码，所以这更像是一个大脑转储，但可能是一个开始并重构为更整洁的东西的好地方！

public class StrongFileType
{
    private string _friendlyName = string.Empty;

    public StrongFileType(string friendlyName)
    {
        _friendlyName = friendlyName;
    }

    public IEnumerable<StrongFileType> CompatibleTypes { get; set; }

    public override string ToString()
    {
        return _friendlyName;
    }
}

private void SampleTest()
{
    // The possible types
    var typeA = new StrongFileType("A");
    var typeB = new StrongFileType("B");
    var typeC = new StrongFileType("C");
    var typeD = new StrongFileType("D");
    var typeE = new StrongFileType("E");

    // Setup possible compatible types
    typeA.CompatibleTypes = new List<StrongFileType> { typeA, typeB, typeC, typeD };
    typeB.CompatibleTypes = new List<StrongFileType> { typeA, typeB, typeC };
    typeC.CompatibleTypes = new List<StrongFileType> { typeA, typeB, typeC, typeD };
    typeD.CompatibleTypes = new List<StrongFileType> { typeA, typeC, typeD, typeE };
    typeE.CompatibleTypes = new List<StrongFileType> { typeD, typeE };

    // Now do a check...
    var userSubmittedFilesValid = new List<StrongFileType> { typeA, typeB, typeC };
    CheckCompatible(userSubmittedFilesValid);
    var userSubmittedFilesInvalid = new List<StrongFileType> { typeA, typeB, typeC, typeD };
    CheckCompatible(userSubmittedFilesInvalid);
}

private bool CheckCompatible(IEnumerable<StrongFileType> requestedFiles)
{
    // Useful for debugging
    var validList = new List<string>();
    var invalidList = new List<string>();

    foreach (StrongFileType fileType in requestedFiles)
    {
        string invalid = string.Empty;
        string validCombination = string.Empty;

        foreach (StrongFileType fileTypeToCheck in requestedFiles)
        {
            if (!fileType.CompatibleTypes.Contains(fileTypeToCheck))
            {
                // Show as not compatible and remove any previously valid combinations that match
                invalid += string.Format("{0} not compatible with {1}", fileType, fileTypeToCheck);
                validList.RemoveAll(x => x.Contains(fileType.ToString()) && x.Contains(fileTypeToCheck.ToString()));
            }
            else
            {
                validCombination += string.Format("{0}", fileTypeToCheck);
            }
        }

        // Add to respective lists
        if (!string.IsNullOrEmpty(validCombination) && !validList.Contains(validCombination))
        {
            validList.Add(validCombination);
        }
        if (!string.IsNullOrEmpty(invalid))
        {
            invalidList.Add(invalid);
        }
    }

    // Was valid?
    return invalidList.Count == 0;
}

这应该导致第一个显示 ABC 的 VALID 列表和 INVALID 列表为空。第二个应该将 ABC 和 ACD 显示为 VALID，将 BD 和 DB 显示为 INVALID。

对不起，我没有更多的时间来整理它！

于 2012-10-31T11:56:14.110 回答