모두 다른 위치로 랜덤으로 바꾸는 알고리즘?

Question

N개의 위치에 값이 있을때 랜덤으로 위치를 바꿔주고 싶습니다, 단 반드시 다른 위치로요 즉

ABCDE 가 있는데

CDBA'E' 는 E는 위치가 바뀌지 않았으므로 불가 입니다.

 

혹시 이런 문제를 부르는 이름이 있나요?

 

일단 생각한 해법은 두가지 인데

1. 모든 변경 가능한 경우의 수를 구한 뒤 -> 위치가 바뀌지 않은 경우를 제거하고 -> 남은 경우의 수 중에서 하나를 뽑는것

인데 이건 N의 크기가 커지면 노답일거 같구요

 

2. 그냥 계속해서 랜덤으로 모든 위치가 바뀔때까지 돌려보기

이건 사실 의외로 쓸만할거 같은데 재수 없으면 너무 오랜시간이 걸리는 경우가 생길거 같은게 문제입니다.

Comments

idx+1 과 교환시 성립은 하는데 모든 분포가 나오지 않는 문제가 있네요

                크기가 2일때 (가능한 경우 10)
                01
                    10
                
                크기가 3일때 (가능한 경우 120, 210, 201)
                012                
                    102                    
                        120                    
                    210                
                        201
                        
                        
                크기가 4일때 (경우의수 1230, 1302, 1320, 2031, 2301, 2310, 3012, 3201, 3210)                
                0123
                    1023
                        1203
                            1230
                        1320
                            1302                        
                    2103
                        2013
                            2031
                        2301
                            2310
                    3120
                        3210
                            3201
                        3021
                            3012

---

일단 무작위로 섞은 후

 

변경되지 않은 위치가 있는지 검사해서 랜덤으로 다른 위치로 변경하는 방법으로 해결 했습니다.

다만 이를 위해 크기만큼 메모리가 더 필요하네요(인덱스가 변경되었는지 저장해야함)

Answer 1

확률은 상관 없다고 가정할때

1. a 를 제외 하고 랜덤으로 선택한다. ( 1개 제외 )

2. 1 에서 선택한 값과 b를 제외 하고 선택한다. ( 1개 에서 2개 제외 )

3. 1, 2, 에서 선택한 값과 c 를 제외 하고 랜덤 선택 한다. ( 2 개에서 3개 제외 )

4 1,2,3 에서 선택한 값과 d 를 제외 하고 랜덤 선택 한다. ( 3개 에서 4개 제외 )

5 마지막 남은 아이템이 이전 값과 같은지 본후 이전값과 같다면 3이나 4으로 돌아간다. ( 4개 제외 )

대충 이정도면 되지 않을까 싶은데... 수학적으로 증명은 어렵겟군요.

Comments

X를 다른 위치의 값 Y와 교환한다고 할때

  -> X는 자기와 다른 위치와 교환하므로 반드시 다른 위치에 설정된다

  -> Y가 가는 위치는 X가 주인이였으므로 역시 다른 위치에 설정된다

이므로 무조건 모든 자리가 바뀌는건 확실하네요

 

다만 랜덤 분포가 고르게 나올지는 모르겠군요

---

그런데 크기가3인 리스트는 말하신 방식으론 불가합니다

{0,1,2}

a. 0 과 1 교환 {102}

b. 두번째 idx는 교환 했으므로 스킵 {102}

c. 2는 교환할 위치가 없음 -> 이전 으로 돌아가도 다른 방법이 없음

---

{0 , 1 , 2}

a . 0 제외 나머지 ( 1 , 2 ) ( 1 픽 )

b .  선택한 1 제외 , 그리고 2 번째 인덱스인 1 제외 (중복 제외 ) (0 , 2 ) 중 선택 ( 0 픽)

c .  (0, 1) 제외 2 남음 b 로 돌아감

 

b .  선택한 1 제외 , 그리고 2 번째 인덱스인 1 제외 (중복 제외 ) (0 , 2 ) 중 선택 ( 2 픽)

c .  (0, 2) 제외 1 픽

 

a . 0 제외 나머지 ( 1 , 2 ) ( 2 픽 )

b .  선택한 2 제외 , 그리고 2 번째 인덱스인 1 제외 (중복 제외 ) ( 0 ) 중 선택 ( 0 픽)

c .  (2 , 0 ) 제외 1 픽

 

먼 가 설명에 오해가 있을만한 부분이 있나봅니다..

Answer 2

우선 문자열을 반으로 가릅니다.

만약 홀수개의 Element가 있다면, 정 중앙의 1개를 제외하고 서로 위치를 바꿔버립니다.

ABCD라면, AB와 CD를 바꿔 CDAB로 만듭니다. CDAB

홀수개의 Element가 존재 할때, 가령 ABCDE라면, 정중앙 C를 제외하고 AB와 DE의 위치를 바꿔

DECAB로 만듭니다. C의 경우에 DE나 AB 두 그룹중 하나와 Element를 바꾸면 됩니다.

D를 골라 C와 위치를 바꿉니다. CEDAB 가 됩니다.

C 의경우 정중앙에 있는 원소이므로 양측 영역 두군데중 하나로 들어가게 된다면 그자체로 위치가 바뀌었음이 자명합니다.

D의 경우, 원래 자신이 있던 영역(지금 AB가 위치한곳) 이 아니므로 , 위치가 바뀐것이 자명합니다.

이렇게하면 위치는 무조건 바뀐게 됩니다.

덧붙여 예쁘게 섞이길 원한다면, (ABCD를 CDAB로 바꾸어도  중앙 경계를 제외하고는

양 그룹 내부에서의 이웃이 그대로기 때문에 엉성하게 섞인것처럼 보입니다.

두개로 갈라 바꾼것을 알아채기가 쉬울 수 있습니다.

이 경우에는 , 그룹 내부에서 위와 같은 작업을 반복해 패턴을 복잡하게 만들면 됩니다.

가령 ABCD E FGHI 의 경우, ABCD와 FGHI를 바꿔 FGHI E ABCD 로 만듭니다.

FGHI를 HI FG로 만듭니다. E 는 그대로 두고 ABCD를 CD AB로 만듭니다.

HI,FG,CD,AB 내부에서는 위치를 바꿔도 되고 안바꿔도 됩니다.

그리고 타 그룹의 같은 위치에 위치한 Element 끼리 위치를 바꿔 줄 수 있습니다 . HIFGECDAB이므로 H<->C , D<->I

그룹내부에서의 위치가 달라졌기 때문에, 다른 그룹내의 같은 위치의 원소와 바꿔도 바뀐게 됩니다.

마지막으로 중앙의 E를 아무 원소랑 위치를 바꿔주면 완성입니다.