列表<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. 排列。消除如果不是订单()。
在排列
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;
}
}
}