c# - 如何根据括号中的范围获得每个可能的组合？

Question

寻找最好的方法来获取类似的东西1[a-C]3[1-6]07[R,E-G]并让它输出一个如下所示的日志——基本上每个可能的组合都基于括号中的范围。

1a3107R
1a3107E
1a3107F
1a3107G
1b3107R
1b3107E
1b3107F
1b3107G
1c3107R
1c3107E
1c3107F
1c3107G

一直到1C3607G。

抱歉，我对我要寻找的东西没有更多的技术性，只是不确定要解释的正确术语。

标签： c#python

Answer 1

I would approach this problem in three stages. The first stage is to transform the source string to an IEnumerable of IEnumerable<string>.

static IEnumerable<IEnumerable<string>> ParseSourceToEnumerables(string source);

For example the source "1[A-C]3[1-6]07[R,E-G]" should be transformed to the 6 enumerables below:

"1"
"A", "B", "C"
"3"
"1", "2", "3", "4", "5", "6"
"07"
"R", "E", "F", "G"

Each literal inside the source has been transformed to an IEnumerable<string> containing a single string.

The second stage would be to create the Cartesian product of these enumerables.

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
    IEnumerable<IEnumerable<T>> sequences)

The final (and easiest) stage would be to concatenate each one of the inner IEnumerable<string> of the Cartesian product to a single string. For example the sequence "1", "A", "3", "1", "07", "R" to the string "1A3107R"

The hardest stage is the first one, because it involves parsing. Below is a partial implementation:

static IEnumerable<IEnumerable<string>> ParseSourceToEnumerables(string source)
{
    var matches = Regex.Matches(source, @"\[(.*?)\]", RegexOptions.Singleline);
    int previousIndex = 0;
    foreach (Match match in matches)
    {
        var previousLiteral = source.Substring(
            previousIndex, match.Index - previousIndex);
        if (previousLiteral.Length > 0)
            yield return Enumerable.Repeat(previousLiteral, 1);
        yield return SinglePatternToEnumerable(match.Groups[1].Value);
        previousIndex = match.Index + match.Length;
    }
    var lastLiteral = source.Substring(previousIndex, source.Length - previousIndex);
    if (lastLiteral.Length > 0) yield return Enumerable.Repeat(lastLiteral, 1);
}

static IEnumerable<string> SinglePatternToEnumerable(string pattern)
{
    // TODO
    // Should transform the pattern "X,A-C,YZ"
    // to the sequence ["X", "A", "B", "C", "YZ"]
}

The second stage is hard too, but solved. I just grabbed the implementation from Eric Lippert's blog.

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
    IEnumerable<IEnumerable<T>> sequences)
{
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
    return sequences.Aggregate(
        emptyProduct,
        (accumulator, sequence) =>
        accumulator.SelectMany(_ => sequence,
            (accseq, item) => accseq.Append(item)) // .NET Framework 4.7.1
    );
}

The final stage is just a call to String.Join.

var source = "1[A-C]3[1-6]07[R,E-G]";
var enumerables = ParseSourceToEnumerables(source);
var combinations = CartesianProduct(enumerables);
foreach (var combination in combinations)
{
    Console.WriteLine($"Combination: {String.Join("", combination)}");
}