Re: C-equivalence aware hash function

In article <dmfph0$3fo@qualcomm.com>, Gregory G Rose <ggr@qualcomm.com> wrote:
>In article <dmfoja$1od3$1@agate.berkeley.edu>,
>David Wagner <daw-usenet@taverner.cs.berkeley.edu> wrote:
> >Francois Grieu wrote:
> >>For some fixed positive n and m, I consider the set S of matrixes
> >>of n rows, m columns, containing elements of the set {-1,0,+1}.
> >>
> >>Two matrixes in S are defined to be C-equivalent when we can go
> >>from one to the other by swaping rows, swaping colums, and/or
> >>changing polarity of whole columns.
> >>
> >>C-equivalence is obviously an equivalence relation.
> >
> >Note that swapping rows commutes with swapping columns, and
> >changing polarity commutes with both.
> >
> >Given a matrix M, you can first canonicalize it with respect to
> >polarity (e.g., by making each column have minimum number of positive
> >elements), then canonicalize it with respect to column-swaps (by
> >sorting the columns), and finally canonicalize it with respect to
> >row-swaps (by sorting the rows). The result will be canonical
> >representative for M with respect to C-equivalent. You can then
> >hash that canonical representative.
> >
> >Does this work?
>
>I don't think so. Sorting the rows might unsort
>the columns. However I believe that the process
>converges after a while; see my other post.
>
>... but now I'm not so sure, I thought I had a
>contrived example but it didn't behave
>pathologically as I expected.
I believe I have a counterexample:
00111
01011
10101
10010
Note that this is already sorted by columns
(defining top as most significant). But
after sorting the rows (defining left to be most
significant):
00111
01011
10010
10101
Now the last two columns are out of order.
Sorting columns again fixes the problem.

This also gives the intuition for a more
efficient, recursive algorithm (if Francois
cares...). For subsequent rounds of sorting, you
only have to consider the leftmost or highest
positions where elements differed. In the above
example, when sorting the rows, the first two
columns didn't change, so in the next round you
only need to sort the last three columns (but
note, the whole columns are still significant).
During that sorting, only the 3rd and 4th rows
changed, so the final sort on rows could be
limited to them... which does nothing so you're
finished.

>I think you're right.

I think I was wrong about you being right. :-)

Greg.

-- 
Greg Rose
232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au