자바의 효율적인 배열 알고리즘

나는 순서가 중요한 곳에서 파워 집합의 모든 순열을 계산할 방법을 쓰려고합니다. 나는 이것을 "준비 (arrangement)"라고 생각한다. 내가이 의미하는 것은 :자바의 효율적인 배열 알고리즘

{a} -> {{a}, {}} 
{a,b} -> {{a,b}, {b,a}, {a}, {b}, {}} 
{a,b,c} -> {{a,b,c}, {a,c,b}, {b,a,c}, {b,c,a}, {c,a,b}, {c,b,a}, {a,b}, {a,c}, {b,a}, {b,c}, {c,a}, {c,b}, {a}, {b}, {c}, {}}

등 내 인상은 세트 S 주어, 나는 다음 순열지도, 그래서 먼저 파워 셋을 생성 S.의 파워 셋의 모든 부분 집합의 모든 순열을 생성해야한다는 것입니다 기능을 각 세트에 적용합니다.

문제는 이것이 매우 복잡하다는 것입니다. 예를 들어 k = 0..n 인 O (Σn!/k!)와 같은 것입니다.

이 종류의 일을 매우 효율적으로 수행하는 기존의 알고리즘 (아마도 병렬 구현)이 있는지 궁금합니다. 또는 병렬 병렬 알고리즘이 존재하고 병렬 대체 알고리즘이 존재하는 경우에도 두 알고리즘을 결합 할 수 있습니다.

생각하십니까?

출처

2012-06-18 rhombidodecahedron

아마도이 게시물을 확인하십시오. http://stackoverflow.com/questions/1506078 – squiguy

[빠른 순열 -> 수 -> 순열 매핑 알고리즘] 가능한 복제본 (http://stackoverflow.com/questions/1506078/fast) -permutation-number-permutation-mapping-algorithms) – Makoto

나는 그것이 중복이라고 생각하지 않는다. 나는 그 실을 읽고 꽤 다른 것을 요구합니다. 솔루션은 주제와 다소 비슷하지만 별도의 스레드를 보증 할만큼 충분히 다릅니다. – rhombidodecahedron

Google에서 제공하는 구아바 라이브러리에는 컬렉션을 바꾸기위한 여러 가지 방법이 있습니다.

com.google.common.collect.Collections2 here 클래스의 javadoc을 참조하십시오.

출처

2012-06-19 15:31:03 luchoct

좋은 답변입니다. 소규모 컬렉션에 매우 편리하지만 N이 커지면 구현이 확장되지 않는다고 생각합니다. –

이렇게하려면 먼저 1-n 슬롯에 대한 조합을 생성합니다. 여기서 n은 전원 집합의 요소 수입니다. 예를 들어 3 개의 요소가있는 경우

C (3,3) = 1 조합 (abc)
C (3,2) = 3 조합 (ab) (ac) (bc)
C (3) = 3 조합 (a) (b) (c)

이제 각 조합에 대한 순열을 생성합니다.

순열 및 조합을 계산하는 잘 알려진 알고리즘이 있습니다. 예를 들어 크 누스의 "컴퓨터 프로그래밍 기술", 볼륨 4A, 섹션 7.2.1.2 및 7.2.1.3에서는 관련 알고리즘을 구성하는 방법을 정확하게 설명합니다.

출처

2012-09-20 22:34:14

자바의 효율적인 배열 알고리즘

답변

관련 문제