트위스트를 사용하여 선형 시간의 순열을 계산하는 방법

StackOverflow https://stackoverflow.com/questions/483890

  •  20-08-2019
  •  | 
  •  

문제

Java에서 순서를 지정해야 하는 리소스 예약 문제가 있지만 서로 옆에 있을 수 있는 리소스에는 제한이 있습니다.좋은 비유는 특정 숫자만 서로 옆에 있을 수 있는 "숫자"의 문자열입니다.내 솔루션은 재귀적이었고 작은 문자열에는 잘 작동하지만 런타임은 O(X^N)입니다. 여기서 X는 가능한 자릿수(기본)이고 N은 문자열의 길이입니다.금방 관리할 수 없게 됩니다.

아래 호환성 매트릭스를 사용하여 허용되는 문자열의 몇 가지 예는 다음과 같습니다.
1의 길이:0, 1, 2, 3, 4
2의 길이:02, 03, 14, 20, 30, 41
3의 길이:020, 030, 141, 202, 203, 302, 303, 414

     0  1  2  3  4
   ---------------------
0|  0  0  1  1  0
1|  0  0  0  0  1
2|  1  0  0  0  0
3|  1  0  0  0  0
4|  0  1  0  0  0

길이가 N인 모든 문자열을 세기 위한 내 솔루션은 빈 문자열로 시작하여 첫 번째 숫자를 치환하고 길이가 N-1인 모든 문자열에 대해 재귀 호출을 수행하는 것입니다.재귀 호출은 추가된 마지막 숫자를 확인하고 해당 숫자 옆에 있을 수 있는 모든 순열을 시도합니다.매번 00, 01, 04를 바꾸려고 시도하지 않도록 몇 가지 최적화가 이루어졌습니다. 예를 들어 02, 03만 있지만 기본 5(예제)에서 기본 4000으로 확장되므로 성능은 여전히 ​​좋지 않습니다.

순열을 모두 열거하는 것 외에 순열을 계산하는 더 좋은 방법에 대한 생각이 있습니까?

도움이 되었습니까?

해결책

특정 길이의 문자열 수만 원할 경우 호환성 매트릭스에 몇 번 곱하고 그 값을 합산하면 됩니다.

N = 문자열의 길이
ㅏ = 호환성 매트릭스
가능한 문자열 수 = 합계 ㅏN-1

몇 가지 예:

n = 1
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 1 0 |
| 0 0 0 0 1 |
sum: 5

n = 3
| 2 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 1 0 |
| 0 0 1 1 0 |
| 0 0 0 0 1 |
sum: 8

n = 8
| 0 0 8 8 0 |
| 0 0 0 0 1 |
| 8 0 0 0 0 |
| 8 0 0 0 0 |
| 0 1 0 0 0 |
sum: 34

원래 행렬(행 나, 열 제이)는 기호로 시작하는 문자열의 수로 생각할 수 있습니다. 나, 이고 다음 기호는 기호입니다. 제이.또는 길이의 문자열 수로 볼 수도 있습니다. 2, 기호로 시작 나 그리고 기호로 끝남 제이.

행렬 곱셈은 이 불변성을 유지하므로 지수화 후에는 ㅏN-1 기호로 시작하는 문자열의 개수를 포함합니다. 나, 길이가 있음 N, 기호로 끝납니다. 제이.

보다 위키피디아:제곱에 의한 지수화 행렬 거듭제곱을 더 빠르게 계산하기 위한 알고리즘입니다.

(stefan.ciobaca에게 감사드립니다)

이 특정 사례는 다음 공식으로 축소됩니다.

가능한 문자열 수 = 에프(N) = 4 + Σ케이=1..N 2⌊케이-1⁄2⌋ = 에프(N-1) + 2⌊N-1⁄2⌋

n       f(n)
----    ----
   1       5
   2       6
   3       8
   4      10
   5      14
   6      18
   7      26
   8      34
   9      50
  10      66

다른 팁

주어진 행렬의 규칙을 사용하여 주어진 길이의 문자열을 몇 개나 만들 수 있는지 알고 싶으십니까?그렇다면 다음과 같은 접근 방식이 작동합니다.

n = 5
maxlen = 100

combine = [
      [0, 0, 1, 1, 0],
      [0, 0, 0, 0, 1],
      [1, 0, 0, 0, 0],
      [1, 0, 0, 0, 0],
      [0, 1, 0, 0, 0]
   ]

# counts of strings starting with 0,1,...,4, initially for strings of length one:
counts = [1, 1, 1, 1, 1]

for size in range(2, maxlen+1):
   # calculate counts for size from count for (size-1)
   newcount = []
   for next in range(n):
      total = 0
      for head in range(n):
         if combine[next][head]:
            # |next| can be before |head|, so add the counts for |head|
            total += counts[head]
      # append, so that newcount[next] == total
      newcount.append(total)
   counts = newcount
   print "length %i: %i items" % (size, sum(counts))

귀하의 알고리즘이 최적인 것 같습니다.

이러한 순열을 어떻게 사용하고 있나요?하나의 목록에 쌓아두시나요, 아니면 하나씩 사용하시나요?이러한 순열이 엄청나게 많기 때문에 메모리 사용량이 많아서(모두 수집하는 경우) 성능이 저하되거나 시간이 너무 많이 걸릴 수 있습니다.사소한 시간에 수십억 개의 루프를 수행할 수는 없습니다.

댓글에 답장:

단지 개수를 세고 싶다면 동적 프로그래밍을 사용할 수 있습니다.

count[n][m]을 배열로 가정합니다. 여기서 count[l][j]는 길이가 l이고 j로 끝나는 순열의 수입니다.

그러면 count[l][i] = count[l-1][i1]+count[l-1][i2]+..., 여기서 i1, i2, ...i 앞에 올 수 있는 숫자입니다(미리 계산된 배열에 저장할 수 있음).

count의 모든 셀은 K개 숫자(K는 호환 행렬에 따라 다름)를 합산하여 채울 수 있으므로 복잡도는 O(KMN)이고 M은 순열의 길이이며 N은 총 자릿수입니다.

아마도 나는 이것을 이해하지 못할 수도 있지만, 각 숫자에 대해 따라올 수 있는 유효한 숫자 목록이 있는 목록 테이블을 가짐으로써 이것이 제공되지 않을까요?

그런 다음 생성할 루틴은 누적된 결과, 숫자 및 현재 숫자를 사용합니다.다음과 같은 것 :

// not really Java - and you probably don't want chars, but you'll fix it
void GenerateDigits(char[] result, int currIndex, char currDigit)
{
    if (currIndex == kMaxIndex) {
        NotifyComplete(result);
        return;
    }
    char[] validFollows = GetValidFollows(currDigit); // table lookup
    foreach (char c in validFollows) {
        result[currIndex] = c;
        GenerateDigits(result, currIndex+1, c);
    }
}

생성할 자릿수의 함수에 따라 복잡성이 증가하지만 해당 기능은 한 자릿수에 대한 유효한 팔로어의 총 수에 따라 달라집니다.다음의 총 수가 모든 자릿수에 대해 동일하다면, 즉 k라고 가정하면 가능한 모든 순열을 생성하는 시간은 O(k^n)이 될 것입니다. 여기서 n은 자릿수입니다.죄송합니다. 수학을 변경할 수 없습니다.10진법에서 n자리 숫자를 생성하는 데 걸리는 시간은 10^n입니다.

나는 당신이 무엇을 요구하는지 정확히 모르겠지만 잠재적으로 n이 있기 때문에!n자리 문자열의 순열을 사용하면 n!보다 빠르게 나열할 수 없습니다.O(n^2)의 런타임을 어떻게 얻었는지 정확히 모르겠습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top