计数排列 - 将计数器存储在数组中

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

另请参阅阶乘数系统的维基百科页面.