python - 如何以最少的轮数按升序收集数字？
问题描述
有人知道如何解决以下问题吗？
取数字 1,...,100000 并以某种方式排列它们。首先，您可以交换两个数字。然后你必须计算按升序收集数字需要多少轮。您必须从左到右收集每一轮的数字。有多少种方法可以在开始时交换两个数字以以最少的轮数按升序收集数字？
例如，如果数字是从 1 到 5，开头的数字依次为 3、1、5、4、2，那么您可以分三轮收集它们：第一轮收集 1、2，第二轮收集 3 , 4 最后是 5。但是您可以通过三种不同的方式进行一次交换以在两轮中收集数字，即
3, 4, 5, 1, 2
3, 1, 4, 5, 2
3, 1, 2, 4, 5
五个数字序列可以通过蛮力轻松解决，我找到了一个收集 1000 个数字的算法，但是 100000 个数字可能需要某种技巧来快速计算开始时特定交换如何影响收集数字所需的轮数。
另一个例子：
按顺序取 10 个数字 [6, 1, 4, 10, 7, 2, 3, 9, 5, 8]。您可以交换 4 和 9 以在三轮中收集数字。但是我的代码返回有 3 种方法可以进行交换。我的错误在哪里？
from bisect import bisect_left, bisect_right
from functools import cmp_to_key
def longest_subsequence(seq, mode='strictly', order='increasing',
key=None, index=False):
bisect = bisect_left if mode.startswith('strict') else bisect_right
# compute keys for comparison just once
rank = seq if key is None else map(key, seq)
if order == 'decreasing':
rank = map(cmp_to_key(lambda x,y: 1 if x<y else 0 if x==y else -1), rank)
rank = list(rank)
if not rank: return []
lastoflength = [0] # end position of subsequence with given length
predecessor = [None] # penultimate element of l.i.s. ending at given position
for i in range(1, len(seq)):
# seq[i] can extend a subsequence that ends with a lesser (or equal) element
j = bisect([rank[k] for k in lastoflength], rank[i])
# update existing subsequence of length j or extend the longest
try: lastoflength[j] = i
except: lastoflength.append(i)
# remember element before seq[i] in the subsequence
predecessor.append(lastoflength[j-1] if j > 0 else None)
# trace indices [p^n(i), ..., p(p(i)), p(i), i], where n=len(lastoflength)-1
def trace(i):
if i is not None:
yield from trace(predecessor[i])
yield i
indices = trace(lastoflength[-1])
return list(indices) if index else [seq[i] for i in indices]
def computerounds(lines):
roundnumber = 1
for i in range(len(lines)-1):
if lines[i] > lines[i + 1]:
roundnumber += 1
return roundnumber
if __name__ == '__main__':
lines = [[3,1,5,4,2],[6, 1, 4, 10, 7, 2, 3, 9, 5, 8]]
case = 1
ways_to_change = len(longest_subsequence(lines[case], mode='strictly', order='decreasing',
key=None, index=False))
print(len(lines[case]), computerounds(lines[case]), ways_to_change)
# Should return 10 3 1
努力一：
我想最难的部分是找到一个排列，以保证您以最少的移动次数收集数字。我还听说 Dilworth 定理告诉我，升序子序列的最小分解等于最大降序子序列的大小。https://artofproblemsolving.com/community/c163h1906044_an_algorithm_to_collect_numbers_in_ascending_order
努力2：
junar9.in我尝试运行 jferard的代码并解决https://www.ohjelmointiputka.net/tiedostot/junar.zip. 该文件包含第一行中的数字数量，然后其余行按照原始顺序给出数字。看起来它占用了太多内存。输出在 Linux Mint 中：
(base) jaakko@jaakko-Aspire-E1-572:~/.config/spyder-py3$ python3 temp.py
Killed
这是来自的代码temp.py
# -*- coding: utf-8 -*-
"""
Spyder Editor
This is a temporary script file.
"""
import os.path
import requests
import zipfile
import warnings
def invert(L):
M = [None] + [0 for _ in range(len(L))]
for i, k in enumerate(L):
M[k] = i
return M
def perform_data(read_data):
s = ""
for i in range(len(read_data)):
if read_data[i].isnumeric():
s += read_data[i]
else:
s += " "
s = s[:-1]
s = s.split(" ")
tmp = []
for i in range(1, len(s)):
if s[i] != '':
tmp.append(int(s[i]))
return tmp
def download_zipfile(url):
if not os.path.isfile('/tmp/junar.zip'):
with open('/tmp/junar.zip', 'wb') as out:
out.write(requests.get(url).content)
def read_zipfile_item(filename):
with zipfile.ZipFile('/tmp/junar.zip') as zip_file:
with zip_file.open(filename) as f:
return f.read().decode('utf8')
def generate_original_rounds(A):
B =[0]*(len(A)-1)
print(A)
roundno = 1
for i in range(1,len(A)):
if A.index(i) < A.index(i+1):
B[i-1] = roundno
else:
roundno += 1
B[i-1] = roundno
print(roundno)
return B
def classify_moves(L):
M = invert(L)
N = len(L)
good_moves, bad_moves = [None], [None]
for k in range(1, N+1):
good_move, bad_move = find_moves(k, L, M, N)
good_moves.append(good_move)
bad_moves.append(bad_move)
return good_moves, bad_moves
def find_moves(k, L, M, N):
def in_range(a, b):
return set(L[j] for j in range(a, b))
good_move = set()
bad_move = set()
if k == 1:
if M[k+1] < M[k]:
good_move |= in_range(0, M[k+1]+1)
else: # M[k] < M[k+1]
bad_move |= in_range(M[k+1], N)
elif k == N:
if M[k] < M[k-1]:
good_move |= in_range(M[k-1], N)
else: # M[k-1] < M[k]
bad_move |= in_range(0, M[k-1]+1)
elif M[k-1] < M[k+1]:
if M[k] < M[k-1]:
good_move |= in_range(M[k-1], M[k+1])
elif M[k+1] < M[k]:
good_move |= in_range(M[k-1]+1, M[k+1]+1)
if M[k-1] < M[k]:
bad_move |= in_range(0, M[k-1]+1)
if M[k] < M[k+1]:
bad_move |= in_range(M[k+1], N)
else: # M[k+1] < M[k-1]
if M[k+1] < M[k] < M[k-1]:
good_move |= in_range(0, M[k+1]+1) | in_range(M[k-1], N)
elif M[k] < M[k+1]:
bad_move |= in_range(M[k+1], M[k-1])
else: # M[k-1] < M[k]:
bad_move |= in_range(M[k+1]+1, M[k-1]+1)
return good_move, bad_move
def collate_moves_aux(L):
good_moves, bad_moves = classify_moves(L)
N = len(L)
swaps_by_removed = {}
for i in range(1, N+1):
for j in range(i+1, N+1):
removed = 0
if j in good_moves[i]:
if i in good_moves[j]:
removed = 2
elif i not in bad_moves[j]:
removed = 1
elif j not in bad_moves[i] and i in good_moves[j]:
removed = 1
if abs(i-j) <= 1: # don't count twice
removed -= 1
if removed > 0:
swaps_by_removed.setdefault(removed, []).append((i,j))
return swaps_by_removed
def collate_moves(L):
swaps_by_removed = collate_moves_aux(L)
if __name__ == '__main__':
# Testing
url = 'https://www.ohjelmointiputka.net/tiedostot/junar.zip'
download_zipfile(url=url)
rawdata = read_zipfile_item('junar9.in')
data = perform_data(rawdata)
numbers = data
A = collate_moves(numbers)
print(A)
想法1：以某种方式计算排列反转是否有帮助， http: //mathworld.wolfram.com/PermutationInversion.html？https://www.geeksforgeeks.org/counting-inversions/中有一些算法可以计算所有排列反转，但这有助于解决问题吗？我认为它在某种程度上与计算形式 (n,n+1) 的排列反转有关。
努力 3：我试图从 jferard 的回答中应用这个想法。我认为它计算错误答案需要多少轮才能收集数字[6, 1, 4, 10, 7, 2, 3, 9, 5, 8]。它返回 4，但需要五轮，第一个 1、2、3，第二个 4、5，第三个 6、7、8，第四个 9，第五个 10。
def compute_original_rounds(M):
c = 1
for i in range(2, len(M)):
if M[i] < M[i-1]:
c += 1
return c
if __name__ == '__main__':
lines = [[3,1,5,4,2],[6, 1, 4, 10, 7, 2, 3, 9, 5, 8]]
verygoods = 0
lista = lines[1]
best = 0
drops = [0,0,0]
for k in range(2,len(lista)):
a = lista.index(k-1)<lista.index(k)
b = lista.index(k)<lista.index(k+1)
c = lista.index(k-1)<lista.index(k+1)
if a and b:
print("Zero inversions")
drops[0] += 1
if (not a and c) or (c and not b) or (b and not c) or (a and not c):
print("One inversion")
best = max(best,1)
drops[1] += 1
if not b and not a:
print("Two inversions")
best = max(best,2)
drops[2] += 1
ways = drops[2]
if ways == 0:
ways = drops[1]
if ways == 0:
ways = drops[0]
original_rounds = compute_original_rounds(lista)
print(original_rounds)
print(len(lista),original_rounds - best, ways)
解决方案
我看不出最长的递减子序列将如何为您提供交换次数。根据 Dilworth 定理，最长的反链（递减数字的子序列）将为您提供列表的宽度，即您可以在列表分区中拥有的最小链数（递增数字的序列）。
请注意，Dilworth 定理可能不适用于此处，因为链（在您的情况下为数字序列）应该是有序的，并且数字必须是连续的（[6, 1, 4, 10, 7, 2, 3, 9, 5, 8]是一个反例：3 Dilworth 的链，但 5 轮）。
这是一个尝试。解决方案很复杂，我希望存在更直接的答案，但我没有找到。我不能肯定地说它没有错误。
计算轮数
要计算 中的轮数O(n)，让我们按照以下方法：
- 开始，
1, 2, 3, ...直到你发现原始列表中的索引k在idx(k+1) < idx(k)哪里idx（我们称之为反转）。 - 第一轮结束，第二轮开始，
k+1, k+2, ...直到你找到一个l有idx(l+1) < idx(l)， - 以此类推，直到列表用完。
因此公式：number of rounds = 1 + |{k in L | pos(k+1)<pos(k)}|。3,1,5,4,2与:idx(3)<idx(2)和的示例idx(5)<idx(4)，因此轮数是3。
在 Python 中：
def invert(L):
M = [None] + [0 for _ in range(len(L))]
for i, k in enumerate(L):
M[k] = i
return M
def rounds(M):
c = 1
for i in range(2, len(M)):
if M[i] < M[i-1]:
c += 1
return c
>>> rounds(invert([3, 1, 5, 4, 2]))
3
>>> rounds(invert([6, 1, 4, 10, 7, 2, 3, 9, 5, 8]))
5
好的和坏的动作
那是容易的部分。现在专注于给定k的L. 你有六种可能性：
... k ... k-1 ... k+1 ... : 1 inversion
... k-1 ... k ... k+1 ... : 0 inversion
... k-1 ... k+1 ... k ... : 1 inversion
... k ... k+1 ... k-1 ... : 1 inversion
... k+1 ... k ... k-1 ... : 2 inversions
... k+1 ... k-1 ... k ... : 1 inversion
我们称“好棋步”为从 1 次反转的情况到 0 次反转的情况，或从 2 次反转到 1 次反转的情况。相反，“坏举动”是从 0 反转到 1 反转或 1 反转到 2 反转的情况的移动。在执行交换时，我们要避免坏动作并做好动作。我们能做的最好的事情就是一次做两个好的动作，将轮数减少2。
首先，我们将计算每一个k好的和坏的动作。我们必须处理边缘情况（k == 1或k == N），以及两种主要可能性（pos(k-1) < pos(k+1)和pos(k+1) < pos(k-1)）。k和k-1or之间的交换也k+1应该考虑。这给出了以下繁琐的代码：
def classify_moves(L):
M = invert(L)
N = len(L)
good_moves, bad_moves = [None], [None]
for k in range(1, N+1):
good_move, bad_move = find_moves(k, L, M, N)
good_moves.append(good_move)
bad_moves.append(bad_move)
return good_moves, bad_moves
def find_moves(k, L, M, N):
def in_range(a, b):
return set(L[j] for j in range(a, b))
good_move = set()
bad_move = set()
if k == 1:
if M[k+1] < M[k]:
good_move |= in_range(0, M[k+1]+1)
else: # M[k] < M[k+1]
bad_move |= in_range(M[k+1], N)
elif k == N:
if M[k] < M[k-1]:
good_move |= in_range(M[k-1], N)
else: # M[k-1] < M[k]
bad_move |= in_range(0, M[k-1]+1)
elif M[k-1] < M[k+1]:
if M[k] < M[k-1]:
good_move |= in_range(M[k-1], M[k+1])
elif M[k+1] < M[k]:
good_move |= in_range(M[k-1]+1, M[k+1]+1)
if M[k-1] < M[k]:
bad_move |= in_range(0, M[k-1]+1)
if M[k] < M[k+1]:
bad_move |= in_range(M[k+1], N)
else: # M[k+1] < M[k-1]
if M[k+1] < M[k] < M[k-1]:
good_move |= in_range(0, M[k+1]+1) | in_range(M[k-1], N)
elif M[k] < M[k+1]:
bad_move |= in_range(M[k+1], M[k-1])
else: # M[k-1] < M[k]:
bad_move |= in_range(M[k+1]+1, M[k-1]+1)
return good_move, bad_move
>>> classify_moves([3, 1, 5, 4, 2])
([None, set(), set(), set(), {1, 5}, {2, 4}], [None, {2}, {1}, {4}, {3}, set()])
这意味着，例如，从4角度来看，与1or的交换5是好的，而与 的交换3是坏的。
选择掉期
现在，我们必须将所有这些好的和坏的移动整理成一个可接受的交换列表。这个想法很简单：对于每对(i,j)，如果i是一个好的移动j和j一个好的移动i，那么我们可以删除两轮。如果i从 开始是一个好的移动j并且i不是一个坏的移动j，那么我们可以删除一轮。还有一些微妙的技巧：1）我们有一个删除 1 轮的交换列表，但是一旦我们找到删除 2 轮的交换（我们能做的最好的），我们就会丢弃这些交换。2) when kis a good move fromk+1和k+1a good move from k，我们不删除两轮，而只删除一个（该classify_moves函数计算了两次好棋）。
def collate_moves_aux(L):
good_moves, bad_moves = classify_moves(L)
N = len(L)
swaps_by_removed = {}
for i in range(1, N+1):
for j in range(i+1, N+1):
removed = 0
if j in good_moves[i]:
if i in good_moves[j]:
removed = 2
elif i not in bad_moves[j]:
removed = 1
elif j not in bad_moves[i] and i in good_moves[j]:
removed = 1
if abs(i-j) <= 1: # don't count twice
removed -= 1
if removed > 0:
swaps_by_removed.setdefault(removed, []).append((i,j))
return swaps_by_removed
def collate_moves(L):
swaps_by_removed = collate_moves_aux(L)
return max(swaps_by_removed.items(), key=lambda i: i[0])
>>> collate_moves_aux([3, 1, 5, 4, 2])
{1: [(1, 4), (2, 5), (4, 5)]}
>>> collate_moves([3, 1, 5, 4, 2])
(1, [(1, 4), (2, 5), (4, 5)])
和：
>>> collate_moves_aux([6, 1, 4, 10, 7, 2, 3, 9, 5, 8])
{1: [(3, 8), (5, 10), (8, 9), (9, 10)], 2: [(4, 9)]}
>>> collate_moves([6, 1, 4, 10, 7, 2, 3, 9, 5, 8])
(2, [(4, 9)])
算法的复杂性是O(N^2)摊销的：invertis O(N)，classify_moves是O(N^2)因为find_movesis O(N)（构建集具有基数 < N）和collate_movesis O(N^2)（摊销）。
希望有人制作一个简单的版本！！！
推荐阅读
- mysql - 删除与 MySQL 中前一行没有区别的行
- sql - 聚合可能不会出现在 WHERE 子句中，除非它位于 HAVING 子句中包含的子查询中
- mysql - 如何在同一个表中选择多行，其中其他行的主键位于单独的列中？
- google-chrome - 重置 Chrome 的“打开方式”设置
- java - Java将for循环转换为lambda表达式
- javascript - 只选择子 div，而不是“孙子”div
- python - 用文本自动填充 SVG 对象（Python / svgwrite）？
- ios - 无法仅将本地 html 文件加载到设备上的 WKWebView 中（适用于模拟器）
- javascript - 登录后反应路由器重定向无法正常工作
- xml - XSLT 将 CDATA 转换为文本