граф перестановок - магазин счетчик в массиве

Question

Вход: У меня есть некоторые массивы, например:

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

Все они являются не являющиеся Повторяющимися перестановками из 5 цифр - 5C5. Строки могут повторяться, но любая цифра в ряду уникальна.

Цель: Подсчитайте, сколько массивов каждого типа (перестановка) находится во входных данных.

Мои мысли: 5C5 говорит, что существует только 120 уникальных строк. Поэтому я могу хранить счетчики в массиве int[120]. И увеличивайте их при чтении ввода.

Мой вопрос: Есть ли эффективный алгоритм для преобразования (хэш) этого массива в индекс массива?

Предпочтительный язык - C, с его указателями и ручным управлением памятью. В безупречном, я пытаюсь сделать что-то вроде:

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

PS: Я был вдохновлен на этот вопрос путем решения «UVA 157 - переработка». Позже я увидел решения и понял, что я неправильно понял задачу, но вопрос остался без ответа.

Answer 1

Сделайте базовое преобразование. Первая цифра находится в основании 5, вторая в основании 4, затем в основании 3 и в основании 2.Так, например:

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 

Помните, что только цифры номера вы не видите при выборе цифры! тщательно Проходя через третий ряд выше:

3, 2, 5, 4, 1 

Во-первых, мы имеем следующее отображение чисел в цифр:

1 2 3 4 5 
0 1 2 3 4 

Поскольку первое число 3, первая цифра 2. Теперь мы удалим 3 из чисел, давая

1 2 4 5 
0 1 2 3 

Следующий номер 2, поэтому следующая цифра 1. Отображение теперь

1 4 5 
0 1 2 

следующий номер 5, поэтому следующая цифра 2. Отображение теперь

1 4 
0 1 

следующий номер 4, поэтому следующая цифра 1. Последняя цифра будет 0, хотя она не будет вносить ничего в сумму - последняя цифра находится в унарной, поэтому она всегда будет 0. Таким образом, цифры 32541 соответствуют цифрам 21210.

Чтобы вычислить значение этого числа в базе 10, мы используем обычную базовую процедуру преобразования: умножим значение столбца на базу текущего столбца, а затем добавим значение текущей цифры, умноженное на значение столбца. Итак:

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

Смотрите также страницу Википедии на factorial number systems.

Answer 2

Простейшим, но потребляющим память решением является создание не сталкивающегося хеша. Преобразуйте массив в число, считая, что перестановки содержат только 5 цифр. Максимальное значение числа может быть только 54321. Возьмите A[54321], вычислите число из цифр и счетчика приращений.

Theoritically оптимальное столкновение свободный хэш имеет следующее выражение:
Если S = ​​S 0 с сек ... _{с п-1}
Хэш (S) = S 0 * М + s * М + s * М ... с _n-1 * M ^n-1
где M - размер набора цифр _i можно взять.

В вашем случае М 5 и п равно 5,
Так максимальное значение хэш должен быть
1 * 5 + 2 * 5 + 3 * 5 + 4 * 5 + 5 * 5 = 3711.