Combinatorial methods are used to determine the spatial distribution of earthquake magnitudes on a fault whose slip rate varies along strike. Input to the problem is a finite sample of earthquake magnitudes that span 5 kyr drawn from a truncated Pareto distribution. The primary constraints to the problem are maximum and minimum values around the target slip-rate function indicating where feasible solutions can occur. Two methods are used to determine the spatial distribution of earthquakes: integer programming and the greedy-sequential algorithm. For the integer-programming method, the binary decision vector includes all possible locations along the fault where each earthquake can occur. Once a set of solutions that satisfy the constraints is found, the cumulative slip misfit on the fault is globally minimized relative to the target slip-rate function. The greedy algorithm sequentially places earthquakes to locally optimize slip accumulation. As a case study, we calculate how earthquakes are distributed along the megathrust of the Nankai subduction zone, in which the slip rate varies significantly along strike. For both methods, the spatial distribution of magnitudes depends on slip rate, except for the largest magnitude earthquakes that span multiple sections of the fault. The greedy-sequential algorithm, previously applied to this fault (Parsons et al., 2012), tends to produce smoother spatial distributions and fewer lower magnitude earthquakes in the low slip-rate section of the fault compared to the integer-programming method. Differences in results from the two methods relate to how much emphasis is placed on minimizing the misfit to the target slip rate (integer programming) compared to finding a solution within the slip-rate constraints (greedy sequential). Specifics of the spatial distribution of magnitudes also depend on the shape of the target slip-rate function: i.e. stepped at the section boundaries versus a smooth function. This study isolates the effects of slip-rate variation along a single fault in determining the spatial distribution of earthquake magnitudes, helping to better interpret results from more complex, interconnected fault systems.