manitou manitou - 3 months ago 11
C Question

Count permutations - store counter in array

Input:
I have some arrays, like:

1, 2, 3, 4, 5
2, 1, 3, 4, 5
3, 2, 5, 4, 1
5, 4, 3, 1, 2
.....


All of them are non repeating permutations of 5 digits - 5C5. Rows can repeat, but any digit in row is unique.

Aim:
Count how many arrays of each type (permutation) are in input data.

My thoughts:
5C5 says that there's only 120 unique rows can be. So I can store counters in
int[120]
array. And increment them while reading input.

My question:
Is there any efficient algorithm to convert (hash) this array into array index?

Preferable language is C, with it's pointers and manual memory management. In perfect, I'm trying to do something like:

FILE *f;
int counters[120] = {0};
char seq[20];
parse_line(f, seq); #scans and parses string into array
counters[hash(seq)]++;


PS:
I was inspired for this question by solving "UVa 157 - Recycling". Later I saw solutions and understood that I misunderstood task, but question left unanswered.

Answer

Do a base conversion. The first digit is in base 5, the second in base 4, then base 3, and base 2. So, for example:

1, 2, 3, 4, 5 -> 0 * 4*3*2*1 + 0 * 3*2*1 + 0 * 2*1 + 0 * 1 ->   0
2, 1, 3, 4, 5 -> 1 * 4*3*2*1 + 0 * 3*2*1 + 0 * 2*1 + 0 * 1 ->  24
3, 2, 5, 4, 1 -> 2 * 4*3*2*1 + 1 * 3*2*1 + 2 * 2*1 + 1 * 1 ->  59
5, 4, 3, 1, 2 -> 4 * 4*3*2*1 + 3 * 3*2*1 + 2 * 2*1 + 0 * 1 -> 118
5, 4, 3, 2, 1 -> 4 * 4*3*2*1 + 3 * 3*2*1 + 2 * 2*1 + 1 * 1 -> 119

Remember to only count numbers you haven't seen when choosing the digit! Walking carefully through the third row of the above:

3, 2, 5, 4, 1

At first, we have the following mapping of numbers to digits:

1 2 3 4 5
0 1 2 3 4

Since the first number is 3, the first digit is 2. Now we delete 3 from the numbers, giving

1 2 4 5
0 1 2 3

The next number is 2, so the next digit is 1. The mapping is now

1 4 5
0 1 2

The next number is 5, so the next digit is 2. The mapping is now

1 4
0 1

The next number is 4, so the next digit is 1. The last digit will be 0 though it won't contribute anything to the sum -- the last digit is in unary, so it will always be 0. So the numbers 32541 correspond to the digits 21210.

To calculate the value of this number in base 10, we use the usual base conversion routine: we multiply the "column value" by the current column's base, then add in the value of the current digit times the column value. So:

  0 * 1
+ 1 * (1*1)
+ 2 * (2*1*1)
+ 1 * (3*2*1*1)
+ 2 * (4*3*2*1*1)
-----------------
 59

See also the wikipedia page on factorial number systems.

Comments