There are 126 ways to split 10 digits into 2 sets of 5 without duplicates. For each set of 5 digits, there are 120 ways (permutations) to arrange them into the form ab*cde, or 72 ways if the group contains zero and a leading zero is not allowed. That means a brute-force algorithm would need to check 126 × 120 × 72 = 1,088,640 possibilities.
However, for each pair of sets of 5 digits, if you generate the permutations in the order so that the resulting products are ordered from small to large, you can find the smallest difference of products in 120 + 72 = 192 steps (or fewer depending on how much the ranges overlap) instead of 120 × 72 = 8640. The maximum total becomes 24,192 instead of 1,088,640, which is 45 times less.
(In practice, only 12,574 product differences are calculated, and the first zero-difference result is found after 6679 steps).
You take the permutations with the smallest product for each set, calculate their difference, and store it if it is smaller than the minimum found so far. Then, you replace the permutation whose product is smallest by the next permutation in the list for that set (but stay on the same permutation for the other set) and calculate their difference, and so on, until you reach the end of one of the sets.
In the JavaScript code example below I'm using the product as the index of a sparse array (like a dictionary that can be read in order) to create an ordered list of permutations and their products (because I couldn't immediately find a simple way to generate them in order).
Array.prototype.remove = function() { // returns first element of sparse array
for (var key in this) {
if (!this.hasOwnProperty(key)) return false;
var value = this[key];
delete this[key];
return {prod: key, perm: value};
}
}
function NorwegianMath() {
var div = [1,1,1,1,1,0,0,0,0,0]; // which numbers 0-9 go in set 0 or 1
var result, min = 99999;
while (div[0]) { // keep zero in group 1 to avoid duplicates
var set = [[],[0]];
for (var i = 1; i < 10; i++) set[div[i]].push(i); // distribute over sets
var dict = [[],[]];
for (var i = 0; i < 2; i++) {
permute(set[i], dict[i]); // generate permutations for each set
}
var x = dict[0].remove(), y = dict[1].remove(); // start with smallest
while (x && y) {
var diff = Math.abs(x.prod - y.prod);
if (diff < min) {
result = {x: x.perm, y: y.perm, d: diff}; // store new minimum
/* if (diff == 0) return result */ // possible early exit here
min = diff;
}
if (x.prod < y.prod) x = dict[0].remove();
else y = dict[1].remove(); // replace smallest premutation with next
}
revLexi(div); // get next distribution into 2 sets of 5
}
return result;
function permute(s, dict) {// there are better permutation algorithms out there
for (var a = 0; a < 5; a++) {
if (s[a] == 0) continue;
for (var b = 0; b < 5; b++) {
if (a == b) continue;
for (var c = 0; c < 5; c++) {
if (a == c || b == c || s[c] == 0) continue;
for (var d = 0; d < 5; d++) {
if (a == d || b == d || c == d) continue;
for (var e = 0; e < 5; e++) {
if (a == e || b == e || c == e || d == e) continue;
var p = (s[a]*10 + s[b]) * (s[c]*100 + s[d]*10 + s[e]);
dict[p] = "" + s[a] + s[b] + "*" + s[c] + s[d] + s[e];
}
}
}
}
}
}
function revLexi(seq) { // next binary sequence (reverse lexicographical)
var max = true, pos = seq.length, set = 1;
while (pos-- && (max || !seq[pos])) if (seq[pos]) ++set; else max = false;
if (pos < 0) return false;
seq[pos] = 0;
while (++pos < seq.length) seq[pos] = set-- > 0 ? 1 : 0;
return true;
}
}
var result = NorwegianMath();
document.write("|" + result.x + " - " + result.y + "| = " + result.d);
