作者uranusjr (←这人是超级笨蛋)
看板Python
标题Re: [问题] 排列组合只取一半
时间Tue Aug 22 03:07:21 2017
※ 引述《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
--
1F：→ GNUGCC:void main(void) 的写法是可行的唷^^08/10 00:59
2F：→ GNUGCC:虽然这个写法较传统,但是语法与文法都正确哦^^08/10 02:16
3F：→ GNUGCC:目前我使用的 Visual C++ 都接受 void main(void) 与 08/10 20:18
4F：→ GNUGCC:int main(void),各位可以把 C++ 专案改成原生 C++ 类型来 08/10 20:19
5F：→ GNUGCC:用 void main(void) 来写发现也可通过编译. 08/10 20:21
6F：→ GNUGCC:这个就是 Visual C++ 的弹性.08/11 20:23
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 218.161.19.12
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Python/M.1503342443.A.93D.html
7F：→ bibo9901: 这样还是 O(n lgn) 08/22 10:28
8F：→ bibo9901: 概念是递回 但实际上可以用回圈做 08/22 10:28