В рамках настоящего исследования анализируется актуальная проблема, связанная с определением точных распределений для ранговых непараметрических критериев при отсутствии замкнутых аналитических решений. Классический подход, основанный на полном переборе всех возможных перестановок рангов, хотя и является теоретически точным, оказывается практически неприменимым уже для небольших объемов выборок вследствие комбинаторного взрыва числа вариантов. Прямой перебор всех возможных перестановок рангов, являющийся методом точного расчета, оказывается вычислительно неразрешимой задачей даже для выборок небольшого объема из-за комбинаторного взрыва. Рассмотрены наиболее известные ранговые непараметрические критерии, не имеющие аналитического решения для получения полной функции распределения, такие как критерии Лемана-Розенблата, Краскела-Уоллиса и Муда. Существующие аппроксимации (нормальная, хи-квадрат) часто оказываются неудовлетворительными для малых выборок. В работе предлагается эффективное решение на основе метода динамического программирования, позволяющее в сотни раз сократить вычислительные затраты по сравнению с наивной генерацией перестановок. Реализована методика, включающая генерацию последовательностей рангов, расчет статистик для каждой из них и последующую агрегацию результатов для построения функции распределения. Проведенные вычислительные эксперименты однозначно демонстрируют, что метод динамического программирования является наиболее эффективным для генерации точных распределений. Разработаны и представлены в открытом доступе программные реализации на C++ и Python, проведено их сравнительное тестирование, которое подтвердило ожидаемое лидерство C++ с точки зрения быстродействия.
This paper considers the problem of calculating exact distributions for nonparametric rank tests in the absence of analytical solutions. The classical approach based on a complete enumeration of all possible permutations of ranks, although theoretically accurate, turns out to be practically inapplicable even for small sample sizes due to the combinatorial explosion of the number of variants. A straightforward enumeration of all possible rank permutations, which is an exact calculation method, proves computationally intractable even for small samples due to combinatorial explosion. The most well-known nonparametric rank tests lacking an analytical solution for obtaining the full distribution function are considered, including the Lehmann-Rosenblatt, Kruskal-Wallis, and Mood tests. Existing approximations (normal, chi-square) often prove unsatisfactory for small samples. This paper proposes an efficient solution based on dynamic programming, which reduces computational costs by hundreds of times compared to naive permutation generation. The methodology implemented includes generating rank sequences, calculating statistics for each sequence, and then aggregating the results to construct the distribution function. Computational experiments conducted clearly demonstrate that dynamic programming is the most effective method for generating accurate distributions. Software implementations in C++ and Python have been developed and made publicly available, and comparative testing has confirmed the expected performance advantage of C++.
The authors declare that there are no conflicts of interest present.