从排列中删除连续字符

Question

我有一个非常简单的排列脚本来将排列写入文件，还有一个计时器来说明脚本完成需要多长时间。

from itertools import permutations  
import time
start_time = time.time()
str = '012345'

file=open("p1.txt","a")
perm = permutations(str, 6)  
    
for i in perm:  
    file.write(''.join(i))
    file.write('\n')
else:
    print("--- %s seconds ---" % (time.time() - start_time))
file.close()

它给了我 012345 的所有排列。我想尝试实现的是删除前后连续的字符。

例如，如果排列是05314，就可以了。非字符是连续的，无论是向前还是向后。但是，如果排列是 (a) 05324 或 (b) 05231，则这些都不起作用，因为在 (a) 中 2 向后跟随 3，而在 (b) 中 3 跟随 2 向前。

这样的事情可能吗？谢谢。

Answer 1

修改代码以过滤掉排列中的连续对

from itertools import permutations  
import time

start_time = time.time()
s = '012345'            # Don't use str = ... since its masks the builtin function

with open("p1.txt","a") as file:
    perm = permutations(s, 6)  

    for i in perm:  
        if not any(abs(ord(a)-ord(b))==1 for a, b in zip(i, i[1:])):
            # Does not have any consecutive pairs in i
            file.write(str(i))
            file.write('\n')
    else:
        print("--- %s seconds ---" % (time.time() - start_time))

说明

总体思路

数字对 (a, b) 是连续的 increasing/decreasing 当且仅当 (iff) abs(a-b) == 1.
一个列表至少有一对连续的 increasing/decreasing 当且仅当列表中有一个连续的 increasing/decreasing 对。

想法的应用

给定列表 lst，我们可以使用 zip 找到所有连续的对，即 zip(lst, lst[1:])

所以连续的对列表是：

 [(a, b) for a, b in zip(lst, lst[1:])]

所有连续对increasing/decreasing则为：

[(a, b) for a, b in zip(lst, lst[1:]) if abs(a-b)== 1]

我们只关心这个列表中是否至少有一对。我们可以为此使用任何，即

any(abs(a-b) == 1 for a, b in zip(lst, lst[1:]))

以上适用于数字列表，但我们必须对数字列表稍作调整。

any(abs(ord(a) - ord(b)) == 1 for a, b in zip(lst, lst[1:]))

这是通过检查两个字符串数字是否相隔一个来工作的，方法是检查它们的 Unicode 十进制表示是否相隔一个。 Unicode 十进制由 ord 函数提供。注意数字“0”到“9”具有 Unicode 十进制 48 到 57 List of Unicode characters

从排列中删除连续字符

Removing consecutive characters from permutation

python

permutation