미러링 또는 순환 반복이없는 고유 순열

Question

일부 배경 : 내가 가지고있는 문제를 해결하기 위해 다소 힘이있는 검색 알고리즘을 작성하고 있습니다. 이렇게하기 위해서는 어떤 것이 가장 적합한 지 알아 내기 위해 모든 가능성을 생성하고 평가해야합니다. 평가에는 실제로 약간의 시간이 걸리기 때문에 가능한 한 적은 수의 솔루션을 생성하여 내 검색 공간을 완전히 커버하는 것을 선호합니다. 또한, 더 많은 요소를 위해이 작업을 수행 할 수 있습니다. 어떤 숫자 K에 대해서도 보통 K가 있습니다! 순열, 그리고 그들을 모두 생성하는 것은 ~ 10보다 높은 숫자의 경우 어려울 것입니다.

실제 문제 : 검색 공간이 제한 두 가지 요소의 모든 순열 (K = M + N은 EL1 N 시간과 M의 배 EL2)이 포함되어 있어야합니다

1. 가 고유 할 필요를 (즉, 단 하나만 [aabbb]을 원한다면)
2. 순열이 필요 없다 (예 : [aab]가있는 경우, [baa]도 필요하지 않음)
3. 순열이 원형이므로 [aab] = [aba] = [baa]

이렇게 할 수 있다면 가능성이 크게 줄어들 것입니다. K가 이상적으로 크기 때문에 모든 순열을 먼저 생성 한 다음 이러한 기준에 따라 필터링을 수행하는 것은 불가능합니다. 나는 이미 첫 번째 제한 (아래 참조)을 수행했으며 Matlab의 정규 순열 함수 (perms)를 2^K에서 K!/N! M!으로 줄였습니다. 이는 엄청난 승리입니다. 두 번째 제한은 가능한 경우의 수를 절반으로 줄이는 것이지만, 세 번째 방법은 가능성의 수를 줄일 수 있어야한다고 생각합니다.

누구나 할 수있는 방법을 알고 있고 가능한 한 많은 가능성을 계산하는 방법을 알고 있다면 많은 도움이됩니다. 설명을 선호하지만 코드도 훌륭합니다 (C와 유사한 언어, Java (Script), Python, Ruby, Lisp/Scheme을 읽을 수 있습니다). 관심 들어

---

: 당신은 N-1과 M의 모든 순열이있는 경우

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과 M에 대한 순열을 e1을 삽입하여 찾는다. 당신은 단지 어디에서나 삽입 할 수 없습니다, 왜냐하면 당신은 중복을 얻을 것이기 때문입니다. 이것이 작동하는 이유는 모르겠지만 이전의 것에서 생성 할 수있는 새로운 가능성의 수를 계산할 수 있습니다 (저는 이것을 '이득'이라고 부릅니다). 이 숫자는 첫 번째 이전 순열에 대해 M + 1에서 시작하고 이전 순열에 대해 1 씩 감소하여 0이 될 때까지, 그 시점에서 M 등으로 돌아갑니다 (M> = N 인 경우에만 작동 함). 따라서 N = 3과 M = 3에 대한 순열을 계산하려면 N = 2와 M = 3에 대해 10 개의 순열을 사용하면 그 이득은 [4 3 2 1 3 2 1 2 1 1]이됩니다. 이 이득을 순열의 길이에서 빼면 중복을 만들지 않고 새 요소 삽입을 시작할 수있는 색인이 생성됩니다.

Answer 1

뒤에 오는 것은 2-ary 팔찌의 부분 집합입니다 (이 부분 집합은 문자 n의 정확히 n 개와 문자 B의 m으로 정의됩니다). 집합이 모두 팔찌는 A와 B의 수가 다를 수 있습니다.

다음 코드는 어순 순서와 일정 상각 시간으로 사용자가 수행 한 시퀀스를 인쇄합니다. this paper by Sawada에있는 일반 알고리즘을 기반으로합니다 - 작동 방식에 대한 설명은 해당 문서를 참조하십시오.

#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

두 개의 요소 만있는 경우 공간이 훨씬 작습니다. k!가 아니라 2^k입니다. 2^K 1에서 모든 숫자를 통해

1. 실행 :

   는이 같은 방법을 사용해보십시오.

2. 숫자를 이진 형식으로 작성하십시오.
3. 모든 0을 a 및 1을 b로 변환하십시오. 이제 당신은 순열을가집니다.
4. 시퀀스를 가져 와서 순환 순열 및 역전으로 2k 시퀀스를 생성하십시오. 이 2k 시퀀스 중 1 개만 평가하면됩니다.
5. 2k 시퀀스 중에서 알파벳순으로 정렬하는 시퀀스를 선택하십시오.
6. 로그를 확인하여 이미 완료했는지 확인하십시오. 그렇다면 건너 뜁니다.
7. 새로운 것이면 그것을 평가하고 "완료"된 로그에 추가하십시오. (공간이 허락한다면 "family"의 모든 2k 요소를 완료 로그에 추가 할 수 있으므로 단계 (6)을 단계 (3) 직후로 이동할 수 있습니다. 또한 a의 순서가 아닌 번호를 저장할 수도 있습니다 가 "완료"당신이 J 가능한 문자가있는 경우와 b의, 같은 일을 오히려 두보다).

를 기록하지만 당신이 찾고있는 기본 J보다는 기본 2

Answer 3

를 사용 조합 - 순서에 독립적입니다. Matlab은 이것을 K!/N! M! 이것은 조합 수를 계산하기위한 공식입니다.

Answer 4

모든 순열의 배열을 가지고 있다고 가정하면 배열의 내용을 해시에 넣을 수 있습니다. 그런 다음이 (작은 짐승 힘, 그러나 그것의 시작)를 작동합니다

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

나는 당신이 2 진 무료 목걸이를 생성 할 생각합니다. 링크, 논문 및 일부 코드는 this question을 참조하십시오.