假设“按顺序”是指匹配初始列表中的顺序:
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;
}
}
}