주어진 모든 문자열 회의를 열거합니다

Question

효과적인 알고리즘과 더 많은 정보를 얻을 수 있도록 다음 클래스의 문제의 이름을 찾고 있습니다.

{-1, 0, 1}의 세 문자가있는 알파벳이 있습니다.

주로 {0}이지만 특정 패턴으로 분포 된 0 ~ 8 {1, -1} 문자가있는 길이 24의 모든 문자열을 효과적으로 생성해야합니다. (패턴은 {-1}의 숫자와 페어링에 대한 제한을 포함합니다). 내 기준을 충족하는 총 숫자 문자열은 약 128,000입니다.

그렇다면이 클래스의 문제/알고리즘의 이름은 무엇입니까?

Answer 1

이것에 대해 잘 정의 된 "알고리즘 클래스"가 있는지 확실하지 않습니다. 그것은 단지 조합에서 운동 일뿐입니다. 세 단계로 세대를 수행 할 수 있습니다.

1. 8 개 이하의 비트 세트로 24 비트 숫자를 모두 생성합니다 (일부 조회 테이블을 전제하면 약간의 속도를 높일 수 있습니다).
2. N 비트 세트가있는 각 24 비트 번호에 대해 모든 N 비트 번호를 반복하십시오.
3. N- 비트 숫자의 kth 비트가 0이면 24 비트 번호 인쇄물의 kth 세트 비트는 -1로 인쇄하고 그렇지 않으면 1으로 인쇄합니다.

2-3 단계를 조금 더 잘 설명하려면 24 비트 번호가 4 비트 세트가 있고

0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0

그런 다음 16 개의 4 비트 숫자를 모두 반복합니다. 0 0 0 0 에게 1 1 1 1, 예를 들어 :

0 0 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 0 0 0 0
0 1 1 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0 -1 0 0 0 0
0 1 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1 -1 0 0 0 0 0 -1 0 0 0 0
1 1 1 1 gives the string  0 0 0  1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0  1 0 0 0 0

Answer 2

이것을 한 번만 해결해야한다면, 아마도 무차별들을 강제하고 결과를 응용 프로그램에 조회 테이블에 넣을 수 있습니다. 확인할 0,1, -1의 24 비트 시퀀스 미만이 있습니다.

아마도 수학 잘못을 잘못하고 있거나 런타임에 문제를 동적으로 해결해야한다면, 문제를 각각 -1, 0, 1으로 제한된 24 개의 변수 시스템으로 간주하고이를 제약 만족도 문제, 당신이 어떤 식 으로든 당신의 제약을 열거 할 수 있다고 가정합니다. 그러나 내 관심사는 모두 솔루션은 서브 세트뿐만 아니라 문제 공간을 철저하게 검색하고있을 수 있습니다.

이 논문은 골목길 바로 위에있는 것 같습니다. 제약 만족도 문제에 대한 모든 솔루션을 열거합니다. 논문의 전체 텍스트에 액세스 할 수는 없지만 도움이되는지 확인하십시오.

나는 잘못된 나무를 함께 짖을 수도 있지만 아마도 이것은 아마도 출발점 일 것입니다.

Answer 3

작업 코드가 연구 논문과 연결되는 경향이 있기 때문에 마지막으로부터 완전히 분리 된 답변은이 코드를 찾았습니다. 물리학 포럼 그리고 직접 신용을 얻을 수 없으며, G ++ 아래로 컴파일되어 상수로 변경하여 24 비트로 8 비트를 찾아서 8 비트를 켜고 735,000 개에 불과합니다. 이들의. 이 '템플릿'은 0이 아닌 캐릭터에 대한 유일한 유효한 패턴을 보여줍니다. 그런 다음이 735,000 개의 답변 각각을 취하고 -/+ 표지판 주위를 던지고 각각이 기준을 충족하는지 결정해야하지만이 방법으로 2 천억 대신 735k 가능한 솔루션에서 시작합니다.

#include <stdio.h>

 int main()
 {
 int size = 24;
 int pop = 8;

 int n = ((1 << pop) - 1) << (size - pop);

 while(true) {
    printf( "%x\n",n);

    int lowest = n & -n;

     if(lowest > 1) {
        n = n ^ lowest ^ (lowest >> 1);
        continue;
     }

     int high = n & (n + lowest);
     if(high == 0) break;

     int low = n ^ high;

     low = (low << 2) + 3;

     while((low & high) == 0) low <<= 1;
     n = high ^ low;
  }
 }