Liệt kê tất cả các kết hợp có thể có của k số nguyên giữa 1 ... n (n chọn k)

Question

Không có lý do cụ thể nào tôi quyết định tìm một thuật toán tạo tất cả các lựa chọn có thể có của k số nguyên giữa 1 ... n, trong đó thứ tự trong số nguyên k không quan trọng (n chọn k thingy).

Từ cùng một lý do, không có lý do gì cả, tôi cũng đã triển khai nó trong C#. Câu hỏi của tôi là:

Bạn có thấy bất kỳ sai lầm nào trong thuật toán hoặc mã của tôi không? Và quan trọng hơn, bạn có thể đề xuất thuật toán tốt hơn không?

Vui lòng chú ý nhiều hơn đến thuật toán so với chính mã. Đó không phải là đoạn mã đẹp nhất mà tôi từng viết, mặc dù bạn biết nếu bạn gặp lỗi.

EDIT: Alogirthm giải thích -

• Chúng tôi giữ chỉ số k.
• Điều này tạo k lồng nhau cho vòng lặp, trong đó chỉ số vòng lặp i là chỉ mục [i].
• Nó mô phỏng k cho vòng nơi chỉ mục [i + 1] thuộc về vòng lặp được lồng trong vòng lặp của chỉ mục [i].
• chỉ số [i] chạy từ chỉ số [i - 1] + 1 đến n - k + i + 1.

Mã sản phẩm:

public class AllPossibleCombination 
{ 
    int n, k; 
    int[] indices; 
    List<int[]> combinations = null; 

    public AllPossibleCombination(int n_, int k_) 
    { 
     if (n_ <= 0) 
     { 
      throw new ArgumentException("n_ must be in N+"); 
     } 
     if (k_ <= 0) 
     { 
      throw new ArgumentException("k_ must be in N+"); 
     } 
     if (k_ > n_) 
     { 
      throw new ArgumentException("k_ can be at most n_"); 
     } 

     n = n_; 
     k = k_; 
     indices = new int[k]; 
     indices[0] = 1; 
    } 

    /// <summary> 
    /// Returns all possible k combination of 0..n-1 
    /// </summary> 
    /// <returns></returns> 
    public List<int[]> GetCombinations() 
    { 
     if (combinations == null) 
     { 
      combinations = new List<int[]>(); 
      Iterate(0); 
     } 
     return combinations; 
    } 

    private void Iterate(int ii) 
    { 
     // 
     // Initialize 
     // 
     if (ii > 0) 
     { 
      indices[ii] = indices[ii - 1] + 1; 
     } 

     for (; indices[ii] <= (n - k + ii + 1); indices[ii]++) 
     { 
      if (ii < k - 1) 
      { 
       Iterate(ii + 1); 
      } 
      else 
      { 
       int[] combination = new int[k]; 
       indices.CopyTo(combination, 0); 
       combinations.Add(combination); 
      } 
     } 
    } 
} 

Tôi xin lỗi vì câu hỏi dài, nó có thể phù hợp cho một bài đăng blog, nhưng tôi muốn ý kiến ​​của cộng đồng ở đây.

Cảm ơn,
Asaf

Answer 1

Dưới đây là một chương trình tương đối đơn giản/hiệu quả nCr tôi đã viết một thời gian trước trong C:

main(n,k){float t=0,r=1;for(scanf("%d, %d",&n,&k);t++<k;r*=(1+n-t)/t);printf("%.0f\n",r);} 

Okay ... phiên bản có thể đọc được. =] (Không chắc nếu điều này là 1:. 1 tương ứng với ở trên)

void nCr(int n, int k) { 
    float curK = 0, r = 1; 
    while(curK < k) { 
     ++curK; 
     printf("%.0f\n", r); 
     r *= (1 + n - curK)/curK; 
    } 
} 

Thay vì in, bạn có thể yield hoặc bất cứ điều gì (Tôi không biết C#) vào danh sách của bạn.

Answer 2

Asaf,

Bạn đang yêu cầu chúng tôi đánh giá thuật toán của bạn, nhưng bạn không giải thích thuật toán của mình - ngay cả trong nhận xét mã. Vì vậy, bạn muốn tất cả mọi người dành một giờ hoặc hơn kỹ thuật đảo ngược thuật toán từ mã, chỉ để chúng tôi có thể hiểu câu hỏi của bạn trước khi chúng tôi trả lời nó?

Vui lòng chỉnh sửa câu hỏi của bạn để giải thích thuật toán của bạn.

Có một điều hiển nhiên - dấu chân bộ nhớ của mã của bạn là khủng khiếp. Đối với các giá trị khiêm tốn của n, số lượng combinatations sẽ dễ dàng ở hàng tỷ, điều này đòi hỏi nhiều bộ nhớ hơn hầu hết các máy tính có. Ngoài ra, bạn đang sử dụng mảng được tạo động, giúp giữ lại và sao chép chính chúng khi chúng phát triển.Cộng với chương trình của bạn tạo ra các tập hợp con trong các mảng khác nhau và hợp nhất chúng. Tất cả trong tất cả, chương trình của bạn sẽ đòi hỏi nhiều lần số lượng bộ nhớ sẽ là lý tưởng cần thiết để lưu trữ danh sách, và nó sẽ dành phần lớn thời gian của nó chỉ là sao chép dữ liệu qua lại.

Nếu bạn phải có tất cả các giá trị trong một mảng cùng một lúc, ít nhất là bắt đầu bằng cách tính toán kích thước của mảng bạn cần - n!/(n-k)!/k! - và sau đó chỉ cần điền nó vào.

Thậm chí tốt hơn sẽ là mã "lười biếng" chỉ tính mỗi thành viên của chuỗi khi cần thiết. Xem this question from the related questions sidebar

Answer 3

Trong C++ đưa ra sau thói quen:

template <typename Iterator> 
inline bool next_combination(const Iterator first, Iterator k, const Iterator last) 
{ 
    /* Credits: Thomas Draper */ 
    if ((first == last) || (first == k) || (last == k)) 
     return false; 
    Iterator itr1 = first; 
    Iterator itr2 = last; 
    ++itr1; 
    if (last == itr1) 
     return false; 
    itr1 = last; 
    --itr1; 
    itr1 = k; 
    --itr2; 
    while (first != itr1) 
    { 
     if (*--itr1 < *itr2) 
     { 
     Iterator j = k; 
     while (!(*itr1 < *j)) ++j; 
     std::iter_swap(itr1,j); 
     ++itr1; 
     ++j; 
     itr2 = k; 
     std::rotate(itr1,j,last); 
     while (last != j) 
     { 
      ++j; 
      ++itr2; 
     } 
     std::rotate(k,itr2,last); 
     return true; 
     } 
    } 
    std::rotate(first,k,last); 
    return false; 
} 

Sau đó bạn có thể tiến hành làm như sau:

std::string s = "123456789"; 
std::size_t k = 3; 
do 
{ 
    std::cout << std::string(s.begin(),s.begin() + k) << std::endl; 
} 
while(next_combination(s.begin(),s.begin() + k,s.end())); 

Answer 4

anh chàng này dường như đã làm việc nghiêm túc trong tổ hợp sử dụng C# (CodeProject):

Permutations, Combinations, and Variations using C# Generics