KTUG마당은 KTUG를 방문하는 모든 이용자가 대화를 나누고 소식을 전하는 곳입니다.
- 로그인 없이 자유롭게 글을 읽고 쓸 수 있는 철학은 처음과 같이 계속됩니다.
- Team Blog의 글을 이곳 게시판의 "정보글"로 모았습니다. Team blog는 기고자가 올린 글에 질문을 받는 부담을 줄이기 위하여 댓글을 허용하지 않았습니다. 그러나 이곳 게시판으로 모으면서 댓글을 달 수 있습니다. 게시물을 작성하실 때 댓글을 원하지 않으시면 댓글을 허용하시지 않으시기를 바랍니다. 또한 불필요한 소모성 댓글을 달지 않도록 주의하여 주시기를 바랍니다.
- TeX과 관련된 질문이나 답변은 QnA 마당을 이용하십시오. TeX과 관련된 질문은 지웁니다
- MathJax를 이용한 수식조판을 사용하실 수 있습니다. 여기를 참조하세요.
- 스팸 글을 막기 위하여 짧은 시간 내에 다시 글이 등록되는 IP를 막거나, 광고 글을 막기 위하여 금지어로 .com, .net 등을 설정하고 있습니다. 다소간의 불편함이 있으시더라도 양해 바랍니다.
- 금지어에서 stackexchange, stackoverflow, ctan, overleaf, , github, google.com, gmail.com, .org, .io, sil.org, wiki.com, tistory.com등은 해제하였습니다.
- 사용하는 편집기는 CKeditor입니다. 편집기에서 [enter]를 누르면 <p> 태그가 들어가고, 문단으로 생각하고 한줄을 비웁니다. 글줄만 바꾸려면 shift-enter 를 누르시면 <BR>가 들어가므로 용도에 맞게 나누어 쓸 수 있습니다.
자유글 [expl3] string의 permutation
2018.12.09 09:55
hoze 님의 블로그에서 주어진 글자들을 조합하여 낱말 만들기라는 글을 읽었습니다. ( http://hoze.tistory.com/1693 )
예전에 이 비슷한 것을 본 기억이 나서 검색을 하였습니다. 이 글에 첨부되어 있는 tstmlt.pdf라는 문서였습니다. forloop 패키지에 대한 글이었는데요. forloop를 반복적으로 사용하면 할 수 있다는 것이었는데 expl3를 쓰지 않던 시절이었으니까요. 그것과 별도로 문서 자체는 제법 재미있습니다.
아무튼 이제 expl3가 있으니까 hoze 님 글에 소개된 재미있어 보이는 알고리즘을 어떻게 해볼 수 없을까 생각해보았습니다. 두 가지가 문제가 되었는데,
(1) 만약 문자열을 tl로 받아들인다면 (seq이나 clist라도 마찬가지입니다만) tl의 i번째 item과 j번째 item을 교환하는 명령을 정의해야 합니다.
(2) hoze님의 permute()는 자신을 재귀호출 한 이후에 교환했던 a[i]와 a[j]를 되돌려놓도록 하고 있습니다. 그런데 이것은 재귀호출 후의 코드라서 이 방식 그대로 expl3로 하는 것이 좋아 보이지 않았습니다. 재귀호출이 "마지막"에 오도록 하고 싶었기 때문이지요.
이를 피하기 위하여 원래의 tl에 대하여 item(i)와 item(j)가 교환된 결과를 별도의 사본 tl에 옮겨놓는 방식으로 해결하였습니다. 원래의 tl을 건드리지 않았기 때문에 되돌릴 필요가 없고 사본 tl은 교환이 이루어진 형태로 작성할 수 있기 때문입니다. 이 tl은 local로 사용되어서 재귀적으로 다시 할당되니까 원하는 결과가 나오리라고 예상했습니다.
좋은 공부가 되었습니다. 더 좋은 해결책을 가르쳐주시는 것을 환영합니다.
소스를 첨부하였습니다.
* SRC (zip): testpermute.zip
댓글 4
-
yihoze
2018.12.10 08:41
-
작나
2018.12.13 10:02
주어진 배열의 모든 순열을 나열하는 방법은 여러 가지가 있습니다.
가장 먼저 생각할 수 있는 것이 모든 순열을 사전식으로 나열하는 것이고, 또, plain changes 라는 꽤 효과적이고 유명한 알고리즘이 있습니다.
이 알고리즘의 특징은, 순열들을 나열할때, 다음 순열은 현재 순열의 위치와 한쌍만 다르다는 것입니다.
예를들면, "abc"라는 문자열의 순열들을 모두 나열할 때, 다음 처럼하면
abc, acb, cab, cba, bca, bac
abc에서 다음 acb로 갈때는 (b,c)의 위치만 서로 바뀐 것이고, acb 에서 그 다음 cab로 갈때는 (a,c)의 위치만 바뀐것입니다.
이처럼 abc에서 시작하여 한쌍의 위치만 서로 바꾸면서 최종 bac까지 가는 방법이 plain changes 알고리즘입니다.
plain changes와 같은 방식으로 동작하는 순열에서는 짱먹는 Heap 알고리즘이 있습니다.
이 알고리즘은 plain changes와 개념은 같지만 보다 좀더 효율적입니다.
그래서 Heap 알고리즘을 루아로 구현해봤습니다. https://bit.ly/2rxaUBF
루아로 됐으니, 텍으로 만들 수도 있다는 뜻이죠.
-
yihoze
2018.12.13 14:10
Heap 알고리듬 이해하려면 며칠 걸릴 것 같은데요. 아무튼 Heap 알고리듬을 루어텍이 아니라 expl3로 구현하기는 아주 어려울 것 같아요. 이런 짓(?)은 텍이 아니라 루어나 파이썬 같은 것들에게 맡기는 게 정신적으로 해롭지 않다고 봅니다. ^^
-
noname
2018.12.13 19:19
expl3로 하는 것이 *아주* 어렵지는 않을 것 같습니다. 이 정도의 태스크라면 expl3도 함수형 언어를 곧잘 흉내내는 것이 아닌가 싶습니다. 문제는 목적이 무엇이냐와 어떤 툴에 익숙한가 정도 아닐까요? (본글에서 언급한 블로그 게시글에 최근 추가된 것, 이를테면 만들어진 문자열이 자연어 단어인가 여부를 확인하기 위해서 자연어 패키지가 제공하는 사전을 참조한다든가 하는 그런 일을 expl3로 하기는 좀 그렇겠지요.)
작나 님의 루아 코드에서는 for 루프를 n-1까지 돌리고 heap() 함수를 한 번 더 재귀호출하는 방식으로 되어 있는데 나열되는 순서에 민감하신 것으로 생각하고요, 여기서는 그냥 n까지 루프를 돌리면서 재귀호출을 한 번만 하도록 했습니다. 작나 님 코드와 완전히 동일한 결과를 얻으려면 그와 같은 방식으로 조금 수정하면 될 줄로 짐작합니다.
TEX: heappermute.tex
Word Tower라는 모바일 게임에 도움이 될까 하여 찾아본 건데요. 해 보시면 알겠지만 그다지 큰 도움은 되지 않습니다. ^^ 그런데 파이썬도 그렇고, 이 expl3 코드도 한글을 잘 처리하네요.