及时计算组合

Question

我想对 N 个变量的每个三元组组合做一些事情：

示例 1:

T
F
U

示例 2:

TT
FT
UT
TF
FF
UF
UU

有没有办法计算这个但只在需要时计算：例如：

    var combinator = new Combinator<string>(2, {"T","F","U"});
    List<String> tt = combinator.Next(); 
    //tt contains {"T","T"}

Answer 1

可能不是计算效率最高的，但它是组合数学，所以复杂性可能非常糟糕：

public static IEnumerable<List<T>> Combinations<T>( int count, IEnumerable<T> items )
{
    if( count <= 0 ) yield break;
    if( count == 1 ) 
    {
        foreach( var item in items ) yield return new List<T> { item };
        yield break;
    }

    foreach( var item in items )
    {
        foreach( var combo in Combinations<T>( count - 1, items ) )
        {
            var result = new List<T> { item };
            result.AddRange( combo );
            yield return result;
        }
    }
}

Answer 2

你可以通过给组合一些排序来实现这个，所以你基本上可以在它们和从 1 到 n^m 的数字之间分配一个映射（其中 n 是排列的长度，m 是字符串的数量） .然后保存状态。

然而，这基本上是重新实现 IEnumerable。 https://msdn.microsoft.com/de-de/library/system.collections.ienumerable(v=vs.110).aspx

更简单的是，如果您在某种 foreach 循环中需要它，则只需使用 returns IEnumerable 的方法。如果您使用 yield 语法，IEnumerable 将被延迟计算。 http://www.dotnetperls.com/yield

Answer 3

您可以在迭代器方法中实现它：

private IEnumerable<List<T>> Combinations<T>(int n, T[] values)
{
    if (n == 0) yield return new List<T>();
    else
    {
        foreach (var list in Combinations(n - 1, values))
            foreach (var item in values)
            {
                var items = new List<T>(list);
                items.Add(item);
                yield return items;
            }
    }
}

这会创建所有组合，但是是以一种惰性的方式进行的。

如果需要，您可以像这样创建 Combinator class：

class Combinator<T>
{
    IEnumerator<List<T>> enumerator;

    public Combinator(int n, T[] values)
    {
        enumerator = Combinations(n, values).GetEnumerator();
    }

    public List<T> Next()
    {
        return enumerator.MoveNext() ? enumerator.Current : null;
    }

    private IEnumerable<List<T>> Combinations<T>(int n, T[] values) { ... }
}

Answer 4

不清楚您是如何获得 TFU 组合的。

您只列出了以下内容：

TT
FT
UT
TF
FF
UF
UU

但是缺少两个组合，应该是这样的（据我所知）：

TT
FT
UT
TF
FF
UF
TU
FU
UU

假设后者实际上是正确的列表，那么您可以这样计算它"on demand"：

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    class Program
    {
        public static void Main()
        {
            foreach (var combination in Combinator(new [] { "T", "F", "U" }, 2))
                Console.WriteLine(string.Concat(combination));
        }

        public static IEnumerable<IEnumerable<T>> Combinator<T>(IEnumerable<T> sequence, int count)
        {
            if (count == 0)
            {
                yield return Enumerable.Empty<T>();
                yield break;
            }

            foreach (T startingElement in sequence)
            {
                IEnumerable<T> remainingItems = sequence;

                foreach (IEnumerable<T> permutationOfRemainder in Combinator(remainingItems, count - 1))
                    yield return permutationOfRemainder.Concat(new [] { startingElement});
            }
        }
    }
}

及时计算组合

Just in time computation of combinations

c#

algorithm

combinations