2

我一直对算法、排序、加密、二叉树、数据压缩、内存操作等感兴趣。

我用 STL 函数 next_perm() 阅读了 Mark Nelson 关于 C++ 中排列的文章，非常有趣和有用，之后我编写了一个类方法来在 Delphi 中获取下一个排列，因为这是我目前使用最多的工具。这个函数适用于字典顺序，我从stackoverflow上另一个主题的答案中得到了算法的想法，但现在我遇到了一个大问题。我正在处理向量中重复元素的排列，并且有很多我不需要的排列。例如，我有 7 个元素的第一个排列（按字典顺序）：

6667778（6 = 连续 3 次，7 = 连续 3 次）

对于我的工作，我认为有效的烫发只有那些最多连续重复 2 个元素的烫发，如下所示：

6676778（6 = 连续 2 次，7 = 连续 2 次）

简而言之，我需要一个函数，该函数根据收到的参数仅返回最多具有 N 个连续重复的排列。

有谁知道是否有一些算法已经这样做了？

很抱歉文本中的任何错误，我仍然不会说英语。

非常感谢，卡洛斯

4

5 回答 5

2

我的方法是递归生成器，它不遵循包含非法序列的分支。

这是python 3代码：

def perm_maxlen(elements, prefix = "", maxlen = 2):
    if not elements: 
        yield prefix + elements
        return

    used = set()

    for i in range(len(elements)):
        element = elements[i]
        if element in used:
            #already searched this path
            continue

        used.add(element)

        suffix = prefix[-maxlen:] + element
        if len(suffix) > maxlen and len(set(suffix)) == 1:
            #would exceed maximum run length
            continue

        sub_elements = elements[:i] + elements[i+1:]
        for perm in perm_maxlen(sub_elements, prefix + element, maxlen):
            yield perm


for perm in perm_maxlen("6667778"):
    print(perm)

实现是为了可读性而不是速度而编写的，但是该算法应该比简单地过滤所有排列要快得多。

print(len(perm_maxlen("a"*100 + "b"*100, "", 1)))

例如，它以毫秒为单位运行，而朴素的过滤解决方案可能需要数千年的时间。

于 2008-12-19T19:52:41.240 回答
1

所以，在家庭作业帮助的方式中，我可以想到两种方法。

计算出包含 3 个或更多连续重复的所有排列（您可以通过将一行中的三个视为一个伪数字并将其提供给正常的排列生成算法来完成）。制作所有这些的查找表。现在生成原始字符串的所有排列，并在将它们添加到结果之前在查找表中查找它们。

使用递归排列生成算法（依次选择第一个数字的每种可能性，递归以生成剩余数字的排列），但在每个递归中，传递到目前为止生成的最后两个数字。那么在递归调用的函数中，如果传入的两个值相同，则不允许第一个数字与那些相同。

于 2008-12-18T13:48:28.297 回答
1

为什么不围绕正常置换函数制作一个包装器来跳过具有 N 个连续重复的值？就像是：

（伪代码）

funciton custom_perm(int max_rep)
  do
    p := next_perm()
  while count_max_rerps(p) < max_rep
  return p
于 2008-12-18T23:04:27.410 回答
0

Krusty，我已经在函数结束时这样做了，但没有解决问题，因为需要生成所有排列并检查它们。

consecutive := 1;
IsValid := True;
for n := 0 to len - 2 do
begin
    if anyVector[n] = anyVector[n + 1] then
        consecutive := consecutive + 1
    else
        consecutive := 1;
    if consecutive > MaxConsecutiveRepeats then
    begin
        IsValid := False;
        Break;
    end;
end;

由于我确实从字典顺序中的第一个开始，因此最终需要通过这种方式生成许多不必要的烫发。

于 2008-12-18T23:22:00.183 回答
0

这很容易做到，但很难提高效率。

如果您需要构建仅考虑有效输出的单段代码，因此不必费心遍历整个组合空间，那么您将需要考虑一些事情。

另一方面，如果您可以使用内部生成所有组合的代码，无论是否有效，那么它应该很简单。

创建一个新的枚举器，您可以在其上调用 next_perm 方法，并让它在内部使用另一个枚举器，即生成每个组合的枚举器。

然后简单地让外部枚举器在 while 循环中运行，向内部枚举器询问更多排列，直到找到一个有效的排列，然后产生它。

伪代码：

generator1:
    when called, yield the next combination

generator2:
    internally keep a generator1 object
    when called, keep asking generator1 for a new combination
        check the combination
        if valid, then yield it
于 2008-12-19T18:09:38.983 回答