如何从List中获得所有可能的字符串组合

本文关键字：有可能 组合 字符串 List string | 更新日期: 2023-09-27 18:10:58

我正在做一个类似标记的字符串匹配函数，其中函数检查字符串是否包含任何可能的单词，同时保持它们的顺序，至少每个标记。我发现最好是预先创建一个可能性列表，然后检查一下字符串是否包含每个所需的组合

也许代码会使它更清楚。

List<List<string[]>> tags;
List<string[]> innerList;
List<List<string>> combinationsList;
public void Generate(string pattern)
{
    // i will add whitespace removal later so it can be ", " instead of only ","
    foreach (string tag in pattern.Split(','))
    {
        innerList = new List<string[]>();
        foreach (var varyword in tag.Split(' '))
        {
            innerList.Add(varyword.Split('|'));
        }
    }
    // atm i lack code to generate combinations in form of List<List<string>> 
    // and drop them into 'combinationsList'
}
// the check function will look something like isMatch = :
public bool IsMatch(string textToTest)
{
    return combinationsList.All(tc => tc.Any(c => textToTest.Contains(c)));
}

例如pattern:

"老|小约翰|鲍勃,| |拥有狗猫"

  • 标签:
    • List_1:
      • {老,年轻}
      • {约翰,鲍勃}
    • List_2
      • {,拥有}
      • {狗、猫}

所以组合列表将有:

  • combinationsList:
    • List_1
        "老约翰"
      • "老鲍勃"
      • "年轻的约翰"
      • "年轻bob"
    • List_2
      • "狗"
      • "猫"
      • "拥有狗"
      • "拥有猫"

所以结果将是:

  • old bob have cat = true，包含List_1:"old bob"和List_2:"have cat"
  • young john有car = false，包含List_1:"young john"但不包含任何List_2的组合

我不知道如何迭代集合来获得这些组合，以及如何每次迭代获得组合。另外，我不能把订单弄乱，这样old john就不会被生成为john old。

请注意，模式中的任何"变体词"都可能有2个以上的变体，例如"dog|cat|mouse"

如何从List<string[]>中获得所有可能的字符串组合

这段代码可能会有帮助

string pattern = "old|young john|bob have|posses dog|cat";
var lists = pattern.Split(' ').Select(p => p.Split('|'));
foreach (var line in CartesianProduct(lists))
{
    Console.WriteLine(String.Join(" ",line));
}

//http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx
static IEnumerable<IEnumerable<T>> CartesianProduct<T>(IEnumerable<IEnumerable<T>> sequences)
{
    // base case:
    IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() };
    foreach (var sequence in sequences)
    {
        var s = sequence; // don't close over the loop variable
        // recursive case: use SelectMany to build the new product out of the old one
        result =
            from seq in result
            from item in s
            select seq.Concat(new[] { item });
    }
    return result;
}

我在另一个帖子里找到了答案。

https://stackoverflow.com/a/11110641/1156272

Adam发布的代码完美无瑕，完全符合我的需求

        foreach (var tag in pattern.Split(','))
        {
            string tg = tag;
            while (tg.StartsWith(" ")) tg = tg.Remove(0,1);
            innerList = new List<List<string>>();
            foreach (var varyword in tg.Split(' '))
            {
                innerList.Add(varyword.Split('|').ToList<string>());
            }
            //Adam's code
            List<String> combinations = new List<String>();
            int n = innerList.Count;
            int[] counter = new int[n];
            int[] max = new int[n];
            int combinationsCount = 1;
            for (int i = 0; i < n; i++)
            {
                max[i] = innerList[i].Count;
                combinationsCount *= max[i];
            }
            int nMinus1 = n - 1;
            for (int j = combinationsCount; j > 0; j--)
            {
                StringBuilder builder = new StringBuilder();
                for (int i = 0; i < n; i++)
                {
                    builder.Append(innerList[i][counter[i]]);
                    if (i < n - 1) builder.Append(" "); //my addition to insert whitespace between words
                }
                combinations.Add(builder.ToString());
                counter[nMinus1]++;
                for (int i = nMinus1; i >= 0; i--)
                {
                    // overflow check
                    if (counter[i] == max[i])
                    {
                        if (i > 0)
                        {
                            // carry to the left
                            counter[i] = 0;
                            counter[i - 1]++;
                        }
                    }
                }
            }
            //end
            if(combinations.Count > 0)
                combinationsList.Add(combinations);
        }
    }
    public bool IsMatch(string textToCheck)
    {
        if (combinationsList.Count == 0) return true;
        string t = _caseSensitive ? textToCheck : textToCheck.ToLower();
        return combinationsList.All(tg => tg.Any(c => t.Contains(c)));
    }

看起来像魔法，但它有效。谢谢大家

相关文章：