c# - 循环 - 处理 2 个未知长度列表的控制流

Question

假设有 2 个未知的字符串列表，可能长度不同。第二个列表中的项目必须与第一个列表中的项目匹配，但匹配可能取决于以下项目的内容:

列表 lst_1:[0] 苹果[1] 橙色[2] 桃子[3] ...

列表 lst_2:[0] 盐[1] 龙舌兰酒[2] 蜂蜜[3] 伏特加[4] 威士忌[5] ...

lst_1 中的项目必须根据几个条件与 lst_2 中的项目匹配。例如，对于每种水果，必须至少有一种酒精；威士忌不能和桃子搭配；任何给定的鸡尾酒等中的酒精含量必须少于 5 种。

如果我将苹果与盐和龙舌兰酒搭配，橙子与蜂蜜和伏特加搭配，我会得到桃子与威士忌，这打破了其中一个条件......但如果我将苹果、龙舌兰酒和蜂蜜放在一起，我会得到橙子-伏特加-威士忌，这是一种有效的饮料。

最重要的是，我需要遍历两个列表，每次检查当前项目的一些条件以及它对列表中的下一项和前一项意味着什么，我可能需要返回多次跟踪并修复问题，直到一切都正确匹配。

我在想一个像这样的大while(bNotReady){...} 循环:

int i = 0;
int j = 0;
string fruit, additive;
bool bContainsAlcohol = false;
dictionary<string, string> dic = new dictionary<string,string>();
while(bNotReady){
  fruit = lst_1[i];
  additive = lst_2[j];
  if (is_valid_match(fruit,additive) && bContainsAlcohol)
  {
     dic.Add(fruit,additive);
     i++; j++;
     continue;
  }
  else if(...)

}

并按照我的方式浏览列表，但我可以看到这很快就会变成一个巨大的、不可读的循环。

是否有更好的方法来计算此任务的控制流？

Answer 1

如果您决定采用约束编程路径，我认为这会是一个更好的主意，但您可以使用蛮力和 .Net 集合来实现。它不会很漂亮，但应该可以。

• 首先，您需要一种方法来将添加剂的所有可能分区枚举到基数等于成分数的集合中。 [a,b,c] 分成三组可以给出 [abc,,] 然后是 [ab,c,] 然后是 [a,bc,]等。
• 枚举所有这些集合你需要枚举这些集合的所有排列
• 最后，对于一组的每个排列，您需要检查成分和添加剂组之间的当前匹配是否满足所有规则

我没有时间创建分区方法，但我有可用的排列扩展，所以我创建了程序的第二步

private static IList<string> Ingredients { get; set; }
private static IList<string> Additives { get; set; }
private static IList<Func<string, string, bool>> Rules { get; set; }

private static void Main(string[] args)
{
    Ingredients = new List<string>() { "Apple", "Orange", "Peach" };
    Additives = new List<string>() { "Vodka", "Rum", "Whiskey" };
    Rules = new List<Func<string, string, bool>>() { (ingredient1, ingredient2) => { return (ingredient1 != "Peach" && ingredient2 != "Whiskey"); } };
    var additivesOrganisationMatchingAllTheRules = FindMatch();
}

private static IList<string> FindMatch()
{
    // here we should enumerate all sets and then enumerate permutation of all the sets
    // instead for the example we just enumerate the permutations
    foreach (var additivesPermutation in Additives.GetCombinations())
    {
        for (int i = 0; i < additivesPermutation.Count; i++)
        {
            var thisSituationIsOk = Rules.All(r => r(Ingredients[i], Additives[i]));
            if (thisSituationIsOk) return additivesPermutation;
        }
    }
    return null;
}

它使用置换方法扩展；据我所知，此扩展程序不保留初始列表。未经测试请勿使用

public static class CombinatorialExtension
{
    public static IEnumerable<IList<TSource>> GetCombinations<TSource>(
        this IList<TSource> source)
    {
        if (source == null)
        {
            throw new ArgumentNullException("source");
        }
        return GetCombinationsImpl<TSource>(source);
    }

    private static IEnumerable<IList<TSource>> GetCombinationsImpl<TSource>(
        this IList<TSource> list)
    {
        return Permutations(list, list.Count);
    }

    private static void ShiftRight<TSource>(IList<TSource> list, int cardinality)
    {
        var lastElement = list[cardinality - 1];
        list.RemoveAt(cardinality - 1);
        list.Insert(0, lastElement);
    }

    private static IEnumerable<IList<TSource>> Permutations<TSource>(IList<TSource> list, int cardinality)
    {
        if (cardinality == 1)
        {
            yield return list;
        }
        else
        {
            for (int i = 0; i < cardinality; i++)
            {
                foreach (var perm in Permutations(list, cardinality - 1))
                    yield return perm;
                ShiftRight(list, cardinality);
            }
        }
    }
}

---

此算法可以让您找到与您拥有的成分和规则相匹配的解决方案，但它不是很漂亮，而且实际上效率不高:许多组合会计算多次。您还必须调整规则以获得令人满意的结果(即添加剂的最小和最大数量等)

---

编辑

甚至可以避免必须创建所有集合，您可以简单地在添加剂中添加与成分减 1 一样多的分隔符。然后只需进行排列并根据分隔符将您的添加剂分成添加剂列表。然后你的规则可以以一种成分和添加剂列表为基础来检查它是否得到遵守。这是一些示例代码

private static IList<string> Ingredients { get; set; }
private static IList<string> Additives { get; set; }
private static IList<Func<string, IList<string>, bool>> Rules { get; set; }

private static void Main(string[] args)
{
    Ingredients = new List<string>() { "Apple", "Orange", "Peach" };
    Additives = new List<string>() { "Vodka", "Rum", "Whiskey" };
    Additives.Add("Separator");
    Additives.Add("Separator"); // add as many separators as the number of ingredients - 1
    Rules = new List<Func<string, IList<string>, bool>>() {
        (ingredient1, ingredient2) => { return (ingredient1 != "Peach" && ingredient2.All(s => s != "Whiskey")); }
        , 
        (ingredient1, ingredient2) => { return ingredient2.Count > 0; }
    };
    var additivesOrganisationMatchingAllTheRules = FindMatch();
}

private static IList<IList<string>> FindMatch()
{
    // separators will create the sets
    foreach (var additivesPermutation in Additives.GetCombinations())
    {
        var Sets = Split(additivesPermutation);
        var thisSituationIsOk = true;
        for (int i = 0; i < Sets.Count && thisSituationIsOk ; i++)
        {
            thisSituationIsOk = thisSituationIsOk && Rules.All(r => r(Ingredients[i], Sets[i]));
        }
        if (thisSituationIsOk) return Sets;
    }
    return null;
}

private static IList<IList<string>> Split(IList<string> values)
{
    var splitValues = new List<IList<String>>();
    var currentList = new List<string>();
    foreach (var value in values)
    {
        if (value == "Separator")
        {
            splitValues.Add(currentList);
            currentList = new List<string>();
        }
        else
        {
            currentList.Add(value);
        }
    }
    splitValues.Add(currentList);
    return splitValues;
}