Frobenius Numbers – Round Robin Algorithm

September 20, 2010 at 14:50 (algorithm, java, math.NT)

Frobenius numbers are solutions to the coin problem. Let \displaystyle 0<a_1<\cdots<a_n be coin denominations; what is the smallest sum of money that cannot be obtained using these coins? More formally, define the Frobenius number \displaystyle g(a_1,\,\ldots\,,a_n) as the greatest number that is not a linear combination \sum_{i=1}^n x_ia_i with \displaystyle 0 \le x_i \in \mathbb{Z} . The Frobenius number exists if and only if \displaystyle a_1 > 1 and \displaystyle \gcd(a_1,\,\ldots\,,a_n)=1 . A special case of Frobenius numbers involves the interestingly named McNugget numbers, and there is a well-known formula when \displaystyle n=2 given by \displaystyle g(a_1,a_2)=a_1a_2-a_1-a_2 sometimes known as the Chicken McNugget Theorem.

In the article “The Money Changing Problem revisited: Computing the Frobenius number in time O(ka1)” (PDF link), published in 2005 by Sebastian Böcker & Zsuzsanna Lipták, a beautiful algorithm known as the round robin algorithm for finding Frobenius numbers with potentially large \displaystyle n is described. Here is a Java implementation I wrote a a little while ago; I can no longer remember under what circumstances integer overflow would occur, but since infinity is represented as -1, the program can be easily rewritten with long or BigInteger if desired. Note that frobenius() does not enforce that the input array be sorted ascending, and also the improvements discussed on page 5 of the article are not implemented.

Another interesting approach involving circulant graphs can be found in “Faster Algorithms for Frobenius Numbers” (PDF link), published by Dale Beihoffer, et al., also in 2005.

import java.util.Arrays;

public class FrobeniusNums {
	public static void main(String[] args) {
		int[] mcNug = {6, 9, 20};
		System.out.println(frobenius(mcNug));
	}
	
	static int frobenius(int[] nums) {
		int[] ns = new int[nums[0]];
		Arrays.fill(ns, -1);
		ns[0] = 0;
		for (int i = 1; i < nums.length; i++) {
			int d = gcd(nums[0], nums[i]);
			for (int r = 0; r < d; r++) {
				int n = -1;
				if (r == 0) 
					n = 0;
				else {
					int q = r;
					while (q < nums[0]) {
						if (ns[q] != -1 && (ns[q] < n || n == -1))
							n = ns[q];
						q += d;
					}
				}
				if (n != -1)
					for (int j = 0; j < nums[0] / d; j++) {
						n += nums[i];
						int p = n % nums[0];
						if (ns[p] != -1 && (ns[p] < n || n == -1))
							n = ns[p];
						ns[p] = n;
					}
			}
		}
		int max = 0;
		for (int i = 0; i < nums[0]; i++)
			if (ns[i] == -1 || ns[i] > max)
				max = ns[i];
		if (max == -1) return -1;
		return max - nums[0];
	}
	
	static int gcd(int a, int b) {
		return (b == 0) ? a : gcd(b, a % b);
	}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: