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

如果我有一个如下序列(假设它是一个IEnumerable ):

 [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> Subsequences( this IEnumerable source, int count) { if (count == 0) { yield return Enumerable.Empty(); } 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++; } } } 

我在IanG的PermuteUtils课上取得了成功:

 char[] items = new char[] { 'A', 'B', 'C', 'D', 'E' }; foreach (IEnumerable permutation in PermuteUtils.Permute(items, 3)) { Console.Write("["); foreach (char c in permutation) { Console.Write(" " + c); } Console.WriteLine(" ]"); } 

结果是:

 [ABC]
 [ABD]
 [ABE]
 [ACB]
 [ACD]
 [ACE]
 [亚行]
 [ADC]
 [ADE]
 [AEB]
 [AEC]
 [AED]
 [BAC]
 [坏]
 [BAE]
 [BCA]
 [BCD]
 [BCE]
 [BDA]
 [BDC]
 ...

就像是:

 static void Main() { string[] data = { "A", "B", "C", "D", "E" }; WalkSubSequences(data, 3); } public static void WalkSubSequences(IEnumerable data, int sequenceLength) { T[] selected = new T[sequenceLength]; WalkSubSequences(data.ToArray(), selected, 0, sequenceLength); } private static void WalkSubSequences(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[] 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()); } 

这是一个将状态存储在bool数组中的解决方案。 它的工作原理是在每次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个。)

然后可以使用该状态从每个状态的所提供的序列中选择相应的项目。

首先是初始化。

 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: // IE 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调用allPossible查找所有可能的子序列,该iterator生成原始序列中的所有元素,您希望子序列的lengthcurrSubSeq的空项目序列以及allResults的空序列项目序列。 我假设所有参数都是传递引用语义。 很抱歉,我无法为您提供正确的C#实现,但我相信您已经知道了我的算法草图并将其转换为代码。

最后一件事。 由于此算法是递归的,因此如果在具有较大length参数的非常长的序列上运行它,则可能会发生堆栈溢出,因为堆栈使用为O(2 ^ N),其中N = length 。 我不认为这是一个大问题,因为该算法具有O(2 ^ N)运行时,因为问题的性质,所以你不应该尝试以足够大的length运行它来溢出堆栈!

CAVEAT我实际上没有测试过这个伪代码,所以可能有一些我没有想过的微妙的东西。