2

我正在寻找一种仅计算一半可能排列的算法。例如元素 abc 具有以下排列：

美国广播公司

ab

背书

bca

出租车

中央银行

当一个排列与另一个排列相反（以相反的顺序）时，它们被认为是相同的。例如，(abc) ~ (cba)。我需要算法只计算一半的排列。在这种情况下，这将是 (abc) (acb) (bac) 或 (cba) (bca) (cab)。我想不同的 3 组也是可能的，具体取决于算法。

我试过搜索这个算法，我发现所有使用包含函数和置换索引的语言特定算法。我需要一个通用的伪代码。我正在使用 VB.NET

谢谢 ！

4

3 回答 3

4

你可以这样做：

  1. 使用双 for 循环来固定排列的开头和结尾，其中index[end] > index[beginning];
  2. 生成剩余元素的所有排列并将它们放在两者之间。

例如，对于 4 个元素：

a * * b -> a c d b, a d c b
a * * c -> a b d c, a c d b
a * * d -> a b c d, a c b d
b * * c -> b a d c, b d a c
b * * d -> b a c d, b c a d
c * * d -> c a b d, c b a d

由于以这种方式生成排列时，第一个和最后一个元素永远不会是另一个排列的最后一个和第一个元素，并且您正在生成完全n! / 2排列，因此可以保证您只获得所有排列的一半。

于 2013-05-19T21:48:58.420 回答
1

它与生成正常的相同，只是第一个在字典上排在最后。所以你把第一个放在第一位，然后像往常一样把所有更大的词放在最后，把其他放在中间。

如果这样做更简单，此条件也可以用作过滤器以过滤掉不需要的条件。

于 2013-05-19T21:54:43.507 回答
0

感谢您的帮助。我将针对这个问题发布我的伪代码，以防其他人将来需要它：

SET of size (n)
SUBSET of size (n-2)

for i=1 to n
    for j=i+1 to n
        create SUBSET = SET \ { SET[i] , SET[j] }
        do permutations loop, function for SUBSET
        {
          calculate a permutation P for SUBSET
          construct full permutation FP = SET[i] & P & SET[j]
          print or use FP
          continue permutations loop
        }
    next j
next i
于 2013-05-20T11:39:04.160 回答