Tính tất cả các khả năng phụ chuỗi có chiều dài nhất định (C#)

Question

Nếu tôi có một chuỗi như sau (giả sử nó là một IEnumerable<T>):

[A, B, C, D, E] 

Sau đó cách sạch để tính là những gì tất cả các khả năng (liên tục và không liên tục) subsequences có thời lượng nhất định? Việc sắp xếp các kết quả trong tập kết quả không quan trọng, nhưng không nên bao gồm các bản sao.

ví dụ: Nếu tôi muốn để tính toán tất cả subsequences có thể có độ dài 3 tập hợp kết quả sẽ là:

[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] 

---

Đối với hồ sơ, câu trả lời được chấp nhận dưới đây đã cho tôi một điểm khởi đầu tốt, và đây là đoạn code tôi đã ra đi với điều đó được cập nhật để sử dụng một số phương pháp mở rộng 3,5 NET mới:

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

Answer 1

tôi đã thành công với PermuteUtils lớp iang của:

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

Kết quả trong:

 
[ 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 ] 
... 

Answer 2

Cái gì như:

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

Answer 3

tôi sẽ đề nghị một thuật toán đệ quy cho việc này. Tôi xin lỗi, nhưng nó đã được một thời gian kể từ khi tôi đã làm bất cứ điều gì trong C#, vì vậy tôi sẽ chỉ cung cấp cho mã giả ở đây.

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

Sau đó, bạn tìm thấy tất cả các chuỗi phụ có thể bằng cách gọi allPossible với một iterator sản xuất tất cả các yếu tố theo thứ tự ban đầu của bạn, các length mà bạn muốn tiểu trình tự của bạn, một chuỗi rỗng các mặt hàng cho currSubSeq, và một sản phẩm nào chuỗi các chuỗi mục cho allResults. Tôi giả định ngữ nghĩa pass-by-reference cho tất cả các tham số. Xin lỗi vì tôi không thể cung cấp cho bạn triển khai C# phù hợp, nhưng tôi chắc rằng bạn biết quá đủ để thực hiện thuật toán thuật toán của mình và biến nó thành mã.

Một điều cuối cùng. Bởi vì thuật toán này là đệ quy, bạn có thể có tràn ngăn xếp nếu bạn chạy nó trên một chuỗi rất dài với tham số length lớn vì việc sử dụng ngăn xếp là O (2^N) trong đó N = length. Tôi không nghĩ rằng đây là một vấn đề lớn bởi vì thuật toán có thời gian chạy O (2^N) vì bản chất của vấn đề, do đó bạn không nên chạy nó với đủ lớn length để tràn ngăn xếp !

CAVEAT Tôi chưa thực sự kiểm tra mã giả này, vì vậy có thể có điều gì đó tinh tế mà tôi chưa từng nghĩ tới.

Answer 4

Đây là giải pháp lưu trữ trạng thái trong một mảng các bool. Nó hoạt động bằng cách tạo các trạng thái sau trên mỗi cuộc gọi Next() (n = 5, k = 3).

 
1 1 1 . . Move last 1 right once. 
1 1 . 1 . Move last 1 right once. 
1 1 . . 1 Move last 1 right once. 
1 . 1 1 . Move the second last 1 right once and all 1s from the right back. 
1 . 1 . 1 Move last 1 right once. 
1 . . 1 1 Move the second last 1 right once (and all 1s from the right back.) 
. 1 1 1 . Move the third last 1 right once and all 1s from the right back. 
. 1 1 . 1 Move last 1 right once. 
. 1 . 1 1 Move the second last 1 right once (and all 1s from the right back.) 
. . 1 1 1 Move the third last 1 right once (and all 1s from the right back.) 

Trạng thái này có thể được sử dụng để chọn các mục ghi nhớ từ chuỗi được cung cấp cho mọi trạng thái.

Lúc đầu, khởi tạo.

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

Mã để chuyển sang kết hợp tiếp theo (sau).

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

Cuối cùng là một số phương pháp trợ giúp.

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

Và ví dụ sử dụng bằng chuỗi thay vì danh sách.

var sequence = "ABCDE"; 

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

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