Ordered permutation of the list <Int>

Question

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

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

In the above example, this should give the following results:

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}

Here is what I came up with:

• Assign permutations = Create all possible permutations L [1 ... n-1].
• permutations.EliminateIfNotInOrder ().
• Prepare L [0] with each sequence in permutations.

Is there a better way to generate all ordered permutations first and foremost without requiring the second step of exception?

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