帮助置换算法的一个特例（不是一般的）

我一直感兴趣的算法，分类，加密，二叉树，数据压缩，存储操作等帮助置换算法的一个特例（不是一般的）

，我读过马克·纳尔逊的约排列文章在C++中使用STL函数next_perm（），非常有趣且有用，之后我编写了一个类方法来获得Delphi中的下一个排列，因为这是我目前最常用的工具。这个函数适用于字典顺序，我从另一个主题的答案中得到了算法思路，但现在我遇到了一个很大的问题。我正在用向量中的重复元素进行排列组合，并且有很多我不需要的排列组合。例如，我有在词素文字顺序7层的元件这个第一置换：

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

对于我的工作我考虑有效烫发只有那些具有至多2元件连续地重复，例如：（连续6 = 2次，7 = 2连续次）

总之，我需要仅返回具有至多N个连续重复排列的功能，根据收到的参数。

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

对不起，在文中的任何错误，我仍然不会说英语很好。

太感谢你了，卡洛斯

来源

2008-12-18 Carlos Eduardo Olivieri

作业？如果没有，请解释真实世界的任务最终需要这个，我很感兴趣:) – 2008-12-18 12:52:07

嗨，保罗。是一种功课，不是我老师提出的，而是在课堂上朋友间提出的挑战。：D – 2008-12-18 13:32:07

所以，在作业援助的一种方式，我能想到的两种方法。

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

使用生成algorthm的递归排列（依次选择第一个数字的每个可能性，递归生成其余数字的排列），但是在沿着到目前为止产生的最后两个数字的每个递归遍中。然后在递归调用函数中，如果传入的两个值相同，则不要让第一个数字与这些值相同。

来源

2008-12-18 13:48:28

为什么不在正常置换函数周围打包一个包含N个连续重复值的值？是这样的：

（伪）

funciton custom_perm(int max_rep) 
    do 
    p := next_perm() 
    while count_max_rerps(p) < max_rep 
    return p

来源

2008-12-18 23:04:27

香酥，我已经在做，在函数结尾，而不是解决问题，因为需要生成所有排列，并检查他们每个人一个。

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-18 23:22:00

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

如果你需要建立一个单一的一段代码，只考虑有效的输出，从而不打扰行走在整个组合空间，那么你将不得不认真反思一下。

在另一方面，如果你可以用代码在内部生产所有的组合，有效或不住，那么它应该是简单的。

创建一个新的枚举，其中一个可以调用该方法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-19 18:09:38

我的做法是一个递归发电机不遵循包含非法序列分支。

这里的蟒蛇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)

的implentation为可读性，不写速度，但算法应该比天真地过滤所有排列快得多。

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

例如，它以毫秒为单位运行，其中朴素过滤解决方案需要几千年甚至更久。

来源

2008-12-19 19:52:41 recursive

帮助置换算法的一个特例（不是一般的）

回答

相关问题