Beschleunigen Sie die Permutation
Ich habe die nächste Aufgabe.
Gegebene ganze Zahlen n( 1 <= n <= 1000000) und k( 1 <= k <= n).
Es ist erforderlich, eine Permutation pvon ganzen Zahlen zu finden, 1, 2, 3, ..., nso dass die absolute Differenz zwischen jeweils zwei aufeinanderfolgenden ganzen Zahlen in der Permutation ist >= k, dh für die Permutation pwird abs(p[i] - p[i + 1]) >= kfür alle benötigt i.
Wenn keine solche Permutation für gegebene nund kdann Ausgabe existiert Impossible.
Die ursprüngliche Online-Aufgabe ist in persischer Sprache, deshalb biete ich keinen Link an.
Ich habe den nächsten Code implementiert. Die Lösung der oben genannten Aufgabe ist jedoch sehr langsam. Wie kann ich die Geschwindigkeit verbessern?
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")
Die einfachste Optimierung besteht natürlich darin, die check(...)Funktion mithilfe der sehr beliebten NumPy- Bibliothek zu verbessern. Installieren Sie sie nur NumPyeinmal, bevor Sie den nächsten Code über die python -m pip install numpyBefehlszeile verwenden.
def check(n, k):
import numpy as np
return np.abs(np.diff(n)).min() >= k
Aber wenn die Lösung für Ihre Aufgabe wirklich sehr viel schneller sein sollte, habe ich die nächste neue Lösung implementiert, die für große Unternehmen sehr schnell sein sollte n(1 Million oder sogar mehr). Auch meine nächsten Lösungen verwenden keine zusätzliche Bibliothek wie numpy.
Die Hauptlösungsfunktion besteht solve2(n, k)darin, dass die Liste mit der richtigen Antwort zurückgegeben wird (die Richtigkeit wird von überprüft assert), oder dass die Antwort nicht vorhanden ist und zurückgegeben wird None. Anwendungsbeispiel Diese Lösungsfunktion ist test2()Funktion, nur zum Beispiel werden Antworten für alle kleinen nund kKombinationen erstellt. Wenn das Lösen von Funktionen eine Testfunktion zurückgibt None, wird diese Impossiblevor dem Drucken in einen String konvertiert .
Sie müssen Ihre eigene Variante test2()der Art und Weise implementieren , wie Sie sie für Ihren Fall benötigen, z. B. Eingaben nund kvom Benutzer, wie Sie es in Ihrem ursprünglichen Quellcode getan haben. Ich habe gerade ein test2()Beispiel für die Verwendung meines Codes erstellt.
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()