permuatation을 생성하기위한 메모 화

permutation을 생성하는 메모 기법을 사용하는 방법이 있습니까? 예를 들어, 숫자 1234에 대한 ...permuatation을 생성하기위한 메모 화

나를 위해 문제는 많은 메모리를 사용한다는 것입니다. 어느정도의 메모리 량으로 사용할 수 있습니까?

출처

2011-12-19 Abdul Samad

당신은 * 순열을 열거 *하는 법을 의미합니까? – wildplasser

임의의 문자열에 대해 n 개의 별개 문자 n으로 말하십시오. 순열이 존재하므로 필요한 공간이 커질 것이다. 순열을 열거 할 필요가 있다면, 저장하지 말고 각각을 계산할 때 각각을 직접 표시하십시오.

출처

2011-12-19 16:54:28 TimeToCodeTheRoad

만약 내가 그들을 저장하지 않고 그 때마다 나는 내가 이미 계산 한 것들을 다시 계산해야만 할 때마다 표시한다. –

물론 순열 생성을 위해 메모 생성을 사용할 수 있습니다 (거의 모든 다른 계산, 그것이 의미가있을 때). 구체적인 단계는 순열 생성 알고리즘에 따라 다릅니다. 예를 들어, 숫자 집합 (예 : {1, 2, 3, 4})이 있고 numbers의 하위 집합으로 된 재귀 호출 에 의해 모든 순열 집합 (이 숫자의 순서가 지정된 벡터, 예 : {[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], ...})을 반환하는 함수 perms(numbers)이있는 경우이 perms() 함수를 기억할 수 있습니다 직접. 이렇게하려면 맵으로 캐시를 작성하십시오. 여기서 키는 숫자 세트이며 값은 함수 호출의 결과입니다.

질문의 두 번째 부분 (메모리 관련). 자연에 의한 메모 작성은 많은 양의 메모리를 사용합니다. 어떤 종류의 고정 크기 캐시 (예 : LRU/LFU지도)를 사용하여이 금액을 수정할 수 있지만이 방법으로 메모 작성 개념이 깨져야하고 perms()에 대한 일부 호출은 두 번 이상 계속 계산됩니다.

출처

2011-12-19 17:42:17 ffriend

나는 당신의 요지를 가지고있다. 그러나 나는지도를 사용하는 생각이 맵으로 그리 좋지 않다고 생각한다. tales lgn (logarithmic) 주어진 키를 가진 원소를 검색하는 시간. –

@AbdulSamad :지도는 추상 데이터 유형입니다. 예를 들어 HashMap으로 구현 될 수 있으며 따라서 상환 된 O (1) (일정 시간)을 가져옵니다. 그리고 트리 구현으로도 대부분의 perms() 호출에서 더 빨라질 것입니다. – ffriend

순열을 연속적으로 생성하고 이들 모두를 동시에 필요로하지 않으려는 경우, 사전 순열을 반복하여 더 잘 수행 할 수 있습니다. 순열을 취하고 next permutation in lexicographic order을 반환하는 함수 nextPerm을 작성하십시오.

출처

2011-12-19 18:26:08 PengOne

permuatation을 생성하기위한 메모 화

답변

관련 문제