CODEWITHSUNDEEP
carraysalgorithm
Nagy Fathy
Nagy Fathy

Reputation: 21

A unique key for a two dimensional array of letters

I have a two dimensional array of letters. Any letter can vary according to a certain alphabet. I want to make a unique key for this array according to the letters and its position. For example, if the array is 3 * 3 and the alphabet is {0, a, b, c, *}, the array can be in the form like:

0 b c
b * a
a a 0

I have tried Key = sum(code(letter)*(r*3+c)) for all r and c, where r and c are the row and the column, but it still gives me the same key for different array forms.

What do I miss?

P.S. code(letter) is a mapping function to convert the letter into a value.

Upvotes: 2

Views: 185

Answers (1)

Juraj Blaho
Juraj Blaho

Reputation: 13461

You need to take into account the size of alphabet. If code and indices are all zero based it would be:

key = Sum(code(letter)*pow(L, r*C+c))

where L is the number of letters and C is the number of columns. However watch out for numeric overflow. For larger alphabets or matrices you need to use one of the following:

  • Lessen the requirement of keys being unique and use a hash (hash combiner).
  • Larger number type for the key or even unlimited arithmetic type such as in GMP lib.
  • Compression such as arithmetic coding if the distribution of letters is not even. However you still run into the risk of not being able to fit / compress specific matrix into the key.

Upvotes: 3

Related Questions