Bắt tất cả các kết hợp có thể từ một danh sách các số

Question

Tôi đang tìm kiếm một cách hiệu quả để đạt được điều này:

• bạn có một danh sách các số 1 ..... n (thường là: 1 .. 5 hoặc 1,.7 hoặc hơn - nhỏ hợp lý, nhưng có thể khác nhau tùy từng trường hợp)

• bạn cần tất cả các kết hợp của tất cả các độ dài cho các số đó, ví dụ tất cả các kết hợp của chỉ một số ({1}, {2}, .... {n}), sau đó tất cả các kết hợp của hai số riêng biệt ({1,2}, {1,3}, {1,4}. .... {n-1, n}), sau đó tất cả các kết hợp cho ba số đó ({1,2,3}, {1,2,4}) và cứ thế

Về cơ bản, trong nhóm, thứ tự không liên quan, vì vậy {1,2,3} tương đương với {1,3,2} - nó chỉ là vấn đề nhận được tất cả các nhóm x số từ danh sách đó

Có vẻ như đã có là một thuật toán đơn giản cho điều này - nhưng tôi đã tìm kiếm vô ích cho đến nay. Hầu hết các thuật toán tổ hợp và hoán vị dường như là a) đưa vào tài khoản (ví dụ 123 không bằng 132), và chúng luôn có vẻ hoạt động trên một chuỗi ký tự hoặc số ...

Bất cứ ai cũng có một nice'n'quick thuật toán lên tay áo của họ ??

Cảm ơn!

Answer 1

Chỉ cần tăng số nhị phân và lấy các phần tử tương ứng với các bit được đặt.

Ví dụ, 00101101 có nghĩa là lấy các yếu tố ở chỉ số 0, 2, 3 và 5. Từ danh sách của bạn chỉ đơn giản là 1..n, nguyên tố này chỉ đơn giản là chỉ + 1.

này sẽ tạo ra trong permuatations theo thứ tự. Nói cách khác, chỉ có {1, 2, 3} sẽ được tạo. Không phải {1, 3, 2} hoặc {2, 1, 3} hoặc {2, 3, 1}, v.v.

Answer 2

Đây là điều tôi đã viết trong quá khứ để thực hiện một tác vụ như vậy.

List<T[]> CreateSubsets<T>(T[] originalArray) 
{ 
    List<T[]> subsets = new List<T[]>(); 

    for (int i = 0; i < originalArray.Length; i++) 
    { 
     int subsetCount = subsets.Count; 
     subsets.Add(new T[] { originalArray[i] }); 

     for (int j = 0; j < subsetCount; j++) 
     { 
      T[] newSubset = new T[subsets[j].Length + 1]; 
      subsets[j].CopyTo(newSubset, 0); 
      newSubset[newSubset.Length - 1] = originalArray[i]; 
      subsets.Add(newSubset); 
     } 
    } 

    return subsets; 
} 

Đó là chung chung, vì vậy nó sẽ làm việc cho ints, chờ đợi, chuỗi, Foos vv

Answer 3

Không mã của tôi, nhưng bạn đang tìm kiếm Powerset. Google đã cho tôi giải pháp này, mà dường như t công việc:

public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list) 
{ 
    return from m in Enumerable.Range(0, 1 << list.Count) 
       select 
        from i in Enumerable.Range(0, list.Count) 
        where (m & (1 << i)) != 0 
        select list[i]; 
} 

Nguồn: http://rosettacode.org/wiki/Power_set#C.23