1

n我需要为所有可能的文档排名生成可能的排名。我知道数组的排列{1, 2,..., n}会给我所有可能的排名。我的问题有点复杂,因为每个文档都可能采用两种可能类型中的一种。因此,总共有 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 第 4 卷 2b),并且对于每个排列应用上述“产品”以及顺序生成的所有 k 组合(或如果 k 很小,则存储在一个数组中)(参见 TAOCP 第 4 卷分册 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 回答