큰 순열 집합을 효과적으로 저장하는 방법은 무엇입니까?

Question

의 우리가 요소의 목록이 있다고 가정 해 봅시다 :

[{dog,1},{dog,2},{cat,1},{cat,2},{bird,1},{bird,2},...] 

내가 RAM이 목록의 모든 가능한 permutations를 저장하고 싶습니다.

목록이 꽤 길 수 있기 때문에 (10 개 요소 이상),이를 저장하는 데 많은 공간 (계승 N)이 필요합니다.

예를 들어 약 70 바이트의 공간을 소비하고 12 개의 요소가있는 목록이있는 경우 12! * 70 ~ 31 GB이 필요합니다. 목록에 하나 이상의 요소 만 추가하면 순열을 RAM에 저장하는 것이 불가능해질 수 있습니다.

다음 Erlang 표현보다 메모리에서 모든 순열을 유지하는 데 더 효율적인 표현이 있습니까?

[{dog,1},{dog,2},{cat,1},{cat,2},{bird,1},{bird,2},...] 

은 (I는 dog 원자는 원자 테이블에 한 번만 저장 것을 알고 있지만,이 모든 순열의 반복이기 때문에, N 메모리 소요).

어쩌면 이러한 순열은 일종의 바이트 표현으로 저장 될 수 있습니까? (죄송합니다, 저는 바이트와 바이너리로 초보자입니다).

결국, 이는 동일한 요소이지만 다른 방식으로 재 배열됩니다.

Answer 1

게으르지 않은 이유는 무엇입니까? 각 목록에서 색인을 유지하고 새 요소를 요청하면 즉시 조합을 생성합니다. 그렇게하면 언제든지 소스 요소의 초기 목록과 메모리의 인덱스 만 저장하면됩니다. (당신이 순열을 반복해야하는 경우) 예를 들어

:

-record(perm, {list_a, list_b, index_a, index_b}). 

매번 당신은 index_b의 최대에 도달, 당신은 0으로 재설정하고 하나 index_a를 증가. 그런 다음 목록의 N 번째 요소 (N은 인덱스)에 액세스하면 모든 순열 인스턴스를 다시 만들 수 있습니다.

물론 이것은 순열이 생성 될 때마다 목록을 탐색해야 함을 의미합니다. ,

-record(perm2, {list_a, list_b, list_b_orig}). 

다음 순열을 생성하려면 list_b에서 새 요소를 팝업 list_a의 머리에 추가 :이 문제를 방지하려면, 당신은 스스로와 indices으로 목록을 사용할 수 있습니다. list_b이 비어 있으면 list_a의 머리를 제거하고 list_b을 list_b_orig에 저장된 원본으로 설정하여 다시 시작합니다.

Answer 2

어쩌면 그것을 압축하면 작업을 수행 할 수 있습니까?

Zlib 모듈이 이런 식으로 처리하는 것 같습니다.

Answer 3

N 개의 요소 목록이있는 경우 N! 순열. 그래서 우리가 숫자 1에서 N까지 매핑을 생성 할 수 있다면! (또는 0 ~ N! -1)을 재생 가능한 방식으로 이러한 순열에 적용하면 N을 저장할 필요가 없습니다. 요소의 목록이지만 N! 번호.

하지만 그만해 - 왜 우리는 N을 저장해야합니까? 번호? 우리는 변경하지 않기 때문에 저장하지 않아도됩니다. 우리는 가장 큰 요소 인덱스로 정의되는 상한값 만 필요로합니다. N은 코드에 이미 저장되어 있어야합니다.

Erlang을 알지 못해 죄송하지만, 재현성있는 방식으로 임의의 크기의 순열을 생성 할 수있는 I wrote a functional algorithm in Scala입니다.

예를 들어 숫자 (1 - 12)의 123456790 번째 순열은 List (4, 2, 1, 5, 12, 7, 10, 8, 11, 9, 3, 6)입니다.

특별 보너스로이 알고리즘은 정렬 방식으로 순열을 생성합니다. 모든 순열을 재현 할 수 있지만 순서없이 찾는 것은 더 간단합니다.