iPod과 같은 셔플 알고리즘을 효율적으로 구현할 수 있습니까?

목표는 N 개의 노래에 대해 반복없이 1..N에서 임의의 노래를 선택하고 iPod 에서처럼 앞뒤로 반복 할 수 있습니다. 해시 테이블을 사용하여 임의의 노래를 저장했습니다. 더 좋은 방법이 있습니까?iPod과 같은 셔플 알고리즘을 효율적으로 구현할 수 있습니까?

출처

2013-05-06 McDowells

코드를 공유 할 수 있습니까? – pollirrata

당신이 쓰고있는 것을 모른 채 이것을 쓰는 것이 조금 어렵습니다! – GriffLab

앞뒤로 반복 할 때의 의미는 무엇입니까? – arynaq

한 가지 방법은 LCG 기반의 의사 난수 생성기를 사용하여 노래를 선택하는 것입니다. 매 단계마다 노래 n + 1은 (an + b) Mod 2^N입니다. LCG의 기간이 N 이상인지 확인하십시오. LCG의 역수를 사용하여 역순으로 반복하십시오.

출처

2013-05-06 18:05:53

흥미로운 아이디어. 기간이 N보다 큰지 확인하는 방법은 무엇입니까? – McDowells

en.wikipedia.org/wiki/Linear_congruential_generator#cite_note-HullDobell-3 –

이것은 노래의 명확하게 임의가 아닌 순열을주지 않습니까? – templatetypedef

이 작업을 수행하는 간단한 알고리즘은 N 곡 모두의 목록으로 시작한 다음 Fisher-Yates Shuffle과 같은 알고리즘을 사용하여 배열 요소를 임의로 셔플하는 것입니다. 일단 그렇게하면, 모든 노래를 무작위로 순서없이 중복없이 주문할 수 있습니다. 목록에서 현재 색인을 추적하면 배열에서 앞으로 또는 뒤로 이동하여 다음 및 이전을 구현할 수 있습니다.

희망이 도움이됩니다.

출처

2013-05-06 18:05:40 templatetypedef

그래서 O (NlogN)을 섞어서 O (N) 개의 공간을 검색하여 배열을 찾으십니까? – McDowells

@ McDowells- 사실, O (n) 만 셔플을 수행합니다 (Fisher-Yates는 O (n) 시간에 실행 됨). 그런 다음 배열에서 O (1) 조회 시간 만 수행합니다. O (n) 메모리를 사용하여 셔플 순서를 유지해야합니다. – templatetypedef

메모리의 비용이 적게 드는 인덱스 배열을 섞습니다. – arynaq

iPod과 같은 셔플 알고리즘을 효율적으로 구현할 수 있습니까?

답변

관련 문제