Re: Q on associative binary operation

[BillyGOTO]

"For my ally is Perl, and a powerful ally it is."

On Tue, Aug 12, 2003 at 02:06:43AM -0700, Sarad AV wrote:
> hi,
> 
> how do we complete this table
> 
> Table shown may be completed to define 'associative'
> binary operation * on S={a,b,c,d}. Assume this is
> possible and compute the missing entries

> *|a|b|c|d
> ---------
> a|a|b|c|d
> ---------
> b|b|a|c|d
> ---------
> c|c|d|c|d
> ---------
> d| | | |


Lucky you!  There are only 256 possibilities.

There are four solutions:

The last row can be any of:

   d c c a 

   d c c b 

   d c c c 

   d c c d 

..

#!/usr/bin/perl -w
use strict;

my $optbl = [
    [0,1,2,3],
    [1,0,2,3],
    [2,3,2,3],
];

for(my $i=0; $i<0x100; $i++){
    $optbl->[3] = [
        ($i>>0)&0x3,
        ($i>>2)&0x3,
        ($i>>4)&0x3,
        ($i>>6)&0x3,
    ];
    if(&check_assoc($optbl)){
        for(join(',',@{$optbl->[3]})){
            tr/0123/abcd/;
            print "$_\n";
        }
    }
}

sub check_assoc {
    my $op = shift;
    for(my $i=0;$i<3;$i++){
    for(my $j=0;$j<3;$j++){
    for(my $k=0;$k<3;$k++){
        if( $op->[ $op->[$i][$j]] [ $k            ]
         != $op->[ $i           ] [ $op->[$j][$k] ] )
        {
            return 0;
        }
    } } }
    return 1;
}