计算给定长度的所有可能子序列（C#）

Question

如果我有一个序列，如下所示（假设它是一个 IEnumerable<T>）：

[A, B, C, D, E]

那么，计算给定长度的所有可能（连续和非连续）子序列的最清洁的方法是什么？结果集中的顺序不重要，但不应包含重复项。

例如，如果我想计算长度为3的所有可能子序列，则结果集将为：

[A, B, C]
[A, B, D]
[A, B, E]
[A, C, D]
[A, C, E]
[A, D, E]
[B, C, D]
[B, C, E]
[B, D, E]
[C, D, E]

---

就记录而言，下面的被接受的答案为我提供了一个良好的起点，这是我使用的代码，更新后使用了一些新的.NET 3.5扩展方法：

public static IEnumerable<IEnumerable<T>> Subsequences<T>(
    this IEnumerable<T> source, 
    int count)
{
    if (count == 0)
    {
        yield return Enumerable.Empty<T>();
    }
    else
    {
        var skip = 1;
        foreach (var first in source)
        {
            foreach (var rest in source.Skip(skip).Subsequences(count - 1))
            {
                yield return Enumerable.Repeat(first, 1).Concat(rest);
            }

            skip++;
        }
    }
}

- Greg Beech

---

拥有IEnumerable<T>对你来说是不利的，因为你将会多次遍历列表，所以拥有索引器访问将对你非常有帮助。 - DevinB

Answer 1

我使用IanG的PermuteUtils类取得了成功：

char[] items = new char[] { 'A', 'B', 'C', 'D', 'E' };

foreach (IEnumerable<char> permutation in PermuteUtils.Permute(items, 3)) {
    Console.Write("[");
    foreach (char c in permutation) {
        Console.Write(" " + c);
    }
    Console.WriteLine(" ]");
}

结果如下：

[ A B C ]
[ A B D ]
[ A B E ]
[ A C B ]
[ A C D ]
[ A C E ]
[ A D B ]
[ A D C ]
[ A D E ]
[ A E B ]
[ A E C ]
[ A E D ]
[ B A C ]
[ B A D ]
[ B A E ]
[ B C A ]
[ B C D ]
[ B C E ]
[ B D A ]
[ B D C ]
...

- Sean Bright

---

这不是我想要的；那只是所有可能的排列组合，例如[A，D，B]不是子序列，因为它们的顺序不同。 - Greg Beech

再说，修改它以得到正确的结果很容易，所以我会给你接受的答案。谢啦。 - Greg Beech

Answer 2

类似于：

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

- Marc Gravell

Answer 3

我建议使用递归算法解决这个问题。很抱歉，因为我已经有一段时间没有在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;
}

然后，通过使用生成原始序列中所有元素的iterator、您想要的子序列的length、currSubSeq的空序列以及allResults的空项目序列来调用allPossible，您可以找到所有可能的子序列。我假设所有参数都采用引用传递语义。很抱歉我无法为您提供正确的C#实现，但我相信您已经掌握了足够的知识将我的算法草图转化为代码。

最后一件事。由于这个算法是递归的，如果您在一个非常长的序列上运行它，并且使用大的length参数，那么您可能会遇到堆栈溢出问题，因为堆栈使用量是O(2^N)，其中N=length。我认为这不是一个大问题，因为由于问题的本质，该算法具有O(2^N)的运行时间，因此您不应该尝试使用足够大的length来使堆栈溢出！

注意 我实际上没有测试过这个伪代码，所以可能有一些微妙的问题我没有考虑到。

- A. Levy

---

@A. Levy：“‘非连续子序列’不是子序列。”他使用了正确的数学定义，就像他所描述的那样。 - Kevin

这个问题正确地使用了“子序列”。而子集是无序的，所以使用“子集”一词是完全错误的。 - ShreevatsaR

@Kevin 和 @ShreevatsaR：感谢你们纠正了我对子序列的误解。我显然在想“子字符串”。我已经从我的答案中删除了那个无知的学究气息。如果 @Greg Beech 看到这条评论，也许你可以包含一个子序列定义的链接，这样像我这样的无知之辈就可以受教了。例如：http://en.wikipedia.org/wiki/Subsequence - A. Levy

Answer 4

这里有一个将状态存储在布尔数组中的解决方案。它通过在每个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());

- Daniel Brückner