Skip to content

Instantly share code, notes, and snippets.

@joriki
Created March 29, 2020 14:27
Show Gist options
  • Save joriki/d324726fbc3fe4ccdf33628aa02b790c to your computer and use it in GitHub Desktop.
Save joriki/d324726fbc3fe4ccdf33628aa02b790c to your computer and use it in GitHub Desktop.
Generate all configurations of balls in bins, optionally with limited capacity
import java.util.function.Consumer;
public class BallsInBins {
public static void traverseConfigurations (int nballs,int nbins,Consumer<int []> consumer) {
traverseConfigurations(nballs,nbins,Integer.MAX_VALUE,consumer);
}
public static void traverseConfigurations (int nballs,int nbins,int capacity,Consumer<int []> consumer) {
recurse (new int [nbins],nballs,capacity,0,consumer);
}
private static void recurse(int [] bins,int nballs,int capacity,int index,Consumer<int []> consumer) {
if (index == bins.length - 1) {
if (nballs <= capacity) {
bins [bins.length - 1] = nballs;
consumer.accept(bins);
}
}
else
for (bins [index] = 0;bins [index] <= nballs && bins [index] <= capacity;bins [index]++)
recurse (bins,nballs - bins [index],capacity,index + 1,consumer);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment