Advanced Formula Challenge #9: Results and Discussion Reply

Last week I set readers the challenge which can be found here.

One correct solution received, courtesy of Lori, who not only presented a fine construction for working in Excel 2010 and earlier, but also a 2013 version, which had the added benefit of taking advantage of some of the new (and evidently very useful) features of that version to noticeably abridge the required set-up. So many thanks to Lori for sharing this knowledge and also congratulations on an excellent solution to a particularly complex challenge!

Although I will not, unfortunately, be in a position to dissect that 2013 version here (I promise readers that I will try to upgrade soon – not very good promoting advanced Excel techniques if you’re four years behind the latest developments, right? 🙂 ), I imagine (hope?) that the majority of my readers will also be using a pre-2013 set-up, so perhaps it’s not such a great loss!

In fact, the 2010-and-earlier solution I will present differs slightly from that given by Lori, the principal difference being that, whereas Lori went to the effort to first generate a reduced array to pass to our main construction, I took the rather “lazy” approach to process over a larger, unabridged array of values.

This most likely results in a less efficient, more resource-heavy set-up, though it does have the benefit that it considerably reduces the required construction. Nevertheless, the techniques employed by Lori to produce this reduced array are well worth studying, not only from a theoretical point of view, but also considering that we may not always be in a position to afford the “luxury” of passing – as I did – much larger arrays to be processed. As such I will also give a breakdown of those techniques in this post.

The required construction is the following array formula in G2:

=SUM(0+(MMULT(IFERROR(N(OFFSET(A1,IF(MMULT(0+(ISNUMBER(FIND({1,2,3,4},ROW(INDIRECT("1234:4321"))))),{1;1;1;1})=4,MID(ROW(INDIRECT("1234:4321")),{1,2,3,4},1)-1,""),{0,1,2,3},,)),0),{1;1;1;1})=F2))

How does it work?

The premise of this challenge is to form sums over ranges consisting of certain cells only, i.e. subject to the conditions that these ranges comprise four unique cells from our given array and that none of these four cells share the same row or column as any other.

This means, then, that, for the 4×4 case, we are interested in the results of the following sums:

=A1+B2+C3+D4 =A2+B1+C3+D4 =A3+B1+C2+D4 =A4+B1+C2+D3
=A1+B2+C4+D3 =A2+B1+C4+D3 =A3+B1+C4+D2 =A4+B1+C3+D2
=A1+B3+C2+D4 =A2+B3+C1+D4 =A3+B2+C1+D4 =A4+B2+C1+D3
=A1+B3+C4+D2 =A2+B3+C4+D1 =A3+B2+C4+D1 =A4+B2+C3+D1
=A1+B4+C2+D3 =A2+B4+C1+D3 =A3+B4+C1+D2 =A4+B3+C1+D2
=A1+B4+C3+D2 =A2+B4+C3+D1 =A3+B4+C2+D1 =A4+B3+C2+D1

i.e. 24 in total (thanks here to Jeff Weir, who pointed out the general relationship between the required number of permutations and the size of the dataset, which is given by n! for an nxn square.)

Now, this site being one which purports to analyse and promote advanced Excel techniques, clearly we are not going to form a construction involving testing the results of the 24 separate sums as given above! Not only would that be a rather uncultured approach to solving our problem but, more importantly perhaps, were we to wish to extend our solution to consider e.g. the analogous 5X5 or 6×6 cases, then, using Jeff’s formula we would find that the number of required sums to consider would jump from 24 to 120 and 720 respectively, and surely even the most die-hard fans of gigantic formulas would baulk at the task of constructing such a monster.

Instead, we are going to employ a set-up involving OFFSET which, effectively, will produce the same results as the 24 individual sums above though which will be of a considerably more compact form.

Now, looking at those 24 sums as given above, we can deduce that each of those 24 can also be obtained using OFFSET, viz:

=A1+B2+C3+D4

is equivalent to:

=SUM(N(OFFSET(A1,{0,1,2,3},{0,1,2,3})))

And:

=A2+B1+C3+D4

is equivalent to:

=SUM(N(OFFSET(A1,{1,0,2,3},{0,1,2,3})))

And:

=A3+B1+C2+D4

is equivalent to:

=SUM(N(OFFSET(A1,{2,0,1,3},{0,1,2,3})))

etc., etc., the point being that, by fixing the cols parameter as the array {0,1,2,3}, which of course means that each of our four elements will come from each of the four columns, we can then vary the array passed as the rows parameter such that we consider all possible permutations which meet our condition of ensuring that no two elements share the same row.

In effect, then, the 24 rows parameters which, when passed to OFFSET, will generate the equivalent results to the 24 sums given earlier are nothing other than the 24 possible permutations of the set {0,1,2,3}, i.e.:

{0,1,2,3} {1,0,2,3} {2,0,1,3} {3,0,1,2}
{0,1,3,2} {1,0,3,2} {2,0,3,1} {3,0,2,1}
{0,2,1,3} {1,2,0,3} {2,1,0,3} {3,1,0,2}
{0,2,3,1} {1,2,3,0} {2,1,3,0} {3,1,2,0}
{0,3,1,2} {1,3,0,2} {2,3,0,1} {3,2,0,1}
{0,3,2,1} {1,3,2,0} {2,3,1,0} {3,2,1,0}

Now, at present we are no better off here than previously, i.e. we still have 24 individual sums to calculate. However, we are not restricted to passing arrays of one-dimension only to OFFSET: if we could somehow generate an array consisting of all of the above four-element arrays, equivalent to the following:

{0,1,2,3;1,0,2,3;2,0,1,3;3,0,1,2;0,1,3,2;1,0,3,2;2,0,3,1;3,0,2,1;0,2,1,3;1,2,0,3;2,1,0,3;3,1,0,2;0,2,3,1;1,2,3,0;2,1,3,0;3,1,2,0;0,3,1,2;1,3,0,2;2,3,0,1;3,2,0,1;0,3,2,1;1,3,2,0;2,3,1,0;3,2,1,0}

i.e. a 24-row-by-4-column array, each “row” equivalent to one of our 24 permutations as given above, then we could pass this to OFFSET and so achieve our processing of all 24 simultaneously.

In fact, this is precisely what Lori did in the first instance by defining Permutations as:

={1234;1243;1324;1342;1423;1432;2134;2143;2314;2341;2413;2431;3124;3142;3214;3241;3412;3421;4123;4132;4213;4231;4312;4321}

and then manipulating this array further to obtain the desired matrix of parameters to pass to OFFSET.

Of course, whilst this does indeed give the required results, we would nevertheless hope to be able to generate such an array dynamically, even the more so if we were to wish to extend our solution to the analogous 5×5 or 6×6 cases, the latter for which we might not necessarily be thrilled at the idea of having to construct, by hand, a 720-element matrix consisting of all permutations of the integers from 0 to 5.

Unfortunately the task of producing such an array of permutations in Excel is by no means a straightforward one. The only realistic, native means by which we can generate large arrays in Excel is via constructions involving the ROW function. However, this not only limits us in terms of the size of the resulting array (we cannot – at least initially – generate an array of more elements than there are rows in a worksheet, i.e. 1,048,576), but also means that, depending upon our required output, we may end up with many more elements than desired.

Although it is true that we also have at our disposal such functions as SMALL, which, together with a few others such as LARGE, FREQUENCY or MODE.MULT (as used by Lori), possesses the unique ability amongst Excel functions of being able to return an array of a size different to that which was passed to it, it’s often simply not necessary to pare down the array to such an extent: we can, alternatively, simply pass the large array to some IF statement which results in our extraneous elements being excluded from consideration, provided of course we deal with these elements appropriately.

And this is the technique I chose to employ here, which I will now demonstrate.

The first part, then, is to obtain our array of permutations to pass to OFFSET as the rows parameter. The required construction is:

IF(MMULT(0+(ISNUMBER(FIND({1,2,3,4},ROW(INDIRECT("1234:4321"))))),{1;1;1;1})=4,MID(ROW(INDIRECT("1234:4321")),{1,2,3,4},1)-1,"")

Although we will, at least initially, be generating an array of values much larger than necessary, we can at least restrict that array to some degree in the first instance by virtue of the fact that the smallest and largest returns from that array in which we are interested will be 1234 and 4321 (actually it will be 0123 and 3210 which we will ultimately require; however, the first of these, if passed to ROW, would in any case be interpreted as 123, and so our calculation would run over an even larger array than currently. Better to obtain 1234, 1243, 1324, etc. in this way and then manipulate these to 0123, 0132, 0213, etc. later in the formula.)

Processing over an array of 1234:4321 at least makes things a little less resource-heavy than if we were to be supremely lazy and pass instead a whole columns’ worth, i.e. 1:1048576 to ROW.

And so this part:

ROW(INDIRECT("1234:4321"))

will simply generate an array of integers from 1234 to 4321, i.e. (from here on I will just give the results corresponding to the first 91 elements of this array for the sake of brevity):

{1234;1235;1236;1237;1238;1239;1240;1241;1242;1243;1244;1245;1246;1247;1248;1249;1250;1251;1252;1253;1254;1255;1256;1257;1258;1259;1260;1261;1262;1263;1264;1265;1266;1267;1268;1269;1270;1271;1272;1273;1274;1275;1276;1277;1278;1279;1280;1281;1282;1283;1284;1285;1286;1287;1288;1289;1290;1291;1292;1293;1294;1295;1296;1297;1298;1299;1300;1301;1302;1303;1304;1305;1306;1307;1308;1309;1310;1311;1312;1313;1314;1315;1316;1317;1318;1319;1320;1321;1322;1323;1324;...}

We then test each of these as to whether they contain the digits 1, 2, 3 and 4, so that:

FIND({1,2,3,4},ROW(INDIRECT("1234:4321")))

will produce a 3,088-row-by-4-column array, the 12,352 elements of which will be the results of calculating the above FIND function over all 3,088 elements of our above array with each of 1, 2, 3 and 4 as the find_text parameter. The resulting array will be:

{1,2,3,4;1,2,3,#VALUE!;1,2,3,#VALUE!;1,2,3,#VALUE!;1,2,3,#VALUE!;1,2,3,#VALUE!;1,2,#VALUE!,3;1,2,#VALUE!,3;1,2,#VALUE!,3;1,2,4,3;1,2,#VALUE!,3;1,2,#VALUE!,3;1,2,#VALUE!,3;1,2,#VALUE!,3;1,2,#VALUE!,3;1,2,#VALUE!,3;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,4,#VALUE!;1,2,#VALUE!,4;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,4,#VALUE!;1,2,#VALUE!,4;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,4,#VALUE!;1,2,#VALUE!,4;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,4,#VALUE!;1,2,#VALUE!,4;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,4,#VALUE!;1,2,#VALUE!,4;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,2,#VALUE!,#VALUE!;1,#VALUE!,2,#VALUE!;1,#VALUE!,2,#VALUE!;1,4,2,#VALUE!;1,#VALUE!,2,#VALUE!;1,#VALUE!,2,4;1,#VALUE!,2,#VALUE!;1,#VALUE!,2,#VALUE!;1,#VALUE!,2,#VALUE!;1,#VALUE!,2,#VALUE!;1,#VALUE!,2,#VALUE!;1,#VALUE!,2,#VALUE!;1,#VALUE!,2,#VALUE!;1,4,2,#VALUE!;1,#VALUE!,2,#VALUE!;1,#VALUE!,2,4;1,#VALUE!,2,#VALUE!;1,#VALUE!,2,#VALUE!;1,#VALUE!,2,#VALUE!;1,#VALUE!,2,#VALUE!;1,#VALUE!,2,#VALUE!;1,3,2,#VALUE!;1,3,2,#VALUE!;1,3,2,#VALUE!;1,3,2,#VALUE!;1,3,2,4;...}

Since we are interested only in cases where we have a row consisting of four non-error values, we first pass this array to ISNUMBER and coerce the resulting Boolean TRUE/FALSE returns to numerics, so that:

0+(ISNUMBER(FIND({1,2,3,4},ROW(INDIRECT("1234:4321")))))

becomes:

{1,1,1,1;1,1,1,0;1,1,1,0;1,1,1,0;1,1,1,0;1,1,1,0;1,1,0,1;1,1,0,1;1,1,0,1;1,1,1,1;1,1,0,1;1,1,0,1;1,1,0,1;1,1,0,1;1,1,0,1;1,1,0,1;1,1,0,0;1,1,0,0;1,1,0,0;1,1,1,0;1,1,0,1;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,1,0;1,1,0,1;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,1,0;1,1,0,1;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,1,0;1,1,0,1;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,1,0;1,1,0,1;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,1,0,0;1,0,1,0;1,0,1,0;1,1,1,0;1,0,1,0;1,0,1,1;1,0,1,0;1,0,1,0;1,0,1,0;1,0,1,0;1,0,1,0;1,0,1,0;1,0,1,0;1,1,1,0;1,0,1,0;1,0,1,1;1,0,1,0;1,0,1,0;1,0,1,0;1,0,1,0;1,0,1,0;1,1,1,0;1,1,1,0;1,1,1,0;1,1,1,0;1,1,1,1;...}

and then pass this array to MMULT with {1;1;1;1} as the the second array, such that:

MMULT(0+(ISNUMBER(FIND({1,2,3,4},ROW(INDIRECT("1234:4321"))))),{1;1;1;1})

gives:

{4;3;3;3;3;3;3;3;3;4;3;3;3;3;3;3;2;2;2;3;3;2;2;2;2;2;2;2;2;3;3;2;2;2;2;2;2;2;2;3;3;2;2;2;2;2;2;2;2;3;3;2;2;2;2;2;2;2;2;3;3;2;2;2;2;2;2;2;3;2;3;2;2;2;2;2;2;2;3;2;3;2;2;2;2;2;3;3;3;3;4;...}

and finally locate our values of 4 within this array, so that:

MMULT(0+(ISNUMBER(FIND({1,2,3,4},ROW(INDIRECT("1234:4321"))))),{1;1;1;1})=4

returns:

{TRUE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;TRUE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;TRUE;...}

(I have highlighted the three TRUE returns in the above reduced portion of our full array: readers may wish to verify that these correspond to the values of 1234, 1243 and 1324 from our original array produced by ROW.)

Now, for each of those 24 values (1234, 1243, 1324, etc.) which will generate a TRUE in the above IF statement, we want to extract an array of four values consisting of each of those digits, i.e. {1,2,3,4}, {1,2,4,3}, {1,3,2,4}, etc., ready to pass to OFFSET.

We do this using MID with an array of start_num parameters of {1,2,3,4}, so that the value_if_true clause of our IF statement, i.e.:

MID(ROW(INDIRECT("1234:4321")),{1,2,3,4},1)-1

which is:

MID({1234;1235;1236;1237;1238;1239;1240;1241;1242;1243;1244;1245;1246;1247;1248;1249;1250;1251;1252;1253;1254;1255;1256;1257;1258;1259;1260;1261;1262;1263;1264;1265;1266;1267;1268;1269;1270;1271;1272;1273;1274;1275;1276;1277;1278;1279;1280;1281;1282;1283;1284;1285;1286;1287;1288;1289;1290;1291;1292;1293;1294;1295;1296;1297;1298;1299;1300;1301;1302;1303;1304;1305;1306;1307;1308;1309;1310;1311;1312;1313;1314;1315;1316;1317;1318;1319;1320;1321;1322;1323;1324;...},{1,2,3,4},1)-1

gives:

{"1","2","3","4";"1","2","3","5";"1","2","3","6";"1","2","3","7";"1","2","3","8";"1","2","3","9";"1","2","4","0";"1","2","4","1";"1","2","4","2";"1","2","4","3";"1","2","4","4";"1","2","4","5";"1","2","4","6";"1","2","4","7";"1","2","4","8";"1","2","4","9";"1","2","5","0";"1","2","5","1";"1","2","5","2";"1","2","5","3";"1","2","5","4";"1","2","5","5";"1","2","5","6";"1","2","5","7";"1","2","5","8";"1","2","5","9";"1","2","6","0";"1","2","6","1";"1","2","6","2";"1","2","6","3";"1","2","6","4";"1","2","6","5";"1","2","6","6";"1","2","6","7";"1","2","6","8";"1","2","6","9";"1","2","7","0";"1","2","7","1";"1","2","7","2";"1","2","7","3";"1","2","7","4";"1","2","7","5";"1","2","7","6";"1","2","7","7";"1","2","7","8";"1","2","7","9";"1","2","8","0";"1","2","8","1";"1","2","8","2";"1","2","8","3";"1","2","8","4";"1","2","8","5";"1","2","8","6";"1","2","8","7";"1","2","8","8";"1","2","8","9";"1","2","9","0";"1","2","9","1";"1","2","9","2";"1","2","9","3";"1","2","9","4";"1","2","9","5";"1","2","9","6";"1","2","9","7";"1","2","9","8";"1","2","9","9";"1","3","0","0";"1","3","0","1";"1","3","0","2";"1","3","0","3";"1","3","0","4";"1","3","0","5";"1","3","0","6";"1","3","0","7";"1","3","0","8";"1","3","0","9";"1","3","1","0";"1","3","1","1";"1","3","1","2";"1","3","1","3";"1","3","1","4";"1","3","1","5";"1","3","1","6";"1","3","1","7";"1","3","1","8";"1","3","1","9";"1","3","2","0";"1","3","2","1";"1","3","2","2";"1","3","2","3";"1","3","2","4";...}-1

and we then subtract 1 from these values as previously discussed:

{0,1,2,3;0,1,2,4;0,1,2,5;0,1,2,6;0,1,2,7;0,1,2,8;0,1,3,-1;0,1,3,0;0,1,3,1;0,1,3,2;0,1,3,3;0,1,3,4;0,1,3,5;0,1,3,6;0,1,3,7;0,1,3,8;0,1,4,-1;0,1,4,0;0,1,4,1;0,1,4,2;0,1,4,3;0,1,4,4;0,1,4,5;0,1,4,6;0,1,4,7;0,1,4,8;0,1,5,-1;0,1,5,0;0,1,5,1;0,1,5,2;0,1,5,3;0,1,5,4;0,1,5,5;0,1,5,6;0,1,5,7;0,1,5,8;0,1,6,-1;0,1,6,0;0,1,6,1;0,1,6,2;0,1,6,3;0,1,6,4;0,1,6,5;0,1,6,6;0,1,6,7;0,1,6,8;0,1,7,-1;0,1,7,0;0,1,7,1;0,1,7,2;0,1,7,3;0,1,7,4;0,1,7,5;0,1,7,6;0,1,7,7;0,1,7,8;0,1,8,-1;0,1,8,0;0,1,8,1;0,1,8,2;0,1,8,3;0,1,8,4;0,1,8,5;0,1,8,6;0,1,8,7;0,1,8,8;0,2,-1,-1;0,2,-1,0;0,2,-1,1;0,2,-1,2;0,2,-1,3;0,2,-1,4;0,2,-1,5;0,2,-1,6;0,2,-1,7;0,2,-1,8;0,2,0,-1;0,2,0,0;0,2,0,1;0,2,0,2;0,2,0,3;0,2,0,4;0,2,0,5;0,2,0,6;0,2,0,7;0,2,0,8;0,2,1,-1;0,2,1,0;0,2,1,1;0,2,1,2;0,2,1,3;...}

And we can now resolve the full construction, such that:

IF(MMULT(0+(ISNUMBER(FIND({1,2,3,4},ROW(INDIRECT("1234:4321"))))),{1;1;1;1})=4,MID(ROW(INDIRECT("1234:4321")),{1,2,3,4},1)-1,"")

becomes:

IF({TRUE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;TRUE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;TRUE;...},{0,1,2,3;0,1,2,4;0,1,2,5;0,1,2,6;0,1,2,7;0,1,2,8;0,1,3,-1;0,1,3,0;0,1,3,1;0,1,3,2;0,1,3,3;0,1,3,4;0,1,3,5;0,1,3,6;0,1,3,7;0,1,3,8;0,1,4,-1;0,1,4,0;0,1,4,1;0,1,4,2;0,1,4,3;0,1,4,4;0,1,4,5;0,1,4,6;0,1,4,7;0,1,4,8;0,1,5,-1;0,1,5,0;0,1,5,1;0,1,5,2;0,1,5,3;0,1,5,4;0,1,5,5;0,1,5,6;0,1,5,7;0,1,5,8;0,1,6,-1;0,1,6,0;0,1,6,1;0,1,6,2;0,1,6,3;0,1,6,4;0,1,6,5;0,1,6,6;0,1,6,7;0,1,6,8;0,1,7,-1;0,1,7,0;0,1,7,1;0,1,7,2;0,1,7,3;0,1,7,4;0,1,7,5;0,1,7,6;0,1,7,7;0,1,7,8;0,1,8,-1;0,1,8,0;0,1,8,1;0,1,8,2;0,1,8,3;0,1,8,4;0,1,8,5;0,1,8,6;0,1,8,7;0,1,8,8;0,2,-1,-1;0,2,-1,0;0,2,-1,1;0,2,-1,2;0,2,-1,3;0,2,-1,4;0,2,-1,5;0,2,-1,6;0,2,-1,7;0,2,-1,8;0,2,0,-1;0,2,0,0;0,2,0,1;0,2,0,2;0,2,0,3;0,2,0,4;0,2,0,5;0,2,0,6;0,2,0,7;0,2,0,8;0,2,1,-1;0,2,1,0;0,2,1,1;0,2,1,2;0,2,1,3},"";...)

and things become clearer when we resolve this IF statement:

{0,1,2,3;"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";0,1,3,2;"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";0,2,1,3;...}

We can now go ahead and pass this array as the rows parameter to OFFSET, with, as discussed, {0,1,2,3} as the cols parameter, so that:

N(OFFSET(A1,IF(MMULT(0+(ISNUMBER(FIND({1,2,3,4},ROW(INDIRECT("1234:4321"))))),{1;1;1;1})=4,MID(ROW(INDIRECT("1234:4321")),{1,2,3,4},1)-1,""),{0,1,2,3},,))

is now:

N(OFFSET(A1,{0,1,2,3;"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";0,1,3,2;"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";"","","","";0,2,1,3;...},{0,1,2,3},,))

which is:

{1,6,3,2;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;1,6,4,2;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;#VALUE!,#VALUE!,#VALUE!,#VALUE!;1,7,2,2;...}

Resolving the IFERROR clause makes things easier to visualize, so that:

IFERROR(N(OFFSET(A1,IF(MMULT(0+(ISNUMBER(FIND({1,2,3,4},ROW(INDIRECT("1234:4321"))))),{1;1;1;1})=4,MID(ROW(INDIRECT("1234:4321")),{1,2,3,4},1)-1,""),{0,1,2,3},,)),0)

is now:

{1,6,3,2;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;1,6,4,2;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;1,7,2,2;...}

Again, I have highlighted the (in this case non-zero) values in the above array, which, as three groups, correspond to performing each of:

N(OFFSET(A1,{0,1,2,3},{0,1,2,3},,))
N(OFFSET(A1,{0,1,3,2},{0,1,2,3},,))

and:

N(OFFSET(A1,{0,2,1,3},{0,1,2,3},,))

as can easily be verified from the original table.

Again, we can use MMULT here to form the sum of each of these rows consisting of four elements within this matrix, so that:

MMULT(IFERROR(N(OFFSET(A1,IF(MMULT(0+(ISNUMBER(FIND({1,2,3,4},ROW(INDIRECT("1234:4321"))))),{1;1;1;1})=4,MID(ROW(INDIRECT("1234:4321")),{1,2,3,4},1)-1,""),{0,1,2,3},,)),0),{1;1;1;1})

which is:

MMULT({1,6,3,2;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;1,6,4,2;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;0,0,0,0;1,7,2,2;...},{1;1;1;1})

becomes:

{12;0;0;0;0;0;0;0;0;13;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;12;...}

And all that is left is to determine how many values in this array are equal to our target value in F2, 12 in this case, such that:

=SUM(0+(MMULT(IFERROR(N(OFFSET(A1,IF(MMULT(0+(ISNUMBER(FIND({1,2,3,4},ROW(INDIRECT("1234:4321"))))),{1;1;1;1})=4,MID(ROW(INDIRECT("1234:4321")),{1,2,3,4},1)-1,""),{0,1,2,3},,)),0),{1;1;1;1})=F2))

is now:

=SUM(0+({12;0;0;0;0;0;0;0;0;13;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;12;...}=12))

and, although I have not presented the resulting arrays in full during this deconstruction, readers can be assured that the result of the above expression is indeed 6, as desired.

Let’s now finish with a quick look at the method used by Lori to first reduce the array of elements over which we need to process the FIND function.

Recall that I opted here for an array of 3088 elements, generated via the construction:

ROW(INDIRECT("1234:4321"))

Since, out of this array of 3088 elements, we are in fact interested in only 24, i.e. those which are permutations of the string 1234, that’s a not inconsiderable 3064 elements which are extraneous to our calculations, especially when you consider that this figure comprises more than 99% of all the elements within that array.

What Lori did was to first reduce this array to a mere 256 elements: as such, the percentage of elements which are not of interest to us in this array is “improved” to a mere 91% (232/256).

The question of to what degree this improvement in terms of the size of the array over which we process our construction is offset by the necessary increase in function calls is not something I would know, not being one who is inclined towards that branch of Excel which seeks to optimize calculation performance. Suffice to say that, in my opinion, the resulting constructions merit analysis for their own sake, whatever the truth about which offers the more “efficient” set-up.

The construction Lori adopted here was the following:

TEXT(MMULT(MOD(INT((ROW(1:256)-1)/4^{3,2,1,0}),4),10^{3;2;1;0}),"0000")

How does it work?

The reasoning behind this construction belongs not so much to the sphere of Excel as to that of mathematics. Perhaps it will be easier to explain if we consider the analogous construction for the 3×3 square, reducing the number of elements and therefore (hopefully) simplifying the explanation I am about to present.

In that case the equivalent version of Lori’s construction would be:

TEXT(MMULT(MOD(INT((ROW(1:27)-1)/3^{2,1,0}),3),10^{2;1;0}),"000")

Ignoring the TEXT and MMULT functions for the time being, the crux of this construction is to generate an array consisting of triplets of integers which, together, comprise all possible permutations of the digits 0, 1 and 2. That is, an array equivalent to the following:

{0,0,0;0,0,1;0,0,2;0,1,0;0,1,1;0,1,2;0,2,0;0,2,1;0,2,2;1,0,0;1,0,1;1,0,2;1,1,0;1,1,1;1,1,2;1,2,0;1,2,1;1,2,2;2,0,0;2,0,1;2,0,2;2,1,0;2,1,1;2,1,2;2,2,0;2,2,1;2,2,2}

And this is the reason for the 27 in the above construction and also the 256 in Lori’s version for 4 elements: the number of possible permutations for a set of n elements into groups of size n elements is given by n^n (3^3=27 and 4^4=256).

So how does a construction such as:

MOD(INT((ROW(1:27)-1)/3^{2,1,0}),3)

generate such an array?

Effectively what we’re doing here is converting a series of base 10 values to, in this case, base 3. So, taking base 10 values from 0 to 26, we can present a table of their equivalent representation in base 3, viz:

Permutations2

which is of course precisely the 27 permutations we are seeking to generate.

And, for a given value in base 10, in order to determine the quantity of each of 3^2, 3^1 and 3^0 which are present within the base 3 representation of that value, we first determine how many of each of 3^2, 3^1 and 3^0 go into that base 10 value, and then take the modulus (modulo 3) of the resulting values.

For example, the base 10 value 7 will be represented in base 3 as 021, since 3^2 (=9) occurs zero times in 7 and MOD(0,3)=0, 3^1 (=3) occurs twice in 7 and MOD(2,3)=2, and finally 3^0 (=1) occurs 7 times in 7 and MOD(7,3)=1.

For those who do not have a background in mathematics this may seem a touch complex. All I can suggest to those people is that they play around with some of these scenarios until, hopefully, they begin to grasp the essence of how we may represent values in different bases.

This means then that:

MOD(INT((ROW(1:27)-1)/3^{2,1,0}),3)

resolves to:

{0,0,0;0,0,1;0,0,2;0,1,0;0,1,1;0,1,2;0,2,0;0,2,1;0,2,2;1,0,0;1,0,1;1,0,2;1,1,0;1,1,1;1,1,2;1,2,0;1,2,1;1,2,2;2,0,0;2,0,1;2,0,2;2,1,0;2,1,1;2,1,2;2,2,0;2,2,1;2,2,2}

We then combine these triplets into base 10 figures using MMULT with a suitable second array, so that:

MMULT(MOD(INT((ROW(1:27)-1)/3^{2,1,0}),3),10^{2;1;0})

which is:

MMULT({0,0,0;0,0,1;0,0,2;0,1,0;0,1,1;0,1,2;0,2,0;0,2,1;0,2,2;1,0,0;1,0,1;1,0,2;1,1,0;1,1,1;1,1,2;1,2,0;1,2,1;1,2,2;2,0,0;2,0,1;2,0,2;2,1,0;2,1,1;2,1,2;2,2,0;2,2,1;2,2,2},{100;10;1})

gives:

{0;1;2;10;11;12;20;21;22;100;101;102;110;111;112;120;121;122;200;201;202;210;211;212;220;221;222}

and finally we use the TEXT function to fill in the missing zeroes and so generate our required permutations, such that:

TEXT(MMULT(MOD(INT((ROW(1:27)-1)/3^{2,1,0}),3),10^{2;1;0}),"000")

is finally:

{"000";"001";"002";"010";"011";"012";"020";"021";"022";"100";"101";"102";"110";"111";"112";"120";"121";"122";"200";"201";"202";"210";"211";"212";"220";"221";"222"}

as required.

Thanks again to Lori. Another challenge to follow shortly. Watch this space!

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