List< Int>的有序排列 [英] Ordered Permutation of List<Int>

问题描述

给出一个有序的整数列表，L = {1，2，3，4} 排列大小为k，

Given an ordered list of integers, L = { 1, 2, 3, 4 } and a permutation size of k,

我需要生成所有长度为k且具有第一个序列= L [0]的有序"置换.

I need to generate all 'ordered' permutations of length k having the first sequence = L[0].

在上面的示例中，这将产生以下结果:

With the example above, this should yield the following results:

k = 1

= {1}

k = 2

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

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

k = 3

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

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

k = 4

= {1，2，3，4}

= { 1, 2, 3, 4 }

这是我想出的:

1. 分配排列=生成L [1 ... n-1]的所有可能排列.
2. permutations.EliminateIfNotInOrder().
3. 在每个序列中排列L [0].

是否有更好的方法可以首先生成所有有序排列，而无需进行第二步消除?

Is there any better way to generate all ordered permutations in the first place, without needing the second-step of elimination?

推荐答案

假设按顺序"是指匹配初始列表中的顺序:

Assuming that by "in order" you mean matching the order in the initial list:

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 );
        }
    }
}

仍然可以提高效率(通过删除递归).但这是我能想到的最简单的算法.在您的情况下，由于您始终希望第一个元素出现，因此可以通过砍掉第一个元素并稍后再放回去来运行该算法:

This can still be made more efficient (by removing the recursion). But this is the most straight-forward algorithm I could come up with. In your case, since you always want the first element to appear, you can run the algorithm by chopping off the first element and just put it back on later:

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

此算法背后的思想非常简单:通过选择排列中的第一项并将其排在列表其余部分之外的所有长度为k - 1的排列之前，可以找到所有排列.

The idea behind this algorithm is fairly simple: All permutations are found by picking the first item in the permutation and just prepending it to all permutations of length k - 1 made out of the remainder of the list.

如果您要删除递归，则有一种迭代查看的方式:

If you want to remove the recursion, there's a way of looking at it iteratively:

如果要长度为k的排列，请初始化指向源的前k个元素的k指针.这些指针指向当前排列的元素.要获得下一个排列，请增加最后一个指针.如果最后一个指针超出了源的末尾，则增加前一个指针并将最后一个指针设置为超过它的一个.在代码中:

If you want a permutation of length k, initialize k pointers pointing to the first k elements of the source. These pointers point to the elements of the current permutation. To get the next permutation, increment the last pointer. If the last pointer goes past the end of the source, increment the previous pointer and set the last pointer to one past it. In code:

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;
        }
    }
}

这篇关于List< Int>的有序排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！