'완전히 섞였다.', '랜덤성', '연관 관계'에 대한 정의가 우선 필요합니다.

카이자승 값으로 그 둘의 연관성이 있는지 없는지를 구하는 방법이 있다던가, 그 둘의 평균값이 일치하는지 하지않는지를 신뢰수준 x%수준으로 검증하는 방법을 통계시간에 배우긴 합니다만..

전공은 아니지만;;
'수학의 알고리즘'은 '일상의 적당한 절차'와는 다릅니다. 명백하고 기계적(?)입니다. 따라서 X는 언제나 A와 B를 연관시킵니다.

니코님 말씀대로 각 정의가 명확해야합니다.
예를들어 완전히 섞였다를 섞은후 동일한 위치에 존재하는 카드가 없다 라고 둔다면 얼핏 다 섞인것같지만 처음덱 A의카드 각각에 순서를 부여해놓았다고 가정할때 1번만 맨뒤에 넣어버려도 실제 1장외엔 순서가 바뀐건 없지만 동일한 위치에 존재하는 카드는 단 한장도 없기에 완전히 섞인거라 볼 수 있습니다.

섞기 전 덱과 섞인 이후의 덱이 완전히 같더라도

랜덤하게 섞이지 않았다라고 할 수 있는 것은 아니지 싶습니다..

인장님//
얼밀히 말하면 어떤 알고리듬을 쓰느냐에 따라 다릅니다. 예를 들어 '가나다순 정렬 알고리듬'은 A라는 자료에서 결과물 B가 나올지 명백하지만, 결과물 B에선 A의 관계를 유추할 수 없죠. (그래프 이론의 directed edge와 비슷합니다.)

카드 섞기 알고리듬을 짤 때의 문제점은, 평범한 알고리듬은 언제나 역으로 연산함으로서 B에서 A를 찾아내는 게 가능합니다. (간단한 마술 트릭에서 써먹는 방법이기도 하죠.)

순수한 사전적 의미에서 '무작위적'으로 섞이는 것을 원한다면 난수표 등 '랜덤성'을 부여할 시스템이 알고리듬에 충분히 포함되어야 합니다.

만약 연역적으로 알고리듬의 랜덤성을 알고 싶다면, '완전히 동일한 데이터'를 수십 수백번 넣고 알고리듬을 돌렸을 때 충분히 다른 결과가 나올 수 있으면 됩니다.

완전히 섞였다 라는 걸

'누구도 예측하지 못하는' 라는걸로하는게...

니코 // 네 그게 어려운거 같습니다
인장 // 탁탁탁 몇번만 해도 이미 인위적인 랜덤은 제공할 수 있다고 생각합니다. 제가 말한 알고리즘은 방법이라고 하는게 낫겠네요.
모포소년 // 네, 그런 방법으로도 증명이 가능할 것 같습니다. 1번만 옮기면 원상태로 돌아간다, 고로 이건 연관되어졌다, 이렇게 말이죠.
가이오트 // 그런 경우도 있을 것 같습니다. 아무래도 확률이나 신뢰도가 들어가야할 것 같기도 하네요.

니코님//
옳은 말씀입니다. 저의 요지를 조금 수정하면, X는 언제나 A를 B에 연관시킨다는 것입니다. 역은 말씀하신 바와 같습니다.
애초의 문제가 주어진 A와는 완전히 독립적인 '랜덤한' B를 만드는 것인데, '수학적' 알고리즘으로는 불가능하다는 것이 제 생각입니다.

잘 섞였다라는 것을 이미 나온 카드들을 보고 다음 카드를 예측하기 어려운 것이라 정의한다면, 덱에서 임의의 두 카드 사이의 거리를 표로 만든 다음 섞기 전과 후에 비교해서 얼마나 많은 쌍의 거리가 달라졌는지로 판단하면 어떨까 합니다.

byturn // 그 또한 아주 단순한 예시로써 실질적으로 우리가 원하는 잘 섞인 덱이 아님을 보일수 있습니다. 1 2 3 4 5 6 이라는 6장의 카드에서 분명 1과 6은 4라는 거리(두카드사이의 카드수로 거리를 정의)이고 2와 5는 2라는거리, 3,4는 0이겠쬬.
근데 4 5 6 1 2 3 이라고하면 거리의 변화는 3쌍 모두 달라졌습니다만 실제로는 그냥 반더미만 떼어내서 앞으로 옮긴게 되겠죠....

한가지 방법을 생각했는데....홀수번째 카드와 짝수번째 카드로 구분해서 짝수번째 카드들을 뽑아내어 덱으로 모아서 홀수번째더미 뒤에 쌓는겁니다. 이 과정을 반복시행하게되면 어떨까요....일전에 플텍카드 잘섞는 법에 나온걸 하나의 방법으로 만들어본겁니다.ㅎㅎ 이해하기 쉬운 표현을 위해 그 과정이 반대로 시행되지만..

라스베가스에서 현재 사용되고 있는 카드 셔플기의 셔플 알고리듬을 분석하는 게 가장 빠를 것 같군요. (하지만, 그 알고리듬 엄청나게 비싸게 거래된다죠?^^)

모포소년//설명이 불명확했던 것 같습니다. 모든 쌍에 대해 거리를 재는 것입니다. 예시에서 보면

12,13,14,15,16,23,24,25,26,34,35,36,45,46,56 순으로

원래 덱은 1,2,3,4,5,1,2,3,4,1,2,3,1,2,1
옮긴 덱은 1,2,3,2,1,1,4,3,2,5,4,3,1,2,1

15 쌍의 거리 중 6 쌍만 달라졌으니 그리 잘 섞인게 아닌거죠.

니코 // 글쎄요. Knuth's shuffle algorithm 을 구글에서 찾아보시면 뭐 그정도는 아니라는 것을 알 수 있습니다.

byturn님//
크누스 알고리듬은 알고리즘 내에서 '랜덤 넘버 R'을 만들어야 합니다. 즉 '랜덤 넘버 R'이라는 개념을 또다시 알고리듬으로 구성해야 한다는 것이죠.

그놈은못ㅤㅆㅣㅆ었다님//
완전한 알고리듬을 원하시는 게 아니면, 모포소년님이 자정 3분 경에 쓰신 덧글을 포함한 몇 가지 셔플법을 번갈아 하는 걸로도 충분합니다.

니코 // pseudo-random number 알고리즘에 대해서도 찾아 보시면 용도에 따라 수많은 방법들이 존재하며, 이른바 '초장주기' 알고리즘도 구현에 그리 비용이 들 이유가 없다는 건 쉽게 알 수 있으리라 생각합니다. 전산 전공자가 이걸 모르실것 같진 않은데 왜 사족을 붙이신 것인지?

니코 // 라스베가스에서 사용되는 셔플기도 요즘은 컴퓨터 컨트롤이라고 합니다. 손으로 따라하기에는 힘들어진 거죠. 혹시 이전에 사용되었던 기계식 셔플기가 있다면 수집가에게 엄청나게 비싸게 거래될 수도 있겠다는 생각은 듭니다.

byturn님//
전 전산 전공이 아니고 수학 전공으로, 수학 전공 과목에서 들은 파편적 지식으로 답한 것뿐입니다.
무의식중에 수리논리적으로 답해버렸네요. 제 답변보단 byturn님의 답변이 더 정확할 것 같습니다. 위에 제가 단 덧글 중 '라스베가스'이야기가 나온 덧글은 취소하겠습니다.

약간 오해가 있는듯 하네요. 제가 알고 싶었던 것은 카드 섞는 법이 아니라 '섞인 카드가 잘 섞였다는 걸' 증명하는 것이었습니다.

저도 나름 카드 섞을때 공을 들이는 편이구요, 섞인 카드로 하면서 진행에도 아무 문제 없었습니다. 다만 보드게임에 대한 오타쿠적, 혹은 학문적인 호기심으로 질문드렸던 것입니다.

많은 분들의 답변을 읽어보니 어느정도 방법이 보이네요. 감사합니다.

그놈은못씼었다님//
오늘 이산수학 교수님께 질문해서 책을 한 권 추천받았습니다. 제가 직접 책을 읽어봐야 말씀드릴 수 있을 것 같은데, 대강 간단하게 설명드리자면
'나올 수 있는 모든 결과물의 확률 분포가 Uniformly Distributed되어 있다면' 된다고 합니다. (즉, 어떤 ABC를 섞었을 때, ABC ACB BAC BCA CAB CBA가 나올 확률이 모두 1/6이면 된다고 하더군요.)

저도 그놈님 덕분에 관심이 생긴 문제니, 혹시 자세한 공부를 할 기회가 되면 후에 꼭 그놈님께 말씀드리겠습니다.

쉬는 시간에 급하게 다는 덧글이라 그놈님이라고 줄여서 부른 점 죄송합니다.

그냥 A의 카드 순서를 무시하고 A의 카드 목록만 가지고 새로 랜덤하게 카드덱 B를 만드는 게 어떨까 하는데요? A와 B가 완전히 무관하다라는 걸 중시한다면 A와 B를 연결시킬 필요가 없습니다.

하텔슈리// 실제적인 예로 도미니언을 한다고 생각해보세요. 자기 턴이 끝나고 덱이 바닥나 새 덱을 만들때 이왕이면 잘 섞고 싶겠죠? 하지만 탁탁탁을 아무리 해도 그 느낌이 시원찮습니다. 정말 잘 섞인걸까? 제 의문은 거기서 시작된 것입니다. 무관하단걸 중시하기 때문에 이전 덱과 새 덱의 관계가 중요하죠.

니코// 정말 고맙습니다. 덕분에 좋은 방법이 생각났습니다. 2가지 방법이 있습니다.

첫번째는 추적입니다. 가령 1부터 100까지 카드가 있다고 가정할때 여러번 섞으면서 1의 행방을 추적합니다. 간단하게 100번을 섞는다고 하면 완전한 랜덤일 경우 이상적으로 1의 위치는 첫번째부터 100밴째까지 1번씩 위치해야겠죠. 하지만 실제는 어느정도 편차가 있을 것입니다. 그것을 실제 랜덤한 알고리즘과 비교해보면 얼마나 효용이 있는지 상대적으로 알 수 있을 것 같습니다.

두번째는 거리비교입니다. 아까와 같이 1부터 100까지 있고 이번에는 1과 2 두개를 추적합니다. 이때 중요한 것은 위치가 아니라 1과 2의 거리입니다. 이것도 많은 횟수를 반복해 평균을 냈을때 완전한 랜덤일 경우와 어느정도 차이가 보일 것입니다. 둘을 비교해 상대적인 효용성을 알아낼 수 있을 것입니다.

위의 2가지 방법을 동시에 고려해보면 특정한 셔플법이 어느정도의 효용이 있는지 알 수 있겠죠. 실제 구현은 컴퓨터로 할테니 횟수는 중요하지 않겠죠 :)

그 밖에 더 좋은게 생각 나시면 말씀해주세요. 일단은 저 2개로 시작해보려고 합니다.

카드 셔플은 현실에서 하는 거니 어느 정도 현실과 타협도 하세요^^;

아 제가 알고 싶었던 것은 완벽한 셔플법이 아니라, 제가 하는 셔플법이 어느정도나 잘 섞이는지 알고 싶어서였습니다. 그리고 여러가지를 비교해보고 가장 괜찮은 것이 뭘까 궁금하기도 했구요.

입력 시퀀스 X(섞기전의 카드 순서)와 출력 시퀀스 Y(섞은 후의 카드 순서)를 놓고 auto correlation과 cross correlation을 구하면 알 수 있습니다. 두 시퀀스간의 상관계수를 알 수 있죠. 상관계수가 낮을 수록 잘 섞인것이 되겠군요.