1

ドキュメントのすべての可能なランキングの可能なランキングを生成する必要がありnます。{1, 2,..., n}配列の順列により、考えられるすべてのランキングのセットが得られることを理解しています。各ドキュメントが 2 つの可能なタイプのいずれかを取る可能性があるため、私の問題はもう少し複雑です。したがって、全部で n!*2 nの可能なランキングがあります。

たとえば、3 つのドキュメント a、b、および c があるとします。次に、可能なランキングは次のとおりです。

a1 b1 c1
a1 b1 c2
a1 b2 c1
a1 b2 c2
a2 b1 c1
a2 b1 c2
a2 b2 c1
a2 b2 c2
a1 c1 b1
a1 c1 b2
a1 c2 b1
a1 c2 b2
a2 c1 b1
a2 c1 b2
a2 c2 b1
a2 c2 b2
b1 a1 c1
b1 a1 c2
b1 a2 c1
b1 a2 c2
b2 a1 c1
b2 a1 c2
...

そのようなランキングを生成するエレガントな方法は何でしょうか?

4

1 に答える 1

2

これは、B={a,b, ...} の順列と T{1,2} の k 個の組み合わせの間の外積の一種です。ここで、k は B の要素の数です。Perm から ap を取得するとします。 (B)、たとえば p=(b,c,a) および 3-Comb(T) からの ac、たとえば c=(2,1,1) の場合、p と c を (b2,c1,a1) にマージします。
それがエレガントかどうかはよくわかりませんが、Bの順列を順次生成するアルゴリズムを選択し（TAOCP Volume 4 fascicle 2bを参照）、順列ごとに、順次生成されたすべてのk組み合わせで上記の「製品」を適用します（またはk が小さい場合は配列に格納されます) ( TAOCP Volume 4 fascicle 3aを参照)。

B={a,b,c, ... }
T={1,2}
k=length(B)

reset_perm(B)
do
  p = next_perm(B)
  reset_comb(T,k)
  do
    c = next_kcomb(T,k)
    output product(p,c)
  while not last_kcomb(T,k)
while not last_perm(B)
于 2012-09-16T13:11:24.143 に答える