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 回答