Hex, Bugs and More Physics | Emre S. Tasci

Lately, I’ve been studying on the nice and efficient algorithm of Dominik Endres and he’s been very helpful in replying to my relentless mails about the algorithm and the software. Now, if you have checked the algorithm, there is a part where iteration is needed to be done over the possible bin boundary distributions. Via a smart workaround he avoids this and uses a recursive equation.

For my needs, I want to follow the brute-force approach. To requote the situation, suppose we have K=4 number of classes, let’s label these as 0,1,2,3. There are 3 different ways to group these classes into 2 (M=2-1=1) bins obeying the following rules:

* There is always at least one classification per bin.

* Bins are adjascent to each other.

* Bins can not overlap.

The number of configurations are given by the formula:

N=(K-1)! / ( (K-M-1)! M!)   (still haven’t brought back my latex renderer, sorry for that!)

and these 3 possible configurations for K=4, M=1 are:

|—-|—-|—-|

0            3  : Meaning, the first bin only covers the 0 class while the second bin covers 1, 2, 3.

     1       3 : Meaning, the first bin covers 0, 1 while the second bin covers 2, 3.

         2   3 : Meaning, the first bin covers 0, 1, 2 while the second bin covers 3.

Now, think that you are writing a code to get this values, it is easy when you pseudo-code it:

for k_0 = 0 : K-1-M

   for k_1 = k_0+1 : K-M

      …

         for k_(K-3) = k_(K-4)+1 : K-4

            for k_(K-2) = k_(K-3)+1 : K-3

               print("k_0 – k_1 – … – k_(K-2) – K-1")

            endfor

         endfor

      …

   endfor

endfor

easier said than done because the number of the k_ variables and the for loops are changing with M.

So after some trying in Octave for recursive loops with the help of the feval() function, I gave up and wrote a PHP code that writes an Octave code and it was really fun! 8)

<?
//Support for command line variable passing:
for($i=1;$i<sizeof($_SERVER["argv"]);$i++)
{
    list($var0,$val0) = explode("=",$_SERVER["argv"][$i]);
    $_GET[$var0] = $val0;
}

system("octave ".$_GET["f"]);
?>

Now, if you call this code with for example:

> php genfor.php K=4 M=1

it produces and runs this Octave file lol.m:

count=0;
for k0 = 0:2
    printf("%d – %d\n",k0,3)
    count++;
endfor
if(count!=factorial(4-1)/(factorial(4-1-1)*factorial(1)))
    printf("Houston, we have a problem..");
endif

which outputs:

0 – 3
1 – 3
2 – 3

And you get to keep your hands clean 8)

Later addition (27/6/2008) You can easily modify the code to also give you possible permutations for a set with K items and groups of M items (where ordering is not important). For example, for K=5, say {0,1,2,3,4} and M=4:

0-1-2-3
0-1-2-4
0-1-3-4
0-2-3-4
1-2-3-4

5 (=K!/(M!(K-M)!)) different sets.

The modifications we make to the code are:

* Add an optional parameter that will tell the code that, we want permutation instead of binning:

if($_GET["perm"]||$_GET["p"]||$_GET["P"])
{
    $f_perm = TRUE;
    $K+=1;
}

via the f_perm flag, we can check the type of the operation anywhere within the code. K is incremented because, previously, we were setting the end point fixed so that the last bin would always include the last point for the bins to cover all the space. But for permutationing we are not bounded by this fixication so, we have an additional freedom.

* Previously, we were just including the last point in the print() statement, we should fix this if we are permutating:

$str = "";

for($i=0;$i<$m;$i++)
    $str .= "k".$i.",";
if(!$f_perm) fwrite($fp,$str.($K-1).")\n");
else fwrite($fp, substr($str,0,-1).")\n");

The reason for instead of now writing directly to the file in the iteration we just store it in a variable (str) is to deal with the trailing comma if we are permuting, as simple as that!

and the difference between before and after the modifications is:

sururi@dutsm0175 Octave $ diff genfor.php genfor2.php
10a11,16
> if($_GET["perm"]||$_GET["p"]||$_GET["P"])
> {
>     $f_perm = TRUE;
>     $K+=1;
> }
>
21c27,30
< fwrite($fp, str_repeat("\t",$m)."printf(\"".str_repeat("%d – ",$M)."%d\\n\",");
—
> if(!$f_perm)fwrite($fp, str_repeat("\t",$m)."printf(\"".str_repeat("%d – ",$M)."%d\\n\",");
> else fwrite($fp, str_repeat("\t",$m)."printf(\"".str_repeat("%d – ",($M-1))."%d\\n\",");
>
> $str = "";
24,25c33,35
<     fwrite($fp, "k".$i.",");
< fwrite($fp,($K-1).")\n");
—
>     $str .= "k".$i.",";
> if(!$f_perm) fwrite($fp,$str.($K-1).")\n");
> else fwrite($fp, substr($str,0,-1).")\n");

for the really lazy people (like myself), here is the whole deal! 8)

<?
//Support for command line variable passing:
for($i=1;$i<sizeof($_SERVER["argv"]);$i++)
{
    list($var0,$val0) = explode("=",$_SERVER["argv"][$i]);
    $_GET[$var0] = $val0;
}

system("octave ".$_GET["f"]);
?>

After the modifications,

php genfor.php K=5 M=3 p=1

will produce

0 – 1 – 2
0 – 1 – 3
0 – 1 – 4
0 – 2 – 3
0 – 2 – 4
0 – 3 – 4
1 – 2 – 3
1 – 2 – 4
1 – 3 – 4
2 – 3 – 4