寻找可能的组合

本文关键字：组合 寻找 | 更新日期: 2023-09-27 18:04:18

我需要生成{"a", "b","c"}。

例如，输入集如{"a", "b","c"}，预期输出为{"a", "b", "c" "ab", "ac", "bc", "abc"}。

寻找可能的组合

听起来你要找的基本上是一种形式的权力集。下面是一个简单的实现(取自本网站):

public IEnumerable<IEnumerable<T>> GetPowerSet<T>(this IList<T> list)
{
    return from m in Enumerable.Range(0, 1 << list.Count)
           select
               from i in Enumerable.Range(0, list.Count)
               where (m & (1 << i)) != 0
               select list[i];
}

注意，由于<<操作符，您将无法对具有超过30个元素的列表使用此方法。无论如何，我不建议使用接近这么多元素的列表进行尝试，因为在30个元素时，结果集将包含230或1073741824个元素。

你可以使用这个方法得到你想要的结果，像这样

public IEnumerable<string> GetPermutations(IList<string> strings)
{
    return from s in strings.GetPowerSet()
           select string.Concat(s);
}

但是，因为幂集包含空集，这实际上将返回结果{"", "a", "b", "c", "ab", "ac", "bc", "abc"}。要过滤掉空字符串，使用以下命令:

public IEnumerable<string> GetPermutations(IList<string> strings)
{
    return from s in strings.GetPowerSet()
           let str = string.Concat(s)
           where str.Length > 0 // exclude null set result
           select str;
}

或者更简单:

public IEnumerable<string> GetPermutations(IList<string> strings)
{
    return from s in strings.GetPowerSet().Skip(1)
           select string.Concat(s);
}
相关文章：