Что-то вроде:

static void Main()
{
    string[] data = { "A", "B", "C", "D", "E" };
    WalkSubSequences(data, 3);
}

public static void WalkSubSequences<T>(IEnumerable<T> data, int sequenceLength)
{
    T[] selected = new T[sequenceLength];
    WalkSubSequences(data.ToArray(), selected, 0, sequenceLength);
}
private static void WalkSubSequences<T>(T[] data, T[] selected,
    int startIndex, int sequenceLength)
{
    for (int i = startIndex; i + sequenceLength <= data.Length; i++)
    {
        selected[selected.Length - sequenceLength] = data[i];
        if (sequenceLength == 1)
        {
            ShowResult(selected);
        }
        else
        {
            WalkSubSequences(data, selected, i + 1, sequenceLength - 1);
        }
    }
}

private static void ShowResult<T>(T[] selected)
{
    StringBuilder sb = new StringBuilder();
    sb.Append(selected[0]);
    for (int j = 1; j < selected.Length; j++)
    {
        sb.Append(';').Append(selected[j]);
    }
    Console.WriteLine(sb.ToString());
}

Вот решение, хранящее состояние в массиве bools. Он работает путем создания следующих состояний при каждом Next()вызове (n = 5, k = 3).

1 1 1. , Переместить последнюю 1 вправо один раз.
1 1. 1 Переместить последнюю 1 вправо один раз.
1 1. , 1 Переместите последнюю 1 вправо один раз.
1 1 1. Переместите второй последний 1 вправо один раз и все 1 с правой спины.
1 1 1 Переместите последнюю 1 вправо один раз.
1 , 1 1 Переместите второй последний 1 вправо один раз (и все 1 с правой спины.)
, 1 1 1. Переместите третий последний 1 вправо один раз и все 1 с правой спины.
, 1 1. 1 Переместите последнюю 1 вправо один раз.
, 1 1 1 Переместите второй последний 1 вправо один раз (и все 1 с правой спины.)
, , 1 1 1 Переместите третий последний 1 вправо один раз (и все 1 с правой спины.)

Это состояние затем может быть использовано для выбора базовых элементов из предоставленной последовательности для каждого состояния.

Сначала инициализация.

public static Boolean[] Initialize(Int32 n, Int32 k)
{
    return Enumerable.Concat(Enumerable.Repeat(true, k),
                             Enumerable.Repeat(false, n - k)).ToArray();
}

Код для перехода к следующей комбинации (подпоследовательность).

public static Boolean Next(this Boolean[] list)
{
    Int32 lastOneIndex = Array.LastIndexOf(list, true);

    if (lastOneIndex == -1)
    {
        return false; // All zeros. 0000000
    }
    else if (lastOneIndex < list.Length - 1)
    {
        // Move the last one right once. 1100X00 => 11000X0
        list.MoveBlock(lastOneIndex, lastOneIndex, lastOneIndex + 1);
    }
    else
    {
        Int32 lastZeroIndex = Array.LastIndexOf(list, false, lastOneIndex);

        if (lastZeroIndex == -1)
        {
            return false; // All ones. 1111111
        }
        else
        {
            Int32 blockEndIndex = Array.LastIndexOf(list, true, lastZeroIndex);

            if (blockEndIndex == -1)
            {
                // Move all ones back to the very left. 0000XXX => XXX0000
                list.MoveBlock(lastZeroIndex + 1, lastOneIndex, 0);

                return false; // Back at initial position.
            }
            else
            {
                // Move the block end right once. 11X0011 => 110X011
                list.MoveBlock(blockEndIndex, blockEndIndex, blockEndIndex + 1);
                // Move the block of ones from the very right back left. 11010XX => 1101XX0
                list.MoveBlock(lastZeroIndex + 1, lastOneIndex, blockEndIndex + 2);
            }
        }
    }

    return true;
}

Наконец несколько вспомогательных методов.

public static void MoveBlock(this Boolean[] list, Int32 oldStart, Int32 oldEnd, Int32 newStart)
{
    list.ClearBlock(oldStart, oldEnd);
    list.SetBlock(newStart, newStart + oldEnd - oldStart);
}

public static void SetBlock(this Boolean[] list, Int32 start, Int32 end)
{
    list.SetBlockToValue(start, end, true);
}

public static void ClearBlock(this Boolean[] list, Int32 start, Int32 end)
{
    list.SetBlockToValue(start, end, false);
}

public static void SetBlockToValue(this Boolean[] list, Int32 start, Int32 end, Boolean value)
{
    for (int i = start; i <= end; i++)
    {
        list[i] = value;
    }
}

И пример использования с использованием строки вместо списка.

var sequence = "ABCDE";

var state = Initialize(sequence.Count(), 5);

do
{
    Console.WriteLine(new String(sequence.Where((_, idx) => state[idx]).ToArray()));
}
while (state.Next());

Я бы предложил рекурсивный алгоритм для этого. Извините, но я давно уже ничего не делал в C #, поэтому я просто приведу здесь псевдокод.

function allPossible(iterator, length, currSubSeq, allResults) {
    // Add the current sub sequence to the results if it is the correct length.
    if (currSubSeq.length == length) {
        copy = currSubSeq.copy();
        allResults.add(copy);
    }
    // If it is too long, return early.
    else if (currSubSeq.length > length) {
        return allResults;
    }

    // Get the next item from the iterator and handle both cases:
    // I.E. when it is, and when it isn't in a sub sequence.
    item = iterator.getNext();
    allPossible(iterator, currSubSeq, allResults);
    currSubSeq.add(item);
    allPossible(iterator, currSubSeq, allResults);

    return allResults;
}

Затем вы находите все возможные подпоследовательности, вызывая allPossibleоператор, iteratorкоторый производит все элементы в вашей исходной последовательности, для lengthкоторого вы хотите получить свои подпоследовательности, пустую последовательность элементов для currSubSeqи пустую последовательность последовательностей элементов allResults. Я предполагаю семантику передачи по ссылке для всех параметров. Извините, что я не смог дать вам правильную реализацию C #, но я уверен, что вы знаете более чем достаточно, чтобы взять набросок моего алгоритма и превратить его в код.

Последняя вещь. Поскольку этот алгоритм является рекурсивным, у вас может быть переполнение стека, если вы запускаете его на очень длинной последовательности с большим lengthпараметром, поскольку использование стека равно O (2 ^ N), где N = length. Я не думаю, что это большая проблема, потому что алгоритм имеет O (2 ^ N) времени выполнения из-за характера проблемы, поэтому вы не должны пытаться запустить его с достаточно большим, lengthчтобы переполнить стек в любом случае!

ПРОСМОТР Я на самом деле не тестировал этот псевдокод, так что может быть что-то тонкое, о чем я не думал.