C# โปรแกรมพิมพ์ Sublists ทั้งหมดของ List

ตัวอย่างโค้ด (แก้ไขจากต้นฉบับให้ทำงานถูกต้อง)

using System;
using System.Collections.Generic;
using System.Linq;

namespace Demo {
    class MyApplication {
        static void Main(string[] args) {
            string str = "xyz";
            
            // ใช้ List แทน List แบบ Raw
            var list = new List();
            
            // Generate all non-empty subsequences
            for (int i = 0; i < str.Length; i++) {
                // เพิ่มตัวอักษรเดี่ยว
                list.Add(str[i].ToString());
                
                // สร้าง Subsequences ใหม่จากที่มีอยู่
                var newList = new List();
                for (int j = 0; j < list.Count - 1; j++) {  // -1 เพื่อไม่เอาตัวที่เพิ่ง Add
                    string combined = list[j] + str[i];
                    newList.Add(combined);
                }
                list.AddRange(newList);
            }
            
            list.Sort();  // เรียงลำดับ
            Console.WriteLine(string.Join(Environment.NewLine, list));
        }
    }
}

ผลลัพธ์

x
xy
xyz
xz
y
yz
z

วิธีที่ดีกว่า: ใช้ Bit Manipulation

เหมาะกับ n ≤ 30 (2^30 ≈ 1 billion)

public static List GetAllSubsequences(string str) {
    var result = new List();
    int n = str.Length;
    int total = 1 << n;  // 2^n
    
    for (int mask = 1; mask < total; mask++) {  // เริ่ม 1 = ข้าม Empty String
        var chars = new char[n];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                chars[idx++] = str[i];
            }
        }
        result.Add(new string(chars, 0, idx));
    }
    
    result.Sort();
    return result;
}

วิธี Recursive (Backtracking)

public static void GenerateSubsequences(string str, int index, string current, List result) {
    if (index == str.Length) {
        if (!string.IsNullOrEmpty(current))
            result.Add(current);
        return;
    }
    
    // ไม่เอาตัวนี้
    GenerateSubsequences(str, index + 1, current, result);
    // เอาตัวนี้
    GenerateSubsequences(str, index + 1, current + str[index], result);
}

// ใช้งาน
var result = new List();
GenerateSubsequences("xyz", 0, "", result);
result.Sort();

สำหรับ List<T> ทั่วไป (ไม่ใช่ String)

public static List> GetAllSublists(List source) {
    var result = new List>();
    int n = source.Count;
    int total = 1 << n;
    
    for (int mask = 1; mask < total; mask++) {
        var sublist = new List();
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                sublist.Add(source[i]);
            }
        }
        result.Add(sublist);
    }
    return result;
}

// ใช้งาน
var numbers = new List { 1, 2, 3 };
var sublists = GetAllSublists(numbers);
// [[1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

Complexity Analysis

⚠️ หมายเหตุ

โค้ดต้นฉบับมี Logic Error ที่ list.Add(str[i - 1].ToString()) และ Loop เริ่มจาก i=1 ทำให้พลาดตัวแรกและตัวสุดท้าย โค้ดข้างบนแก้ไขแล้ว