カウント順列 - 配列

Question

入力での店舗カウンター： - 5C5それらのすべてが非5桁の順列を繰り返している

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

： は、私のようないくつかの配列を、持っています。行は繰り返すことができますが、行内の数字は一意です。

目的： 入力データに含まれる各タイプ（置換）の配列数を数えます。

私の考え： 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、2番目の桁は基数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行を通して注意深く歩く：

1 2 3 4 5 
0 1 2 3 4 

最初の数は3あるので、最初の桁が2ある：

3, 2, 5, 4, 1 

を最初に、我々は、桁数の次のマッピングを有します。今、私たちは

1 2 4 5 
0 1 2 3 

を与え、数字から3を削除する次の番号は2あるので、次の桁が1です。マッピングは、次の番号が5で今

1 4 5 
0 1 2 

あるので、次の桁が2です。マッピングは、次の番号が4で今

1 4 
0 1 

あるので、次の桁が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にも、Wikipediaのページを参照してください。

Answer 2

最も単純だがメモリを消費するソリューションは、非衝突ハッシュを作成することです。順列には5桁しか含まれていないと仮定して、配列をnumberに変換します。 numberの最大値は54321のみです。A[54321]を取って、数字と増分カウンタから数値を計算します。
場合のS = S 0 S S ... S _N-1
ハッシュ（S）= S _0：

Theoritically最適衝突フリーハッシュは、発現後有します * M + S * M + S * M ... S _n-1 * M ^n-1
ここで、Mは数字の集合のサイズです。 _iが取ることができます。あなたのケースで

、Mは、ハッシュの
そこで最大値があることが必要である、5であり、nは5である
1 * 5 + 2 * 5 + 3 * 5 + 4 * 5 + 5 * 5 = 3711.