3

私は 2 つの配列を持っています。1 つはトップレベルのカテゴリを含み、もう 1 つはサブカテゴリの長さ > トップレベルのカテゴリの長さのサブカテゴリを含みます。

サブカテゴリをトップレベルのカテゴリに配置できるすべての可能な方法を提供する再帰アルゴリズムを作成しようとしています。たとえば、トップレベルのカテゴリ[A,B,C]とサブカテゴリがある場合、次のよう[W,X,Y,Z]になります。

A->WXYZ, B->null, C->null
A->XYZ,  B->W,    C->null
A->WYZ,  B->X,    C->null
...
A->null, B->Z,    C->WXY
A->null, B->null, C->WXYZ

一見したところ、この問題は典型的な順列アルゴリズムでは解決できないと思いますが、間違っている可能性があります。私は再帰があまり得意ではありません。

ありがとう！

4

2 に答える 2

6

順列も再帰も必要ありません。カウントするだけで済みます。N 個のカテゴリと M 個のサブカテゴリがあるとします。基数 N の M 桁の数字をすべて調べる必要があります。

3 つのカテゴリを取り上げますが、それらを 0、1、および 2 と呼びます。つまり、基数 3 のすべての数字です。次に、基数 3 の 4 桁の数字をすべて見てみましょう。

0000, 0001, 0002, 0010, 0011, 0012, ... , 2212, 2220, 2221, 2222

各番号は、サブカテゴリのカテゴリへの割り当てを表します。最初の桁はサブカテゴリ W、2 番目はサブカテゴリ X、3 番目はサブカテゴリ Y、最後の桁はサブカテゴリ Z です。

したがって、0000 は WXYZ が最初のカテゴリ (例の最初の行) にあることを意味します。1000 が 2 行目、2222 が最後の行などです。

于 2012-06-08T21:43:10.323 に答える
1

これは実際には、あなたが考えたような順列の問題です。

M カテゴリに入れる必要がある N 個のサブカテゴリがあります。これは、星と棒の問題に非常によく似ています。

私はいくつかのコードを書くことができましたが、あなたが読んでくれると良いと思います。

于 2012-06-08T19:25:44.243 に答える