Algorithm and R code for dealing with ties in Wilcoxon rank-sum test 
*

*I think one of the  algorithms used to handle ties for the Wilcoxon rank-sum test (a.k.a., Mann-Whitney U test) is Streitberg / Rohmel. I could not find a good source which explains the algorithm / gives a proof / or even simply outlines the algorithm. Could someone please explain this algorithm, or some other algorithm which also solves the ties problem?

*What would be the R code used to get exact p-values / distributions for a Wilcoxon rank-sum test (a.k.a., Mann-Whitney U test)?
 A: *

*The Streitberg-Röhmel shift algorithm is described in two manuscripts:


*

*Streitberg B, Röhmel J (1986). "Exact Distributions for Permutation and Rank Tests: An Introduction to Some Recently Published Algorithms." Statistical Software Newsletter, 12(1), 10-17. ISSN 1609-3631.

*Streitberg B, Röhmel J (1987). "Exakte Verteilungen für Rang- und Randomisierungstests im allgemeinen c-Stichprobenfall." EDV in Medizin und Biologie, 18(1), 12-19.  
Both are not exactly mainstream journals and one manuscript is in German...which explains why this algorithm is less well-known than the network algorithm by Mehta & Patel underlying their proprietary StatXact software.
The Streitberg-Röhmel shift algorithm (and Van de Wiel's split-up algorithm) are implemented in the R package coin for conditional inference. See:


*

*Hothorn T, Hornik K, Van de Wiel MA, Zeileis A (2006). "A Lego System for Conditional Inference". The American Statistician, 60(3), 257-263.

*Hothorn T, Hornik K, Van de Wiel MA, Zeileis A (2008). "Implementing a Class of Permutation Tests: The coin Package." Journal of Statistical Software, 28(8), 1-23.


*The R code for the Streitberg-Röhmel algorithm is contained in the file coin/R/ExactDistributions.R in the coin source package, available from CRAN.
A: Actually, on this website you can find an implemented version of the Wilcoxon Rank-Sum test which provides the exact solution for data that involves ties and also for data without ties. In addition, quite big sample sizes can be solved (at the moment $A, B \le 200$).  
(The reference is Marx, A.; Backes, C.; Meese, E.; Lenhof, H. P.; and Keller, A.; EDISON-WMW: Exact Dynamic Programming Solution of the Wilcoxon-Mann-Whitney Test.  Genomics Proteomics Bioinformatics, 14(1): 55--61. Feb 2016.)
The algorithm behind the code uses dynamic programming to do a complete search and enumerate efficiently all subproblems to be able to calculate the exact p-value without any approximations or corrections.
