2013-02-25 26 views
11

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].n-th hoặc Kết hợp tùy ý của một tập hợp lớn

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?

+0

Hiển thị cho chúng tôi các tính toán liên quan đến giai thừa. Bạn có thể chỉ nhìn nó sai. Chắc chắn bạn sẽ chia một giai thừa thành một giai thừa khác, thường có nghĩa là đơn giản hóa là có thể. – paddy

+0

Tôi nghĩ tôi cần phải thuật lại câu hỏi của mình. Nó không chỉ là một hoán vị của 500 con số. Đó là một sự kết hợp của 3 trong số 500 có thể. Nhưng tôi muốn có thể chọn một sự kết hợp tùy ý trong số 500 chọn 3 có thể. – bgoers

+11

Có lẽ một cái gì đó như sau: http://code.google.com/p/strtk/source/browse/trunk/strtk.hpp#11622 – Gerdiner

Trả lời

5

Đâ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.

+0

Đơn giản, nhanh chóng, hoạt động như xa như tôi có thể nói. Tôi đã cố gắng nghĩ ra điều gì đó tương tự như những gì jacobm đã viết, nhưng tôi làm như thế này! – bgoers

0

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ả jk 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.

+0

Vấn đề duy nhất ở đây là tôi sẽ kết thúc với sự trùng lặp.Tôi cần 500 lựa chọn 3 kết hợp (trường hợp xấu nhất), đó là ~ 20 triệu kết hợp. Điều này xảy ra mà không có sự trùng lặp, do đó (0,0,0) được loại bỏ. Cảm ơn bạn mặc dù, tôi đánh giá cao câu trả lời! – bgoers

+0

Không, không có sự trùng lặp nào theo cách tôi mô tả. Bí quyết là trong cách giải thích: (0,0,0) đại diện cho các phần tử đầu tiên, thứ hai và thứ ba, vì mỗi số bạn bỏ qua tất cả các phần tử bạn đã chọn. – jacobm

+0

Ahhhh. Tôi hiểu rồi. Tôi sẽ kiểm tra nó một chút! – bgoers

1

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.

+0

Tôi chắc chắn sẽ xem xét điều này. 500 chọn 3 được đảm bảo là một trường hợp xấu nhất cho các thông số chúng tôi đang xem xét, vì vậy tôi không quá lo lắng về việc tràn. – bgoers

Các vấn đề liên quan