如何检查一个序列是否可以变成回文
How to check if a sequence could be turned into a palindrome
我必须找出一个列表是否可以是回文。我程序的第一部分对列表进行排序。
A = [0, 99, 97, 97, 99, 100, 100, 0]
# sorted:
B = [0, 0, 97, 97, 99, 99, 100, 100]
这个列表可以是回文，因为它可以重新排序为：
[0, 97, 99, 100, 100, 99, 97, 0]
我写了下面的代码return如果列表可以是回文就为真
i=0
counter = 0
while i<len(B):
if i+1 < len(B):
if B[i]==B[i+1]:
print(B[i],B[i+1])
i+=2
else:
i+=1
counter += 1
else:
i+=1
if counter<2:
return True
return False
但是，如果我测试列表 [0, 99, 97, 97, 99, 100, 100, 0, 1]，它会进入一个看起来像无限循环的东西。如何正确检查列表是否可能是回文？
如果数字也需要按顺序排列（如 [1,1,2,2,3] 可以，但 [1,1,2,3,3] 不行），这里有一个简单的方法，它只需要将排序的列表按每个拆分2个字符
def palindrome( input ):
B = sorted(input)
#Get every even index
firstPart = B[::2]
#Get every odd index
secondPart = B[1::2]
#Fix for if there's an odd number of indexes
if len(secondPart) < len(firstPart):
secondPart.append( B[-1] )
#Return true or false
return firstPart==secondPart
print palindrome( [0, 99, 97, 97, 99, 100, 0] )
#True
print palindrome( [0, 99, 97, 97, 99, 100, 100, 0] )
#True
print palindrome( [0, 94, 97, 97, 99, 100, 0] )
#False
也缩短了一点，但这样可读性较差：
def palindrome( B ):
B=sorted(B)
if len(B)%2:
B+=[B[-1]]
return B[::2]==B[1::2]
计算每个值出现的次数。然后检查奇数计数是零还是一。无需对列表进行排序。这适用于任何值列表。
from collections import Counter
def can_be_palindrome(data):
odd = (c % 2 for c in Counter(data).values())
any(odd) # skip first odd, if present at all
return not any(odd) # ensure no more odds
print(can_be_palindrome([0, 99, 97, 97, 99, 100, 100, 0])) # only even counts, true
print(can_be_palindrome([0, 99, 97, 97, 99, 100, 100, 0, 1])) # one odd count, true
print(can_be_palindrome([0, 99, 97, 97, 99, 100, 100, 0, 1, 2])) # two odd counts, false
print(can_be_palindrome('abcabcd')) # true
print(can_be_palindrome(['a', 'b', 'a', 1, 1]) # true
当我们遍历 B 时，我们可以使用集合来跟踪到目前为止哪些元素具有奇数（这里使用集合比列表快得多）：
odds = set()
for i in B:
if i in odds:
odds.remove(i)
else:
odds.add(i)
然后如果odds的长度为0或1，打印True。否则打印 False.
print len(odds) <= 1 # prints the value you're looking for
正如@Antti 所指出的，如果您正在优化性能（大约 20% 的速度提升），可以通过在循环之外进行属性查找来加快速度：
odds = set()
remove = odds.remove
add = odds.add
for i in B:
if i in odds:
remove(i)
else:
add(i)
print len(odds) <= 1
一个快速的（或者我认为的）：使用字典来计算 odd 个值。将值作为键存储在字典中，如果键出现奇数次，值为 True，偶数次为 False。最后 return 确实 .values() 只有 0 或 1 个 True 元素（a.k.a。只有 0 或 1 个元素出现奇数次）。
迭代器以短路方式工作。第一个any一遇到第一个True就会returnTrue，否则会扫描整个迭代器。然后我们重新运行 any(odd_iter) - 这个 returns True 如果迭代器产生 another True（a.k.a 奇数）。如果第一个 any 耗尽了迭代器，那么第二个 any 将完全 return False。最后我们从函数中否定这个 return 值和 return 它。
def check_palindrome_sequence(sequence):
odds = {}
for i in sequence:
try:
odds[i] ^= True
except KeyError:
odds[i] = True
odd_iter = iter(odds.values())
any(odd_iter)
return not any(odd_iter)
A = [0, 99, 97, 97, 99, 100, 100, 0]
print(check_palindrome_sequence(A)) # True
A = [0, 99, 97, 97, 99, 100, 100, 0, 1]
print(check_palindrome_sequence(A)) # True
A = [0, 99, 97, 97, 99, 100, 100, 0, 1, 2]
print(check_palindrome_sequence(A)) # False
时间 Python 2.7:
In [1]: %timeit antti(ls)
1 loops, best of 3: 128 ms per loop
In [2]: %timeit davidism(ls)
10 loops, best of 3: 103 ms per loop
In [3]: %timeit leek(ls)
10 loops, best of 3: 42.1 ms per loop
所有 3 个的数据相同：
ls = list(range(100000))
ls *= 2
ls += [ 1, 2 ]
random.shuffle(ls)
计时 Python 3，数据再次相同：
In [1]: %timeit leek(ls)
10 loops, best of 3: 37.4 ms per loop
In [2]: %timeit antti(ls)
10 loops, best of 3: 89.3 ms per loop
In [3]: %timeit davidism(ls)
10 loops, best of 3: 52 ms per loop
韭菜的是完全随机的最好的整体。 nettux 的答案呈二次方变慢，100000 * 2 + 2 个元素必须花费一分钟，我没有耐心计时。
对于作为回文的小值，韭菜几乎是赢家
In [1]: %timeit leek(ls)
100000 loops, best of 3: 2.21 µs per loop
In [2]: %timeit antti(ls)
100000 loops, best of 3: 5.52 µs per loop
In [3]: %timeit davidism(ls)
100000 loops, best of 3: 7.45 µs per loop
我必须找出一个列表是否可以是回文。我程序的第一部分对列表进行排序。
A = [0, 99, 97, 97, 99, 100, 100, 0]
# sorted:
B = [0, 0, 97, 97, 99, 99, 100, 100]
这个列表可以是回文，因为它可以重新排序为：
[0, 97, 99, 100, 100, 99, 97, 0]
我写了下面的代码return如果列表可以是回文就为真
i=0
counter = 0
while i<len(B):
if i+1 < len(B):
if B[i]==B[i+1]:
print(B[i],B[i+1])
i+=2
else:
i+=1
counter += 1
else:
i+=1
if counter<2:
return True
return False
但是，如果我测试列表 [0, 99, 97, 97, 99, 100, 100, 0, 1]，它会进入一个看起来像无限循环的东西。如何正确检查列表是否可能是回文？
如果数字也需要按顺序排列（如 [1,1,2,2,3] 可以，但 [1,1,2,3,3] 不行），这里有一个简单的方法，它只需要将排序的列表按每个拆分2个字符
def palindrome( input ):
B = sorted(input)
#Get every even index
firstPart = B[::2]
#Get every odd index
secondPart = B[1::2]
#Fix for if there's an odd number of indexes
if len(secondPart) < len(firstPart):
secondPart.append( B[-1] )
#Return true or false
return firstPart==secondPart
print palindrome( [0, 99, 97, 97, 99, 100, 0] )
#True
print palindrome( [0, 99, 97, 97, 99, 100, 100, 0] )
#True
print palindrome( [0, 94, 97, 97, 99, 100, 0] )
#False
也缩短了一点，但这样可读性较差：
def palindrome( B ):
B=sorted(B)
if len(B)%2:
B+=[B[-1]]
return B[::2]==B[1::2]
计算每个值出现的次数。然后检查奇数计数是零还是一。无需对列表进行排序。这适用于任何值列表。
from collections import Counter
def can_be_palindrome(data):
odd = (c % 2 for c in Counter(data).values())
any(odd) # skip first odd, if present at all
return not any(odd) # ensure no more odds
print(can_be_palindrome([0, 99, 97, 97, 99, 100, 100, 0])) # only even counts, true
print(can_be_palindrome([0, 99, 97, 97, 99, 100, 100, 0, 1])) # one odd count, true
print(can_be_palindrome([0, 99, 97, 97, 99, 100, 100, 0, 1, 2])) # two odd counts, false
print(can_be_palindrome('abcabcd')) # true
print(can_be_palindrome(['a', 'b', 'a', 1, 1]) # true
当我们遍历 B 时，我们可以使用集合来跟踪到目前为止哪些元素具有奇数（这里使用集合比列表快得多）：
odds = set()
for i in B:
if i in odds:
odds.remove(i)
else:
odds.add(i)
然后如果odds的长度为0或1，打印True。否则打印 False.
print len(odds) <= 1 # prints the value you're looking for
正如@Antti 所指出的，如果您正在优化性能（大约 20% 的速度提升），可以通过在循环之外进行属性查找来加快速度：
odds = set()
remove = odds.remove
add = odds.add
for i in B:
if i in odds:
remove(i)
else:
add(i)
print len(odds) <= 1
一个快速的（或者我认为的）：使用字典来计算 odd 个值。将值作为键存储在字典中，如果键出现奇数次，值为 True，偶数次为 False。最后 return 确实 .values() 只有 0 或 1 个 True 元素（a.k.a。只有 0 或 1 个元素出现奇数次）。
迭代器以短路方式工作。第一个any一遇到第一个True就会returnTrue，否则会扫描整个迭代器。然后我们重新运行 any(odd_iter) - 这个 returns True 如果迭代器产生 another True（a.k.a 奇数）。如果第一个 any 耗尽了迭代器，那么第二个 any 将完全 return False。最后我们从函数中否定这个 return 值和 return 它。
def check_palindrome_sequence(sequence):
odds = {}
for i in sequence:
try:
odds[i] ^= True
except KeyError:
odds[i] = True
odd_iter = iter(odds.values())
any(odd_iter)
return not any(odd_iter)
A = [0, 99, 97, 97, 99, 100, 100, 0]
print(check_palindrome_sequence(A)) # True
A = [0, 99, 97, 97, 99, 100, 100, 0, 1]
print(check_palindrome_sequence(A)) # True
A = [0, 99, 97, 97, 99, 100, 100, 0, 1, 2]
print(check_palindrome_sequence(A)) # False
时间 Python 2.7:
In [1]: %timeit antti(ls)
1 loops, best of 3: 128 ms per loop
In [2]: %timeit davidism(ls)
10 loops, best of 3: 103 ms per loop
In [3]: %timeit leek(ls)
10 loops, best of 3: 42.1 ms per loop
所有 3 个的数据相同：
ls = list(range(100000))
ls *= 2
ls += [ 1, 2 ]
random.shuffle(ls)
计时 Python 3，数据再次相同：
In [1]: %timeit leek(ls)
10 loops, best of 3: 37.4 ms per loop
In [2]: %timeit antti(ls)
10 loops, best of 3: 89.3 ms per loop
In [3]: %timeit davidism(ls)
10 loops, best of 3: 52 ms per loop
韭菜的是完全随机的最好的整体。 nettux 的答案呈二次方变慢，100000 * 2 + 2 个元素必须花费一分钟，我没有耐心计时。
对于作为回文的小值，韭菜几乎是赢家
In [1]: %timeit leek(ls)
100000 loops, best of 3: 2.21 µs per loop
In [2]: %timeit antti(ls)
100000 loops, best of 3: 5.52 µs per loop
In [3]: %timeit davidism(ls)
100000 loops, best of 3: 7.45 µs per loop