※ 引述《ptt0720 (湿湿)》之铭言：
: 最近写题目写到一题
: http://i.imgur.com/vYeB7nL.png
: 要先把字串依照a b c顺序排列好
: 之后进行排列组合
: 然后印出最中间的那一笔
: 我用的方法是itertools的module
: 但是在server进行运算的时候 系统说我超过时间了
: 限制时间是12000ms
: 我的code
: http://i.imgur.com/YvcrD7b.png
: 我在想应该是产生全部排列组合太没有效率了
: 但是又不知道如何生成一半组合就好
推文有提到递回方法
不过 CPython 对递回支援那么差我猜一定爆炸慢, 就不管了
解释一下用 next 的做法
itertools.permutations 是回传一个 permutation iterator
而 Python 内建的 next() 函式可以得到一个 iterator 的“下一个”结果
当你对 iterator 做 for 运算时, Python 其实也就是不断取得下一项
所以像下面的程式
for i in iter('abc'):
print(i)
可以大概翻译成
it = iter('abc')
try:
while True:
i = next(it)
print(i)
except StopIteration: # 代表没有下一个了
pass
那所以你就可以这样找到中间项, 而避免执行整个 iterator
perm_it = itertools.permutations(input_value)
for _ in range(中间项的位置):
next(perm_it)
print('item in the middle:', next(perm_it))
好那下一个问题就是要怎么知道中间项的位置
幸好 permutation 的数量有公式解
Python 没有 product 函式 (如果有 numpy 就简单了)
所以你得自己算
permutation_count = 1
for i in range(1, len(input_value) + 1):
permutation_count *= i
中间项的位置就是 permutation_count // 2 - 1

void main(void) 的写法是可行的唷^^虽然这个写法较传统,但是语法与文法都正确哦^^目前我使用的 Visual C++ 都接受 void main(void) 与int main(void),各位可以把 C++ 专案改成原生 C++ 类型来用 void main(void) 来写发现也可通过编译.这个就是 Visual C++ 的弹性.

这样还是 O(n lgn)概念是递回 但实际上可以用循环做