有序列表<Int>

Question

的置換給定整數的有序列表，L = {1，2，3，4} 和k的排列大小，

我需要生成全部「有序」長度爲k的排列具有第一序列= L [0]。

隨着上面的例子中，這應該產生以下結果：

k = 1時

= {1}

k = 2時

= { 1，2}，{1,3}，{1，4}

K = 3

= {1，2，3}，{1，2，4}，{1，3,4}

K = 4

= {1 ，2，3，4}

這是我想出了：

1. 分配置換=基因評價L [1 ... n-1]的所有可能的排列。
2. permutations.EliminateIfNotInOrder（）。
3. 預先將L [0]與每個序列排列在一起。

有沒有更好的方法來首先生成所有有序的排列，而不需要第二步的排除？

Answer 1

假設由你的意思是「爲了」匹配的初始列表的順序：

public static IEnumerable<T> Yield<T>(T value) 
{ 
    yield return value; 
} 

public static IEnumerable<IEnumerable<T>> GetOrderedPermutations<T>(IEnumerable<T> source, int k) 
{ 
    if(k == 0) return new[] { Enumerable.Empty<T>() }; 

    int length = source.Count(); 

    if(k == length) return new[] { source }; 

    if(k > length) return Enumerable.Empty<IEnumerable<T>>(); 

    return GetOrderedHelper<T>(source, k, length); 
} 

private static IEnumerable<IEnumerable<T>> GetOrderedHelper<T>(IEnumerable<T> source, int k, int length) 
{ 
    if(k == 0) 
    { 
     yield return Enumerable.Empty<T>(); 
     yield break; 
    } 
    int i = 0; 
    foreach(var item in source) 
    { 
     if(i + k > length) yield break; 
     var permutations = GetOrderedHelper<T>(source.Skip(i + 1), k - 1, length - i); 
     i++; 

     foreach(var subPerm in permutations) 
     { 
      yield return Yield(item).Concat(subPerm); 
     } 
    } 
} 

這仍然可以更有效率（通過消除遞歸）。但這是我能想到的最直接的算法。在你的情況，因爲你總是希望第一個元素出現，您可以通過斬去第一要素運行的算法，只是把它放回後：

var permutations = GetOrderedPermutations(source.Skip(1), k - 1) 
    .Select(p => Yield(source.First()).Concat(p)); 

這個算法背後的想法很簡單：所有排列是通過挑選排列中的第一個項目找到的，並將其預先添加到由列表的其餘部分組成的所有長度爲k - 1的排列中。

如果你想刪除的遞歸，還有的在其反覆尋找一種方式：

如果你想長k的排列，初始化k指針指向源的第一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(); 

    // The first element of our permutation can only be in the first 
    // Count - k + 1 elements. If it moves past here, we can't have 
    // anymore permutations because there aren't enough items in the list. 
    while(pointers[0] <= source.Count - k) 
    { 
     yield return pointers.Select(p => source[p]); 
     // Increment the last pointer 
     pointers[k - 1]++; 

     // The i variable will keep track of which pointer 
     // we need to increment. Start it at the second to 
     // last (since this is the one that we're going to 
     // increment if the last pointer is past the end). 
     int i = k - 2; 
     while(pointers[k - 1] >= source.Count && i >= 0) 
     { 
      // Okay, the last pointer was past the end, increment 
      pointers[i]++; 

      // Reset all the pointers after pointer i 
      for(int j = i + 1; j < k; ++j) 
      { 
       pointers[j] = pointers[j - 1] + 1; 
      } 

      // If the last pointer is still past the end, we'll 
      // catch it on the next go-around of this loop. 
      // Decrement i so we move the previous pointer next time. 

      --i; 
     } 
    } 
}