生成数据源 [10] 大于所需组合长度 [5] 的组合

绿树

我需要能够从预定义的 int[] 生成 10 个整数的所有可能组合，然后将这些可能的组合作为列表返回。每个组合的长度必须为5。

例子：

{1, 2, 3, 4, 5},
{2, 3, 4, 5, 6},
{3, 4, 5, 6, 7}, etc.

到目前为止，我有以下几点：

int[] cardFaces = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
List<int[]> combos = new List<int[]>();

// For every value in the cardFaces array, get the value and the index.

foreach (var item in cardFaces.Select((value, i) => new { i, value }))
  {
    int value = item.value;
    int index = item.i;    
    int value1 = 0;
    int value2 = 0;
    int value3 = 0;
    int value4 = 0;
    int value5 = 0;

    // Need some nested loop code here, which will create combinations
    // from the cardFaces[] with a length of 5.

    int[] combo = {value1, value2, value3, value4, value5};

    combos.Add(combo);

  }

它不应包含任何重复。我对此很陌生，所以我正在努力研究如何解决循环以获得我需要的组合。

凯尔

这是一个更通用的实现。它需要一个可供选择的项目列表和要选择的项目数量 ( k)。在你的情况下，k = 5.

它是这样工作的：初始化k指向k源列表第一个元素的“指针” 。这是第一个组合。视觉上我们有：

source:  [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
pointers:  ^  ^  ^  ^  ^

要获得下一个组合，请增加最后一个指针：

source:  [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
pointers:  ^  ^  ^  ^     ^

如果该指针现在超过列表末尾，那么我们转到前一个指针并将其递增并将最后一个指针移到它之后。所以假设我们目前的组合如下：

source:  [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
pointers:  ^  ^  ^  ^                  ^

如果我们增加最后一个指针，它将超过结尾。因此，我们从末尾开始查看下一个指针并将其递增，并将我们的最后一个指针放在它之后：

source:  [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
pointers:  ^  ^  ^     ^  ^

然后我们回到像往常一样递增最后一个指针：

source:  [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
pointers:  ^  ^  ^     ^     ^

source:  [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
pointers:  ^  ^  ^     ^        ^

等等。每次您的最后一个指针到达末尾时，您都会移动最后一个指针的下一个。一旦它到达终点（实际上是它之前的一个），您将下一个移回。基本上，一旦您的最后一个指针到达末尾，您就会返回指针列表，尝试向前移动每个指针，直到找到可以向前移动的指针。一旦找到一个，就将所有指针设置为指向它之后的序列。例如：

source:  [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
pointers:  ^                 ^  ^  ^   ^

我们将遍历我们的指针，注意到除了第一个我们不能移动它们中的任何一个。因此，我们将那个移动到下一个位置，然后将所有其他位置重置为紧随其后：

source:  [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
pointers:     ^  ^  ^  ^  ^

如果第一个指针距末尾小于 k 个元素，则我们处于最后一个组合，可以停止。

在代码中，它看起来像这样：

public static IEnumerable<IEnumerable<T>> GetOrderedPermutations<T>( IList<T> source, int k )
{
    if( k == 0 ) yield return Enumerable.Empty<T>();
    if( k == source.Count ) yield return source;
    if( k > source.Count ) yield break;
    var pointers = Enumerable.Range( 0, k ).ToArray();

    while( pointers[0] <= source.Count - k )
    {
        yield return pointers.Select( p => source[p] );

        pointers[k - 1]++;

        int i = k - 2;
        while( pointers[k - 1] >= source.Count && i >= 0 )
        {
            pointers[i]++;

            for( int j = i + 1; j < k; ++j )
            {
                pointers[j] = pointers[j - 1] + 1;
            }

            --i;
        }
    }
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。