Re: Efficient way to store an isomorphism?


"Edsko de Vries" <devriese@xxxxxxxxx> wrote in message
news:1123760098.967374.326650@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> [...] can it be shown that such an improvement is not
> possible?

Easily: The hash function you want specifies a chosen one of N!
permutations of the N items in its range. To specify one of N! permutations
takes ceil(log_2(N!)) bits, which is O(N) words, assuming that words are at
least log_2(N) bits wide.

--
Matt


.