(함수형 언어로 작성한) 응용 프로그램의 경우 결정적 셔플 링 알고리즘을 구현하여 같은 시드가 주어진 경우 X 위치의 일부 요소가 제거 된 같은 동일한 순서로 배열을 반환합니다. 그 원소가 배열에 없었을 것이다. 예 : shuffle([1,2,3,4,5], seed) = [4,2,3,1,5] 인 경우 shuffle([1,3,4,5], seed)은 [4,3,1,5]을 반환해야합니다. 그러나 바퀴를 재발견하기 전에, 나는 물어야 만한다 : 그러한 알고리즘이 존재 하는가? (또한이 속성에 어떤 이름이 있는지 궁금합니다.) 모든 입력에 감사드립니다.요소 삭제시 교환 가능한 셔플 링 알고리즘?
셔플이 원본 목록이나 시드가 바뀐 목록을 거꾸로 만들면 설명하는 속성을 갖게됩니다. 다른 모든 항목과 하위 항목 모두가 해당하는 임의로 배치 된 것과 일치 할 때 요소가 동일한 방식으로 이동하게됩니다. 예를 들어, shuffle([1,2,3])을 고려하십시오. 아래 표에서 각 열은 서로 다릅니다. 각 경우에 대해 3 개의 하위 목록 중 하나에는 다른 두 항목과 다른 방식으로 요소를 이동시키는 셔플이 있습니다. 중복 값을 가정하지
shuffle([1,2,3]) = [1,3,2] [2,1,3] [2,3,1] [3,1,2]
shuffle([1,2]) = [1,2] [2,1]* [2,1] [1,2]*
shuffle([1,3]) = [1,3] [1,3] [3,1] [3,1]
shuffle([2,3]) = [3,2]* [2,3] [2,3]* [3,2]
, 당신은 HMAC, 예를 들어, pseudorandom function에서 값을 정렬 할 수 있습니다.
'X '는 값 또는 초기 위치로 식별됩니까? –
@ScottHunter X는 초기 위치로 식별됩니다. 나는 그것을 명확하게하기 위해 포스트를 업데이트 할 것이다. 내 경우에는 배열이 [1,2, ..., n] 형식이 될 것이므로 문제가되지 않지만 일반화 된 버전을 갖는 것이 좋습니다. – Sid
초기 값을 초기 셔플 위치에 매핑하여 해결할 수있는 것처럼 보입니다. 그 후에, 새로운 목록이 주어지면, 그것들의 매핑을 찾으십시오. 시드가 변경되면 매핑을 다시 빌드하십시오 (시드에 의해 키가 매핑 된 매핑 사전 유지). – Dinesh