Alphabetic Anagrams (3kyu)

https://www.codewars.com/kata/53e57dada0cb0400ba000688/csharp

이번 문제는 문제 자체를 이해하는 것이 더 어려웠던 거 같습니다.

특정 단어가 주어지면, 그 단어를 이루는 문자의 조합을 오름차순으로 정렬할 때, 주어진 단어가 몇 번째인 지를 구하는 문제입니다.

예를 들어, CADB라는 단어가 주어지면, 이 단어는 A, B, C, D 문자로 구성됩니다. 이를 일종의 숫자라고 본다면, 이 문자의 조합으로 가장 작은 수(조합)은 A-B-C-D가 됩니다. 그리고 오름차순으로 정리를 하면,

A-B-D-C, A-C-B-D, A-C-D-B ....

이런 순서가 됩니다.

이 순서에서 주어진 단어 'CADB'가 몇 번째인 지를 찾는 것이 문제입니다.

일단 이렇게 생각했습니다.

초기 값 A-B-C-D를 기준으로 제일 앞 문자가 A일 때, 가능한 조합을 찾습니다. A-B-C-D, A-B-D-C, A-C-B-D, A-C-D-B, A-D-B-C, A-D-C-B 6개가 나옵니다. 그럼 주어진 단어 앞에 6개는 무조건 들어가야 합니다.
실질적으로는 B, C, D로 가능한 조합의 개수입니다. 3개 문자니깐 $3!=3\times 2\times1$ 가 됩니다.
그런데 여기에는 주의할 점이 하나 있는데, 중복이 가능하다는 점입니다. B, B, C가 될 수도 있습니다. 이를 구하는 방법은 중복집합 순열(multiset permutation) 공식을 사용하면 됩니다.

https://ko.wikipedia.org/wiki/%EC%88%9C%EC%97%B4
$\left(\! \begin{array}{c} n \\ n_0,n_1, \cdots ,n_k \end{array} \!\right)=\dfrac{n!}{n_0!n_1! \cdots n_k!}$

첫 번째 문자 A에 대해서 조합 개수를 구한 다음에는,
첫 번째 위치에 그 다음 순서인 B가 올 때 가능한 조합을 또 찾습니다.
A, C, D로 이루어진 조합입니다.

이를 반복해서 주어진 단어의 첫 번째 위치의 문자가 일치할 때까지 개수를 세어나갑니다.

그리고는 두 번째 위치로 이동하여 일치할 때까지 동일한 작업을 반복해서 전체가 똑같아 질 때 까지 계산된 조합을 계속 더해나가는 방식을 택했습니다.

이 방식으로는 문제는 없습니다만,
주의할 점은 중복되는 단어가 존재할 때입니다.

BOOK이라는 단어가 있으면,
두 번째 순서 문자를 처리할 때, O가 2번 올 수 있지만, 이는 중복이므로 하나의 O에 대해서만 조합 개수를 계산해야 합니다.

아래는 중복 순열 조합을 계산하는 코드입니다.
factorial계산 메소드가 당연히 들어갑니다..

        private static long factorial(long num)
        {
            if (num == 1 || num == 0)
                return 1;
            else
                return factorial(num - 1) * num;
        }

        private static long calcCombination(string subValue)
        {
            string order = new string(subValue.OrderBy(s => s).ToArray());
            int totalLen = order.Count();
            long total = factorial((long)totalLen);

            Dictionary<char, int> charCnt = new Dictionary<char, int>();

            for(int i=0;i< totalLen;++i)
            {
                if (charCnt.ContainsKey(order[i]) == false)
                    charCnt.Add(order[i], 0);

                ++charCnt[order[i]];
            }

            long sub = 1;
            foreach(var item in charCnt)
            {
                sub *= factorial(item.Value);
            }

            return total / sub;
        }

아래는 최소 order의 단어와 주어진 단어가 일치할 때까지
업데이트하면서 order는 세어나가는 코드입니다.

        public static long ListPosition(string value)
        {
            string src = value;
            string rank0 = new string(value.OrderBy(s => s).ToArray());

            if (src.Equals(rank0))
                return 1;

            int len = value.Length;

            long rank = 1;
            string procStr = rank0;

            for (int i = 0; i < len; ++i)
            {
                if (src[i] == procStr[i])
                    continue;

                int idx = i + procStr.Substring(i, procStr.Length - i).IndexOf(src[i]);

                string removed, pre, post, sel;

                char ch = rank0[i];
                for (int s = i; s < idx; ++s)
                {
                    if (rank0[s] == rank0[s + 1])
                    {
                        continue;
                    }

                    removed = rank0.Remove(s, 1);
                    pre = rank0.Substring(0, i);
                    post = removed.Substring(i, removed.Length - i);
                    sel = rank0[s].ToString();

                    procStr = pre + sel + post;

                    long subComNum = calcCombination(post);
                    rank += subComNum;
                }

                removed = rank0.Remove(idx, 1);

                pre = rank0.Substring(0, i);
                post = removed.Substring(i, removed.Length - i);

                sel = rank0[idx].ToString();
                procStr = pre + sel + post;
                rank0 = procStr;
            }


            return rank;
        }

중간 중간에 문자열 처리는
단어 내, 문자 순서를 변경하는 부분입니다.

대략적인 알고리즘 순서는 아래와 같습니다.
뭔가 마크다운으로 pseudo code를 작성가능하면 좋겠다는 생각이 드네요..

1. 주어진 단어를 복사(src)
2. 주어진 단어를 오름차순으로 정렬 (rank0)
3. rank0을 복사 (procStr)
4. 단어의 길이 만큼 순회(i)
   1. procStr의 순회 인덱스에 해당하는 문자와 동일한 문자의 위치를 src에서 검색
   2. procStr의 순회 인덱스와 src에서 검색된 문자 위치만큼 순회(s)
      1. 단어순서 변경(procStr)
      2. 변경된 문자위치 이후 문자열로 이루어진 중복순열조합 계산
      3. rank 업데이트
   3. 단어순서 변경(procStr)