时间戳

首页 > 解决方案 > 加速排列

python - 加速排列

问题描述

我有下一个任务。

给定整数n( 1 <= n <= 1000000) 和k( 1 <= k <= n)。

需要找到整数的任何排列p，使得排列中1, 2, 3, ..., n每两个连续整数之间的绝对差为>= k，即所有 都p需要排列。abs(p[i] - p[i + 1]) >= ki

n如果给定和k输出不存在这样的排列Impossible。

原始在线任务是波斯语，这就是我不提供链接的原因。

我已经实现了下一个代码。但是解决上述任务非常慢。我怎样才能提高它的速度？

from itertools import permutations

n,k=input('').split(' ')

n=int(n);k=int(k)

def check(n,k):
    n=list(n)
    N=n[:]
    result=[]
    b=n.pop(0)
    while n:
        if abs(b-n[0]) >= k:
            result.append(True)
        b=n.pop(0)
    if len(result)+1 == len(N) and all(result):
        return True
    else:
        return False

def solver(n,k):
    return (i
        for i in (permutations(range(1,n+1)))
        if check(i,k)
    )
try:
    aaa=next(solver(n,k))
    for i in aaa:
        print(i,end=' ')
except :
    print("Impossible")

标签： pythonperformancepermutation

解决方案

当然最简单的优化是check(...)通过使用非常流行的NumPy库来改进功能，只需安装NumPy一次，然后再通过python -m pip install numpy命令行使用下一个代码。

在线尝试！

def check(n, k):
    import numpy as np
    return np.abs(np.diff(n)).min() >= k

但是，如果您的任务的解决方案应该真的快得多，那么我实施了完整的下一个新解决方案，对于大型n（100 万甚至更多）来说应该非常快。此外，我的下一个解决方案不使用任何额外的库，例如numpy.

主要解决功能是solve2(n, k)它返回正确答案的列表（正确性由 双重检查assert），或者答案不存在它返回None。此求解函数的使用示例是test2()函数，例如它为所有小函数n和k组合创建答案。如果求解函数返回，则测试函数在打印前None将其转换为字符串。Impossible

您必须按照您的案例所需的方式实现您自己的变体，例如像您在原始源代码中所做的那样从用户test2()那里获取输入n，我只是举例说明了如何使用我的代码。ktest2()

在线尝试！

def solve2(n, k):
    if k <= 1 or n <= 1:
        p = list(range(n))
    elif n < 2 * k - 1:
        p = None
    elif 2 * k - 1 <= n <= 2 * k + 1:
        p = [None] * n
        cnt, klo = 0, -1
        if n == 2 * k + 1:
            p[0], p[1], p[2], cnt, klo = 0, k, 2 * k, 3, 0
        for i in range(k - 1, klo, -1):
            p[cnt] = i
            cnt += 1
            if cnt >= n:
                break
            p[cnt] = i + k
            cnt += 1
    else:
        if 2 * (k + 1) <= n <= 3 * (k + 1):
            kst = k + 1
        else:
            kst = k
        p = [None] * n
        cnt = 0
        for i in range(kst):
            for j in range(i, n, kst):
                p[cnt] = j
                cnt += 1

    if p is not None:
        assert len(p) == n, (len(p), n)
        p = [(e + 1) for e in p]
        assert all(abs(f - s) >= k for f, s in zip(p[:-1], p[1:]))

    return p

def test2():
    for n in range(1, 16):
        for k in range(1, n + 1):
            answer = solve2(n, k)
            answer = answer if answer is not None else 'Impossible'
            print(n, k, answer, end = '  |  ', flush = True)

test2()

推荐阅读