n-th hoặc Kết hợp tùy ý của một tập hợp lớn

Question

Giả sử tôi có một tập hợp các số từ [0, ....., 499]. Các kết hợp hiện đang được tạo tuần tự bằng cách sử dụng C++ std::next_permutation. Để tham khảo, kích thước của mỗi tuple tôi kéo ra là 3, vì vậy tôi đang trả về kết quả tuần tự như [0,1,2], [0,1,3], [0,1,4], ... [497,498,499].

Bây giờ, tôi muốn song song mã mà mã này đang ngồi, do đó việc tạo các kết hợp này sẽ không còn hoạt động theo tuần tự nữa. Có bất kỳ thuật toán hiện tại nào để tính toán kết hợp ith của 3 từ 500 số không?

Tôi muốn đảm bảo rằng mỗi chuỗi, bất kể vòng lặp của vòng lặp nhận được, có thể tính toán kết hợp độc lập dựa trên số i đang lặp lại. Vì vậy, nếu tôi muốn kết hợp cho i=38 trong chuỗi 1, tôi có thể tính toán [1,2,5] trong khi đồng thời tính toán i=0 trong chuỗi 2 dưới dạng [0,1,2].

EDIT Dưới đây tuyên bố là không thích hợp, tôi trộn lẫn bản thân mình lên

tôi đã xem xét thuật toán sử dụng thừa để thu hẹp mỗi yếu tố cá nhân từ trái sang phải, nhưng tôi không thể sử dụng các như 500! chắc chắn sẽ không phù hợp với trí nhớ. Bất kỳ đề xuất?

Answer 1

Đây là bắn tôi:

int k = 527; //The kth combination is calculated 
int N=500; //Number of Elements you have 
int a=0,b=1,c=2; //a,b,c are the numbers you get out 

while(k >= (N-a-1)*(N-a-2)/2){ 
    k -= (N-a-1)*(N-a-2)/2; 
    a++; 
} 
b= a+1; 
while(k >= N-1-b){ 
    k -= N-1-b; 
    b++; 
} 

c = b+1+k; 


cout << "["<<a<<","<<b<<","<<c<<"]"<<endl; //The result 

Got suy nghĩ này về bao nhiêu tổ hợp có cho đến khi số tiếp theo được tăng lên. Tuy nhiên nó chỉ hoạt động cho ba yếu tố. Tôi không thể đảm bảo rằng nó là chính xác. Sẽ được mát mẻ nếu bạn so sánh nó với kết quả của bạn và đưa ra một số thông tin phản hồi.

Answer 2

Bạn có thể mô tả lựa chọn cụ thể 3 trong số 500 đối tượng dưới dạng số ba (i, j, k), trong đó i là số từ 0 đến 499 (chỉ số của số đầu tiên), j trong khoảng từ 0 đến 498 (chỉ số của thứ hai, bỏ qua số nào trước tiên) và k nằm trong khoảng từ 0 đến 497 (chỉ mục của số cuối cùng, bỏ qua cả số đã chọn trước đó). Do đó, thực sự dễ dàng liệt kê tất cả các lựa chọn có thể có: bắt đầu bằng (0,0,0), tăng k cho đến khi giá trị lớn nhất, sau đó tăng j và đặt lại k thành 0 và cứ như vậy, cho đến j đạt giá trị tối đa. vào, cho đến khi j nhận giá trị tối đa của riêng nó; sau đó tăng i và đặt lại cả j và k và tiếp tục. Nếu mô tả này nghe có vẻ quen thuộc, đó là vì nó chính xác giống như cách tăng số cơ sở-10 hoạt động, ngoại trừ cơ sở là funkier nhiều hơn, và trên thực tế, cơ sở thay đổi từ chữ số sang chữ số. Bạn có thể sử dụng cái nhìn sâu sắc này để thực hiện một phiên bản rất nhỏ gọn của ý tưởng: đối với bất kỳ số nguyên n 0-500 * 499 * 498, bạn có thể nhận được:

struct { 
    int i, j, k; 
} triple; 

triple AsTriple(int n) { 
    triple result; 
    result.k = n % 498; 
    n = n/498; 
    result.j = n % 499; 
    n = n/499; 
    result.i = n % 500; // unnecessary, any legal n will already be between 0 and 499 
    return result; 
} 

void PrintSelections(triple t) { 
    int i, j, k; 
    i = t.i; 
    j = t.j + (i <= j ? 1 : 0); 
    k = t.k + (i <= k ? 1 : 0) + (j <= k ? 1 : 0); 
    std::cout << "[" << i << "," << j << "," << k << "]" << std::endl; 
} 

void PrintRange(int start, int end) { 
    for (int i = start; i < end; ++i) { 
    PrintSelections(AsTriple(i)); 
    } 
} 

Bây giờ vào phân đoạn, bạn có thể chỉ cần lấy số điện thoại từ 0 đến 500 * 499 * 498, chia chúng thành các trang con theo bất kỳ cách nào bạn muốn và có mỗi phân đoạn tính toán hoán vị cho mỗi giá trị trong phân đoạn của nó.

Thủ thuật này rất tiện lợi cho bất kỳ vấn đề nào bạn cần liệt kê các tập con.

Answer 3

Nếu bạn đang tìm cách lấy chỉ mục từ vựng hoặc xếp hạng kết hợp duy nhất thay vì hoán vị, thì sự cố của bạn sẽ rơi vào hệ số nhị thức. Hệ số nhị thức xử lý các vấn đề về việc chọn các kết hợp duy nhất trong các nhóm K với tổng số N mục.

Tôi đã viết một lớp trong C# để xử lý các hàm phổ biến để làm việc với hệ số nhị thức.Nó thực hiện các tác vụ sau:

1. Xuất tất cả chỉ mục K ở định dạng đẹp cho bất kỳ N nào chọn K thành tệp. Chỉ số K có thể được thay thế bằng nhiều chuỗi hoặc chữ mô tả hơn.

2. Chuyển đổi chỉ mục K thành chỉ mục từ vựng thích hợp hoặc xếp hạng của mục nhập trong bảng hệ số nhị thức được sắp xếp. Kỹ thuật này nhanh hơn nhiều so với các kỹ thuật cũ được công bố dựa trên sự lặp lại. Nó thực hiện điều này bằng cách sử dụng một thuộc tính toán học vốn có trong Tam giác của Pascal và rất hiệu quả so với việc lặp qua tập hợp.

3. Chuyển đổi chỉ mục trong bảng hệ số nhị thức đã sắp xếp thành chỉ mục K tương ứng. Tôi tin rằng nó cũng nhanh hơn các giải pháp lặp cũ.

4. Sử dụng phương pháp Mark Dominus để tính hệ số nhị thức, ít có khả năng tràn và hoạt động với số lớn hơn.

5. Lớp học được viết bằng .NET C# và cung cấp cách quản lý các đối tượng liên quan đến sự cố (nếu có) bằng cách sử dụng danh sách chung. Hàm khởi tạo của lớp này nhận giá trị bool được gọi là InitTable, khi đúng sẽ tạo một danh sách chung để giữ các đối tượng được quản lý. Nếu giá trị này là sai, thì nó sẽ không tạo bảng. Bảng không cần phải được tạo ra để sử dụng 4 phương pháp trên. Các phương thức Accessor được cung cấp để truy cập vào bảng.

6. Có một lớp thử nghiệm được liên kết hiển thị cách sử dụng lớp và các phương pháp của lớp. Nó đã được thử nghiệm rộng rãi với 2 trường hợp và không có lỗi nào được biết đến.

Để đọc về lớp này và tải xuống mã, hãy xem Tablizing The Binomial Coeffieicent.

Mã thử nghiệm sau đây sẽ lặp qua từng kết hợp độc đáo:

public void Test10Choose5() 
{ 
    String S; 
    int Loop; 
    int N = 500; // Total number of elements in the set. 
    int K = 3; // Total number of elements in each group. 
    // Create the bin coeff object required to get all 
    // the combos for this N choose K combination. 
    BinCoeff<int> BC = new BinCoeff<int>(N, K, false); 
    int NumCombos = BinCoeff<int>.GetBinCoeff(N, K); 
    // The Kindexes array specifies the indexes for a lexigraphic element. 
    int[] KIndexes = new int[K]; 
    StringBuilder SB = new StringBuilder(); 
    // Loop thru all the combinations for this N choose K case. 
    for (int Combo = 0; Combo < NumCombos; Combo++) 
    { 
     // Get the k-indexes for this combination. 
     BC.GetKIndexes(Combo, KIndexes); 
     // Verify that the Kindexes returned can be used to retrive the 
     // rank or lexigraphic order of the KIndexes in the table. 
     int Val = BC.GetIndex(true, KIndexes); 
     if (Val != Combo) 
     { 
     S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString(); 
     Console.WriteLine(S); 
     } 
     SB.Remove(0, SB.Length); 
     for (Loop = 0; Loop < K; Loop++) 
     { 
     SB.Append(KIndexes[Loop].ToString()); 
     if (Loop < K - 1) 
      SB.Append(" "); 
     } 
     S = "KIndexes = " + SB.ToString(); 
     Console.WriteLine(S); 
    } 
} 

Bạn sẽ có thể cổng lớp này qua khá dễ dàng để C++. Có thể bạn sẽ không phải chuyển qua phần chung của lớp để đạt được mục tiêu của mình. Trường hợp thử nghiệm của bạn là 500 chọn 3 sản lượng 20,708,500 kết hợp độc đáo, mà sẽ phù hợp trong một int 4 byte. Nếu 500 chọn 3 chỉ đơn giản là một trường hợp ví dụ và bạn cần phải chọn các kết hợp lớn hơn 3, thì bạn sẽ phải sử dụng thời gian dài hoặc có thể là điểm cố định int.