Created
March 29, 2020 14:27
-
-
Save joriki/d324726fbc3fe4ccdf33628aa02b790c to your computer and use it in GitHub Desktop.
Generate all configurations of balls in bins, optionally with limited capacity
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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