Tag Archives: c++

🚪 revdoor

revdoor is a single-file C++ library for visiting revolving door combinations. The combinations without replacement generator implements Algorithm R from TAOCP 7.2.1.3 [1]. The combinations with replacement generator implements the same algorithm, modified to support replacement. The algorithms visit combinations … Continue reading

Tagged , , , , | Leave a comment

SMAWK in C++

I recently implemented kmeans1d—discussed in a prior post—for efficiently performing globally optimal 1D k-means clustering. The implementation utilizes the SMAWK algorithm (Aggarwal et al., 1987), which calculates argmin(i) for each row i of an arbitrary n × m totally monotone … Continue reading

Tagged , , | Leave a comment

kmeans1d: Globally Optimal Efficient 1D k-means Clustering

I implemented kmeans1d, a Python library for performing k-means clustering on 1D data, based on the algorithm in (Xiaolin 1991), as presented in section 2.2 of (Grønlund et al., 2017). Globally optimal k-means clustering is NP-hard for multi-dimensional data. LLoyd’s … Continue reading

Tagged , , , | Leave a comment