How can I make a hash table for my sequences?

Hi

I have the numbers 1,2,3,4,5,6 and 7 and can arrange them in any order. Thus there are 7! ways to do this meaning 5040 possibilites.

I have a program that works out whether to assign a 1 or 0 to each combination, depending on some long piece of code. To do this I currently have an array 7654321 ints long where I use arr[number], where number = the sequence, eg 1234567 and set that value to either 0 or 1. However, doing this means I have an array with 7654321 ints in it, and not 5040.

I need a nice hash function that maps each of my combinations onto a number from 1 to 5040 inclusive. Is there a nice way to do this?

Thanks

PS the numbers fit nicely into base 8 - and thus base 2.
1234567 can be written as:
(001)(010)(100). . . (111)

Sure, just use three bits for each component, and store it as an integer. 7 digits would use 21 bits, so well within the 32 bits that a normal integer is on a modern machine.

--
Mats

Yes but I only want to have an array 5040 ints long and I don't want to have to serach through the array each time to find the sequqnce I am looking for.

It's easy to store the sequences in a 5040 int array, but the bit I can't do is to make a function that can take my sequence and tell me exactly which one of the 5040 ints my sequeences value is stored in. I don't want to waste time searching the whole array.

Thanks

Something like this (I'm assuming you have a text-string of 0-7 digits - errors will occur if you have invalid data in the string, or if it's shorter than 7 digits):

Code:

---

#define SIZE 7
int hash(char arr[SIZE])
{
    int r;
    int i;
    for(i = 0; i < SIZE; i++)
      r = r << 3 + (arr[i] - '0');
    return r;
}

---

--
Mats

One possible method might be this not-really-recursive method:
Combos that start with 1 start in slot 0; start with 2 start in slot 720, etc.

Now throw away the first digit and reorder (so "4123567" would become "123456" -- the original four was thrown away, and five became four, six became five, and seven became six).
Combos that start with 1 start in slot 0; start with 2 start in slot 120, etc.

Continue until only one digit left; add up all the "starting slots" to get the actual slot.

This should work (although I haven't tested it), but it doesn't seem very efficient.

Hmm - I like tabstop's idea

I don't get why you changed 567 to 456 - "the original four was thrown away, and five became four, six became five, and seven became six"? Without doing this I get the problem shown below, but I don't understand how you chose only to change 567?

So I would take my number, abcdefg and its hash would be

(a*6!)+(b*5!)+. . . . . (f*1!)+(g*0!)

But then I have a problem with numbers like

7654321 and 7654312, where 76543 gives the same number and

(2*1!)+(1*0!) = 2 AND (1*1!)+(2*0!) = 2

Ahhh!

I wonder if this only happens with the last two numbers. . .

Quote:

---

Originally Posted by advancedk

Hmm - I like tabstop's idea

I don't get why you changed 567 to 456 - "the original four was thrown away, and five became four, six became five, and seven became six"? Without doing this I get the problem shown below, but I don't understand how you chose only to change 567?

---

The idea would be to reduce the new problem to 1-6 only, so whatever numbers are above the removed number, slide down to take its place. In other words, after the first number sets the initial range, I want 2134567 and 4123567 and 6123457 to be handled the same way -- those are the first valid combinations starting with 2/4/6, so they should each get the "first" number, and the way to see that is to take out the 2/4/6 and renumber -- in each case you'll get "123456".

You should probably be using (n-1) times the factorial, so that things start at 0, rather than starting at ... some other large number.

Let me walk through it slowly (I would try to use shortcuts when coding, too, but at least let's get the idea right first):

I'm going to make up the number 4635712 and let's see what happens.

First: 4 processes as 3*(6!) = 2160 and we continue with "534612". Then 5 processes as 4*(5!) = 480 and we continue with "34512". 3 processes as 2*(4!) =48 and we continue with "3412". 3 processes as 2*(3!) = 12 and we continue with "312". 3 processes as 2*(2!) = 4 and we continue with "12". 1 processes as 0*(1!)=0 and since there's only one number left, we're done with a total of 2704 as a hash. Note that if we swap 12 and 21, the last step becomes 1*1! and we add one more to get the next number, 2705.

If I've done this right, the next number after that (2706) should correspond to the next combination in numerical order, which is 4637125. Let's see 3*(6!)=2160 and "536124"; 4*(5!)=480 and "35124"; 2*(4!)=48 and "4123"; 3*(3!)=18 and "123"; 0*(2!)=0 and "12", 0*(1!) and done. That adds up to 2706, so yay me.

Edit: In terms of calculating, you need to do n-1 as noted above, and you also need to subtract one for every smaller number you've already processed (in other words, once you've processed one, two counts as one, since it's the lowest remaining number). There's probably several ways to make that work.