Làm thế nào để có được tất cả các tập con của một mảng?

Question

Với một mảng:

[,,] 
[,,mouse] 
[,cat,] 
[,cat,mouse] 
[dog,,] 
[dog,,mouse] 
[dog,cat,] 
[dog,cat,mouse] 

tôi cần điều này để làm việc cho bất kỳ mảng có kích thước: [dog, cat, mouse]

cách thanh lịch nhất để tạo ra là gì.

Đây thực chất là bộ đếm nhị phân, trong đó các chỉ mục mảng biểu diễn các bit. Điều này có lẽ cho phép tôi sử dụng một số hoạt động bitwise để đếm, nhưng tôi không thể nhìn thấy một cách tốt đẹp của dịch này để chỉ số mảng mặc dù.

Answer 1

string[] source = new string[] { "dog", "cat", "mouse" }; 
for (int i = 0; i < Math.Pow(2, source.Length); i++) 
{ 
    string[] combination = new string[source.Length]; 
    for (int j = 0; j < source.Length; j++) 
    { 
     if ((i & (1 << (source.Length - j - 1))) != 0) 
     { 
      combination[j] = source[j]; 
     } 
    } 
    Console.WriteLine("[{0}, {1}, {2}]", combination[0], combination[1], combination[2]); 
} 

Answer 2

static IEnumerable<IEnumerable<T>> GetSubsets<T>(IList<T> set) 
{ 
    var state = new BitArray(set.Count); 
    do 
     yield return Enumerable.Range(0, state.Count) 
           .Select(i => state[i] ? set[i] : default(T)); 
    while (Increment(state)); 
} 

static bool Increment(BitArray flags) 
{ 
    int x = flags.Count - 1; 
    while (x >= 0 && flags[x]) flags[x--] = false ; 
    if (x >= 0) flags[x] = true; 
    return x >= 0; 
} 

Cách sử dụng:

foreach(var strings in GetSubsets(new[] { "dog", "cat", "mouse" })) 
    Console.WriteLine(string.Join(", ", strings.ToArray())); 

Answer 3

Tôi không phải là rất quen thuộc với C# nhưng tôi chắc chắn có điều gì đó như:

// input: Array A 
foreach S in AllSubsetsOf1ToN(A.Length): 
    print (S.toArray().map(lambda x |> A[x])); 

---

Ok, Tôi đã nói câu trả lời ở trên sẽ không hoạt động. Nếu bạn đánh giá cao sang trọng hơn hiệu quả, tôi sẽ cố gắng đệ quy, trong giả crappy của tôi:

Array_Of_Sets subsets(Array a) 
{ 
    if (a.length == 0) 
     return [new Set();] // emptyset 
    return subsets(a[1:]) + subsets(a[1:]) . map(lambda x |> x.add a[0]) 
} 

Answer 4

Dưới đây là một giải pháp dễ dàng-to-theo dọc theo dòng của quan niệm của bạn:

private static void Test() 
{ 
    string[] test = new string[3] { "dog", "cat", "mouse" }; 

    foreach (var x in Subsets(test)) 
     Console.WriteLine("[{0}]", string.Join(",", x)); 
} 

public static IEnumerable<T[]> Subsets<T>(T[] source) 
{ 
    int max = 1 << source.Length; 
    for (int i = 0; i < max; i++) 
    { 
     T[] combination = new T[source.Length]; 

     for (int j = 0; j < source.Length; j++) 
     { 
      int tailIndex = source.Length - j - 1; 
      combination[tailIndex] = 
       ((i & (1 << j)) != 0) ? source[tailIndex] : default(T); 
     } 

     yield return combination; 
    } 
} 

Answer 5

Bạn có thể sử dụng lớp BitArray để dễ dàng truy cập các bit theo một số:

string[] animals = { "Dog", "Cat", "Mouse" }; 
List<string[]> result = new List<string[]>(); 
int cnt = 1 << animals.Length; 
for (int i = 0; i < cnt; i++) { 
    string[] item = new string[animals.Length]; 
    BitArray b = new BitArray(i); 
    for (int j = 0; j < item.Length; j++) { 
     item[j] = b[j] ? animals[j] : null; 
    } 
    result.Add(item); 
} 

Answer 6

Đây là một thay đổi nhỏ đối với giải pháp của Mehrdad ở trên:

static IEnumerable<T[]> GetSubsets<T>(T[] set) { 
    bool[] state = new bool[set.Length+1]; 
    for (int x; !state[set.Length]; state[x] = true) { 
     yield return Enumerable.Range(0, state.Length) 
           .Where(i => state[i]) 
           .Select(i => set[i]) 
           .ToArray(); 
     for (x = 0; state[x]; state[x++] = false); 
    } 
} 

hoặc với con trỏ

static IEnumerable<T[]> GetSubsets<T>(T[] set) { 
    bool[] state = new bool[set.Length+1]; 
    for (bool *x; !state[set.Length]; *x = true) { 
     yield return Enumerable.Range(0, state.Length) 
           .Where(i => state[i]) 
           .Select(i => set[i]) 
           .ToArray(); 
     for (x = state; *x; *x++ = false); 
    } 
} 

Answer 7

Elegant? Tại sao không Linq nó.

public static IEnumerable<IEnumerable<T>> SubSetsOf<T>(IEnumerable<T> source) 
    { 
     if (!source.Any()) 
      return Enumerable.Repeat(Enumerable.Empty<T>(), 1); 

     var element = source.Take(1); 

     var haveNots = SubSetsOf(source.Skip(1)); 
     var haves = haveNots.Select(set => element.Concat(set)); 

     return haves.Concat(haveNots); 
    } 

Answer 8

Đây là giải pháp tương tự như phương pháp của David B, nhưng có lẽ phù hợp hơn nếu thực sự yêu cầu bạn lấy lại bộ với số nguyên tố ban đầu (ngay cả khi trống) :.

static public List<List<T>> GetSubsets<T>(IEnumerable<T> originalList) 
{ 
    if (originalList.Count() == 0) 
     return new List<List<T>>() { new List<T>() }; 

    var setsFound = new List<List<T>>(); 
    foreach (var list in GetSubsets(originalList.Skip(1))) 
    {     
     setsFound.Add(originalList.Take(1).Concat(list).ToList()); 
     setsFound.Add(new List<T>() { default(T) }.Concat(list).ToList()); 
    } 
    return setsFound; 
} 

Nếu bạn chuyển vào danh sách ba chuỗi, bạn sẽ lấy lại tám danh sách với ba phần tử mỗi (nhưng một số thành phần sẽ rỗng).

Answer 9

Guffa của câu trả lời có các chức năng cơ bản mà tôi đã tìm kiếm, tuy nhiên phù hợp với

BitArray b = new BitArray(i); 

không làm việc cho tôi, nó đã cho một ArgumentOutOfRangeException. Đây là mã được điều chỉnh và làm việc hơi của tôi:

string[] array = { "A", "B", "C","D" }; 
int count = 1 << array.Length; // 2^n 

for (int i = 0; i < count; i++) 
{ 
    string[] items = new string[array.Length]; 
    BitArray b = new BitArray(BitConverter.GetBytes(i)); 
    for (int bit = 0; bit < array.Length; bit++) { 
     items[bit] = b[bit] ? array[bit] : ""; 
    } 
    Console.WriteLine(String.Join("",items)); 
}