모든 가능한 시퀀스를 열거

Question

문제 설명 : 우리는 주어진

1. T 번호 S1, S2의 집합 .... ST

2. 이 S1 (2 * 범위 + 1) (V)에 걸릴 수 있다는 것을 의미

범위

불리는 정수 012, 1, ..., S1 + Range) 마찬가지로 S2, ... ST는 2 * Range + 1 값을 취할 수있다.

문제 1 : 가능한 모든 시퀀스를 어떻게 열거합니까? 즉, 모든 (2 * 범위 -1)^T 시퀀스 (S1- 범위, S2, ... ST), S1- 범위 +1, S2, ... ST), ..... (S1, S2 -Range, S3, .... ST) 등

문제 2 : 합계가 S1 + S2 + ... + ST 인 순서 만 나열하려면 어떻게합니까? 1 문제

: 내가 고려하고 접근 방식은

for (i=0; i<pow(Range,T);i++) 
{ 
    Sequences that can be derived from i are 
    1. {Si + i mod pow(Range,i)} 
    2. {Si - i mod pow(Range,i)} 
} 

다른 더 우아한 솔루션을하는 것입니다?

또한 문제 2에 대한 아이디어가 있습니까?

Answer 1

# 1의 경우 한 가지 방법은 숫자를 증가시키는 것과 같이 생각하는 것입니다. 마지막 자릿수를 증가시키고 오버플로하면 초기 값 (0)으로 다시 설정하고 다음 자릿수를 증가시킵니다.

그래서 크기 T의 배열을 만든 다음 요소를 (S1- 범위, S2- 범위, ..., ST- 범위)로 초기화하십시오. 인쇄하십시오.

이제 마지막 값을 ST 범위 + 1로 증가시킵니다. 인쇄하십시오. ST + Range에 도달 할 때까지 증가 및 인쇄를 계속하십시오. 증분을 시도 할 때 ST 범위로 다시 재설정 한 다음 한 위치를 왼쪽으로 이동하고 증분합니다. 오버플로가 발생하면 반복하십시오. 끝까지 움직이면 완료됩니다. 그렇지 않으면 인쇄하십시오. # 2의

---

// Input: T, S[T], Range 
create V[T] 
for (i in 1..T): 
    V[i] = S[i] - Range 
loop forever { 
    print V 
    i = T 
    V[i]++ 
    while V[i] > S[i] + Range { 
     V[i] = S[i] - Range 
     i-- 
     if i < 1: 
      return // we're done 
     V[i]++ 
    } 
} 

, 그것은 조금 다릅니다. 설명을 위해 S의 값을 무시하고 각 위치에 대한 델타 (-Range, ..., 0, ..., + Range)의 포커스를 무시합니다.

sum (D) = 0이면 초기 값 집합은 (-Range, -Range, ..., + Range, + Range)입니다. T가 짝수이면 처음 절반은 -Range이고 나머지 절반은 + Range입니다. T가 홀수 인 경우, 중간 값은 0

지금 당신은 반복이 가고 싶은 방법에 대해 살펴입니다 :

-2 -2 0 2 2 
-2 -2 1 1 2 
-2 -2 1 2 1 
-2 -2 2 0 2 (A) 
-2 -2 2 1 1 
-2 -2 2 2 0 
-2 -1 -1 2 2 
-2 -1 0 1 2 
-2 -1 0 2 1 
-2 -1 1 0 2 

여기에서의 논리는 항상의 함수이기 때문에 당신이, 마지막 숫자를 건너 뛸 수 있다는 것입니다 다른 자릿수 증가시킬 수있는 가장 오른쪽 숫자를 증가시키고, 오른쪽으로 숫자를 재설정하여 sum (D) = 0을 제공하는 가능한 낮은 값으로 재설정하십시오.

로직은 좀 더 복잡하므로 재미있게 쓰도록하겠습니다.;-)

좋은 도우미 방법은 시작 델타가 주어진 특정 위치 이후의 숫자를 최대한 낮은 값으로 재설정하는 방법입니다. 그러면 reset(1, 0)을 호출하여 배열을 초기화 할 수 있습니다. 즉 시작 델타 0을 사용하여 위치 1을 재설정합니다.

그런 다음 A로 표시된 단계에서 D [3]을 2로 증가시킬 때 위의 경우 reset(4, -2)으로 전화합니다. 즉, 시작 델타 -2를 사용하여 4..5 위치를 재설정합니다. 마지막 숫자의 최대 값이 2 (범위) 인 경우 D [4]가 0보다 작을 수 없음을 의미합니다.