hoán vị duy nhất không lặp lại nhân đôi hoặc vòng tròn

Question

Một số nền: Tôi đang viết một thuật toán tìm kiếm vũ lực nhiều hơn hoặc ít hơn để giải quyết một vấn đề mà tôi có. Để làm được điều này, tôi cần phải tạo và đánh giá tất cả các khả năng để tìm ra điều tốt nhất. Kể từ khi đánh giá thực sự mất một thời gian tôi muốn tạo ra càng ít càng tốt các giải pháp hoàn toàn bao gồm không gian tìm kiếm của tôi. Hơn nữa, càng có nhiều yếu tố tôi có thể làm điều này càng tốt. Đối với bất kỳ số K có bình thường K! hoán vị, và tạo ra tất cả chúng sẽ khó cho số cao hơn ~ 10.

Bất vấn đề: Không gian tìm kiếm nên chứa tất cả các hoán vị của hai yếu tố (N lần el1 và M lần el2, trong đó K = M + N), với những hạn chế:

1. họ phải là duy nhất (tức là tôi chỉ muốn [aabbb] một lần)
2. Tôi không cần đảo ngược bất kỳ hoán vị nào (ví dụ: nếu tôi có [aab], tôi cũng không cần [baa])
3. Tôi xem xét các hoán vị sẽ là tròn, do đó [aab] = [aba] = [baa]

Nếu tôi có thể làm điều này, số lượng khả năng sẽ giảm đáng kể. Vì K sẽ lý tưởng là lớn, đầu tiên không thể tạo ra tất cả các hoán vị và sau đó lọc chúng theo các tiêu chí này. Tôi đã thực hiện hạn chế đầu tiên (xem bên dưới) và nó cắt giảm số từ 2^K cho hàm hoán vị bình thường của Matlab (perms) thành K!/N! M !, đó là một chiến thắng lớn. Hạn chế thứ hai sẽ chỉ cắt giảm số lượng khả năng trong một nửa (trong trường hợp tốt nhất), nhưng tôi nghĩ rằng thứ ba cũng sẽ có thể thực sự cắt giảm số lượng khả năng.

Nếu có ai biết cách thực hiện, và tốt nhất là cách tính số lượng khả năng sẽ có, điều đó sẽ giúp ích cho tôi rất nhiều! Tôi thích một lời giải thích, nhưng mã cũng tốt (tôi có thể đọc các ngôn ngữ như C, Java (Script), Python, Ruby, Lisp/Scheme).

---

Đối với các quan tâm: Đây là thuật toán cho việc hoán vị chỉ duy nhất mà tôi có cho đến nay:

function genPossibilities(n, m, e1, e2) 
    if n == 0 
     return array of m e2's 
    else 
     possibilities = genPossibilities(n-1, m, e1, e2) 
     for every possibility: 
      gain = number of new possibilities we'll get for this smaller possibility* 
      for i in max(0,(m+n-gain)) 
       if possibility(i) is not e1 
        add possiblity with e1 inserted in position i 
     return new possibilities 

• Nếu bạn có tất cả các hoán vị cho N-1 và M, sau đó bạn có thể sử dụng chúng để tìm các hoán vị cho N và M bằng cách chèn e1 vào chúng. Bạn không thể chỉ chèn ở khắp mọi nơi mặc dù, bởi vì sau đó bạn sẽ nhận được bản sao. Tôi không biết tại sao nó lại hoạt động, nhưng bạn có thể tính số lượng khả năng mới mà bạn sẽ tạo ra từ một cái cũ (tôi gọi đây là 'gain'). Con số này bắt đầu tại M + 1 cho hoán vị cũ đầu tiên và giảm một cho mỗi hoán vị cũ cho đến khi nó trở thành 0, tại thời điểm nó quay trở lại M, vv (chỉ hoạt động nếu M> = N). Vì vậy, nếu bạn muốn tính toán hoán vị cho N = 3 và M = 3 và bạn có 10 hoán vị cho N = 2 và M = 3, lợi ích của chúng sẽ là [4 3 2 1 3 2 1 2 1 1]. Trừ đi độ lợi này từ độ dài của hoán vị và bạn nhận được chỉ mục mà tại đó bạn có thể bắt đầu chèn các phần tử mới mà không tạo các bản sao.

Answer 1

Những gì bạn đang theo sau là một tập con của vòng đeo tay 2 vòng (bộ con được xác định bằng chính xác n của ký tự A và m của ký tự B). Tập hợp của tất cả các vòng đeo tay cho phép số lượng A và B thay đổi.

Đoạn mã sau in ra các chuỗi bạn đang theo dõi và thực hiện theo thứ tự từ vựng và trong thời gian khấu hao không đổi. Nó dựa trên thuật toán chung trong this paper by Sawada - để giải thích cách hoạt động, hãy xem bài báo đó.

#include <stdlib.h> 
#include <stdio.h> 

static int *a; 
static int n; 

void print_bracelet(int n, int a[]) 
{ 
    int i; 

    printf("["); 
    for (i = 0; i < n; i++) 
     printf(" %c", 'a' + a[i]); 
    printf(" ]\n"); 
} 

int check_rev(int t, int i) 
{ 
    int j; 

    for (j = i+1; j <= (t + 1)/2; j++) 
    { 
     if (a[j] < a[t-j+1]) 
      return 0; 
     if (a[j] > a[t-j+1]) 
      return -1; 
    } 

    return 1; 
} 

void gen_bracelets(int n_a, int n_b, int t, int p, int r, int u, int v, int rs) 
{ 
    if (2 * (t - 1) > (n + r)) 
    { 
     if (a[t-1] > a[n-t+2+r]) 
      rs = 0; 
     else if (a[t-1] < a[n-t+2+r]) 
      rs = 1; 
    } 
    if (t > n) 
    { 
     if (!rs && (n % p) == 0) 
      print_bracelet(n, a + 1); 
    } 
    else 
    { 
     int n_a2 = n_a; 
     int n_b2 = n_b; 

     a[t] = a[t-p]; 

     if (a[t] == 0) 
      n_a2--; 
     else 
      n_b2--; 

     if (a[t] == a[1]) 
      v++; 
     else 
      v = 0; 

     if ((u == (t - 1)) && (a[t-1] == a[1])) 
      u++; 

     if ((n_a2 >= 0) && (n_b2 >= 0) && !((t == n) && (u != n) && (a[n] == a[1]))) 
     { 
      if (u == v) { 
       int rev = check_rev(t, u); 

       if (rev == 0) 
        gen_bracelets(n_a2, n_b2, t + 1, p, r, u, v, rs); 

       if (rev == 1) 
        gen_bracelets(n_a2, n_b2, t + 1, p, t, u, v, 0); 
      } 
      else 
       gen_bracelets(n_a2, n_b2, t + 1, p, r, u, v, rs); 
     } 

     if (u == t) 
      u--; 

     if (a[t-p] == 0 && n_b > 0) 
     { 
      a[t] = 1; 

      if (t == 1) 
       gen_bracelets(n_a, n_b - 1, t + 1, t, 1, 1, 1, rs); 
      else 
       gen_bracelets(n_a, n_b - 1, t + 1, t, r, u, 0, rs); 
     } 
    } 
} 

int main(int argc, char *argv[]) 
{ 
    int n_a, n_b; 

    if (argc < 3) 
    { 
     fprintf(stderr, "Usage: %s <a> <b>\n", argv[0]); 
     return -2; 
    } 

    n_a = atoi(argv[1]); 
    n_b = atoi(argv[2]); 

    if (n_a < 0 || n_b < 0) 
    { 
     fprintf(stderr, "a and b must be nonnegative\n"); 
     return -3; 
    } 

    n = n_a + n_b; 
    a = malloc((n + 1) * sizeof(int)); 

    if (!a) 
    { 
     fprintf(stderr, "could not allocate array\n"); 
     return -1; 
    } 

    a[0] = 0; 

    gen_bracelets(n_a, n_b, 1, 1, 0, 0, 0, 0); 

    free(a); 
    return 0; 
} 

Answer 2

Nếu bạn chỉ có hai phần tử, không gian của bạn nhỏ hơn nhiều: 2^k thay vì k !.

Hãy thử một cách tiếp cận như thế này:

1. Chạy qua tất cả các số từ 1 đến 2^k.
2. Viết số ở dạng nhị phân.
3. Dịch tất cả 0 sang a và 1 sang b. Bây giờ bạn có một hoán vị.
4. Lấy chuỗi của bạn và tạo chuỗi 2k theo hoán vị theo chu kỳ và đảo ngược. Bạn chỉ cần đánh giá 1 trong số các chuỗi 2k này.
5. Trong số các chuỗi 2k, hãy chọn trình tự sắp xếp theo thứ tự bảng chữ cái đầu tiên.
6. Kiểm tra nhật ký của bạn để xem bạn đã làm điều này chưa. Nếu có, bỏ qua.
7. Nếu cái này mới, hãy đánh giá nó và thêm vào nhật ký "đã hoàn tất". (Nếu không gian cho phép, bạn có thể thêm tất cả các phần tử 2k của "gia đình" vào nhật ký đã hoàn tất, vì vậy bạn có thể di chuyển bước (6) sang phải sau bước (3). và b của, trong "thực hiện" đăng nhập.)

Nếu bạn có j những biểu tượng có thể, thay vì chỉ hai, thực hiện tương tự nhưng sử dụng j cơ sở chứ không phải là cơ sở 2.

Answer 3

bạn đang tìm kiếm kết hợp - thứ tự độc lập. Matlab tính toán chính xác với K!/N! M! đó chính xác là công thức để tính toán số lượng kết hợp.

Answer 4

Giả sử bạn có một mảng của tất cả các hoán vị, bạn có thể đặt nội dung của mảng vào một băm. Sau đó, điều này sẽ làm việc (một lực lượng nhỏ vũ phu, nhưng một sự khởi đầu của nó):

for each (element in array of permutations){ 
    if (element exists in hash){ 
    remove each circular permutation of element in hash except for element itself 
    } 
} 

Answer 5

Tôi nghĩ rằng bạn muốn tạo ra dây chuyền miễn phí 2-ary. Xem this question để biết liên kết, giấy tờ và một số mã.