Rearranging Digits – Brute Force Solutions


Posted on December 26, 2016


In this post we will revisit an example from the previous post Rearranging Digits with a brute force coding solution, and expand with an another example (analytically) that is trivial with with a brute force solution. The two examples are:

  1. Geometric Progression: Find all ordered pairs of distinct single-digit positive integers $(A, B, C)$ such that the three 3-digit positive integers $ABC$, $BCA$, and $CAB$ form a geometric progression.
  2. Arithmetic Progression: Find all ordered pairs of distinct single-digit positive integers $(A, B, C, D, E, F)$ such that the four 6-digit positive integers $ABCDEF$, $CDEFAB$, $FABCDE$, and $DEFABC$ form an arithmetic progression.
These solutions will highlight the pros (simplicity and guaranteed solutions) and cons (far less insight) of sacrificing analytic solutions for brute force solutions. These brute force solutions clearly have exponential run time. The algorithmic complexity is not a significant hurdle for three or six digit numbers, but would be for larger numbers. Coding examples will be presented in MATLAB and Python.

In the previous post we walked through a somewhat informed, yet clumsy and incomplete analytic solution that end with a less than satisfying guess and check (not to say there aren’t elegant solutions out there, I didn’t quite get there though).

This can be remedied quite easily by brute forcing our way through each of the $9^3$ possibilities for $A$, $B$, and $C$.  It would look something like this in MATLAB

function [] = three_digit_with_fors()
for a=1:9
    for b=1:9
        for c=1:9
            three_digit_geometric([a, b, c])
        end
    end
end
end %function

This calls the function three_digit_geometric:

function [] = three_digit_geometric(final)
tens = [100 10 1];
N1=dot(final([1 2 3]), tens);
N2=dot(final([2 3 1]), tens);
N3=dot(final([3 1 2]), tens);
 
if N2/N1==N3/N2 && N3~=N2
    fprintf('%d, %d, %d -> ', final);
    fprintf('%d, %d, %d, r=%g \n', N1, N2, N3, N3/N2);
end
end

If we wanted to generalize to higher digit numbers, the for loops would get out of hand pretty quickly, especially in with Python with forced indentation (good luck with PEP 8). To alleviate this (at least for our eyes), let’s generate a recursive function call to put these for loops in.

Now, if you’ve been around the block a bit, you know that python has itertools.permutations and MATLAB has perms – and you could use those.  If you do, be wary of edge cases! The next problem is a rearrangement where some of the digits can be 0, but others are leading digits and therefore cannot. Tread lightly.

Also, perms in MATLAB appears to return the permutations in a large array (as opposed to the memory friendly generator for itertools.permutations in Python). Also, perms is recursively implemented so it’s quite easy to reach max recursive depth.  Just try perms([1:n] for a large enough value of n (11 does it for me on 32-bit MATLAB 2011).

Back to our recursion.  Let’s call the function rfor (short for recursive for).  When given an arbitrary number of arrays, it will recursively loop through them.  This will have the same shortcomings that come with any recursive algorithm, without even writing it one can posit that it will be slower and will risk reaching max recursive depth for large problems.

All of that aside, here’s what rfor would look like in MATLAB

function [] = rfor (current, final_func, level, varargin)
a=varargin;
for i=1:length(a{1})
    current(level) = a{1}(i);
    if length(a)>1
        rfor (current, final_func, level+1, a{2:length(a)})
    else
        feval(final_func, current);
    end
end
end

If you’re wondering whether or not time is saved by tracking the level of recursion instead of dynamically changing the size of the array, a quick benchmark showed a $>10\%$ speedup over the assignment current = [current a{1}(i)];

An example use would be

a=1:9; b=1:9; c=1:9;
rfor([], 'three_digit_geometric', 1, a, b, c);

The output is

4, 3, 2 -> 432, 324, 243, r=0.75 
8, 6, 4 -> 864, 648, 486, r=0.75

In case you aren't familiar with it, varargin is a way to pass a variable number of parameters to a MATLAB function. If the length is 1, we are at the lowest level of recursion required.

Python has an simple implementation as well.

def three_digit_geometric(final):
    tens = [100, 10, 1]
    n1 = sum([tens[i]*final[i] for i in range(len(final))])
    n2 = 10 * (n1 % 100) + n1 // 100
    n3 = 10 * (n2 % 100) + n2 // 100
    if n2 / float(n1) == n3 / float(n2) and n3 != n2:
        print n1, n2, n3, '->', final, 'r=%g' % (n3 / float(n2))


def rfor(current, final_func, level, args):
    for i in args[0]:
        current[level] = i
        if len(args) == 1:
            globals()[final_func](current)
        else:
            rfor(current, final_func, level+1, args[1:])


def main():
    a, b, c = [range(1, 10)] * 3
    rfor([0] * 3, 'three_digit_geometric', 0, [a, b, c])

As a last task, let’s solve one more fun challenge: The four six-digit numbers $ABCDEF$, $CDEFAB$, $FABCDE$, and $DEFABC$ for an arithmetic sequence. Find all possible values of ($A$, $B$, $C$, $D$, $E$, $F$).

This could probably be solved analytically. To avoid 3 equations and 6 unknowns, you would want to treat $AB$ and $DE$ as individual variables, reducing the problem to 4 unknowns (and knowledge of which should be 1-digit a 2-digit). This will be left to the reader as an exercise ;)

Here’s the code for the brute force solution (note how some digits are allowed to be zero but not others).

a=1:9; b=0:9; c=1:9; d=1:9; e=0:9; f=1:9;
rfor([], 'six_digit', a, b, c, d, e, f);

function [] = six_digit(final)
tens = [100000 10000 1000 100 10 1];
N1 = dot(final(1:6), tens);
N2 = dot(final([3:6 1:2]), tens);
N3 = dot(final([6 1:5]), tens);
N4 = dot(final([4:6 1:3]), tens);
 
if N2-N1==N3-N2 && N4-N3==N3-N2 && N3>N2
    fprintf('%d, %d, %d, %d, %d, %d -> ', final);
    fprintf('%d, %d, %d, %d, d=%d \n', N1, N2, N3, N4, N3-N2);
end
end

Here’s the output

1, 0, 2, 5, 6, 4 -> 102564, 256410, 410256, 564102, d=153846 
1, 5, 3, 8, 4, 6 -> 153846, 384615, 615384, 846153, d=230769 
1, 6, 2, 3, 9, 3 -> 162393, 239316, 316239, 393162, d=76923 
2, 1, 3, 6, 7, 5 -> 213675, 367521, 521367, 675213, d=153846 
2, 6, 4, 9, 5, 7 -> 264957, 495726, 726495, 957264, d=230769 
2, 7, 3, 5, 0, 4 -> 273504, 350427, 427350, 504273, d=76923 
3, 2, 4, 7, 8, 6 -> 324786, 478632, 632478, 786324, d=153846 
3, 8, 4, 6, 1, 5 -> 384615, 461538, 538461, 615384, d=76923 
4, 3, 5, 8, 9, 7 -> 435897, 589743, 743589, 897435, d=153846 
4, 9, 5, 7, 2, 6 -> 495726, 572649, 649572, 726495, d=76923 
6, 0, 6, 8, 3, 7 -> 606837, 683760, 760683, 837606, d=76923 
7, 1, 7, 9, 4, 8 -> 717948, 794871, 871794, 948717, d=76923 

So there are $12$ solutions.

Again if you are wondering where these came from, look no further than repeating decimals for fractions with $117$ (one of the many divisors of $999, 999$) in the denominator.