有趣的运动 [英] interesting exercise
问题描述
我想要一个给定长度的所有有序排列的列表
的代币。每个标记都是一个字符，为方便起见，它们将按照ASCII顺序以字符串形式传递。
例如
permute（" abc"，2）
应该返回[" aa，ab，ac，ba， bb，bc，ca，cb，cc，
和permute（13579，3）应返回125个元素的列表
[" 111，113，...，997，999]
permute （axc，N）或permute（2446，N）应该引发ValueError，因为
字母表没有严格排序。
I有一个相当优雅的解决方案，但它有点冗长（一对夫妇，如果有兴趣的话，我会在稍后发布）。有没有一些好的b
聪明的Python主义我没有发现？
谢谢
mt
Michael Tobis写道：
我想要一个给定长度的所有有序排列的列表一套
的代币。每个标记都是一个字符，为方便起见，它们将按照ASCII顺序以字符串形式传递。
例如
permute（" abc"，2）
应该返回[" aa，ab，ac，ba， bb，bc，ca，cb，cc，
和permute（13579，3）应返回125个元素的列表
[" 111，113，...，997，999]
permute （axc，N）或permute（2446，N）应该引发ValueError，因为
字母表没有严格排序。
I有一个相当优雅的解决方案，但它有点冗长（一对夫妇，如果有兴趣的话，我会在稍后发布）。有没有一些我不知道的聪明的Python主义？
谢谢
mt
1.你应该继续发布它。
2.你检查了xpermutations吗？
http://aspn.activestate.com/ASPN/Coo.../Recipe/190465
James
En Tue，2007年5月8日00:45:52 -0300，Michael Tobis< mt * ***@gmail.com>
$ b $bescribió：
我想要一个给定长度的所有有序排列的列表
的代币。每个标记都是一个字符，为方便起见，它们将按照ASCII顺序以字符串形式传递
。
这就是我来的，没有技巧，没有特别的优化，只是简单的
Python（包括你的约束）：
def permute（values，n）：
def _permute（values，n）：
如果n == 1：
的值为字母：
收益率[letter]
else：
的值为字母：
为_permute中的其他人（值，n-1）：
收益率[字母] +其他
如果没有排序（值） ：raise ValueError（unsorted values）
if len（set（values））！= len（values）：raise ValueError（" duplicate values"）
返回列表（''''。join（item）为_permute中的项目（values，n））
-
Gabriel Genellina
2007年5月7日星期一20:45:52 -0700，Michael Tobis写道：
I有一个相当优雅的解决方案，但它有点冗长（一对夫妇
打几行whi如果有兴趣，我会稍后发布。是否有一些我没有发现的聪明的Python主义？
盯着我的水晶球，我看到你的算法做错了
的事情，并且还包含错误。你当然不需要将
序列分成三个子序列，或者用元类来做这个技巧，
并且使用list更有效。延伸（）而不是总和。
坚持......愚蠢的水晶球...这是别人的代码。也许你
应该在这里发布你的代码，所以我们可以看看它吗？
与此同时，这里有一个简单的生成器来进行排列
重复：
def permute_with_repetitions（seq）：
if len（seq）< = 1：
收益率清单（seq）
else：
for i，item in enumerate（seq）：
for tail in permute_with_repetitions（ seq [：i] + seq [i + 1：]）：
yield [item] + tail
它不会对包含重复项的序列进行测试，我留下
它作为练习来选择更少的物品。
-
史蒂文。
I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.
For example
permute("abc",2)
should return ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]
and permute("13579",3) should return a list of 125 elements
["111","113", ... ,"997","999"]
permute("axc",N) or permute("2446",N) should raise ValueError as the
alphabet is not strictly sorted.
I have a reasonably elegant solution but it''s a bit verbose (a couple
dozen lines which I''ll post later if there is interest). Is there some
clever Pythonism I didn''t spot?
thanks
mt
Michael Tobis wrote:I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.
For example
permute("abc",2)
should return ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]
and permute("13579",3) should return a list of 125 elements
["111","113", ... ,"997","999"]
permute("axc",N) or permute("2446",N) should raise ValueError as the
alphabet is not strictly sorted.
I have a reasonably elegant solution but it''s a bit verbose (a couple
dozen lines which I''ll post later if there is interest). Is there some
clever Pythonism I didn''t spot?
thanks
mt
1. You oughtta go ahead and post it.
2. Have you checked out xpermutations?
http://aspn.activestate.com/ASPN/Coo.../Recipe/190465
James
En Tue, 08 May 2007 00:45:52 -0300, Michael Tobis <mt****@gmail.com>
escribió:
I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.This is what I come, no tricks, no special optimizations, just plain
Python (including your constraints):
def permute(values, n):
def _permute(values, n):
if n==1:
for letter in values:
yield [letter]
else:
for letter in values:
for others in _permute(values, n-1):
yield [letter]+others
if not sorted(values): raise ValueError("unsorted values")
if len(set(values))!=len(values): raise ValueError("duplicate values")
return list(''''.join(item) for item in _permute(values, n))
--
Gabriel Genellina
On Mon, 07 May 2007 20:45:52 -0700, Michael Tobis wrote:
I have a reasonably elegant solution but it''s a bit verbose (a couple
dozen lines which I''ll post later if there is interest). Is there some
clever Pythonism I didn''t spot?Peering into my crystal ball, I see that your algorithm does the wrong
thing, and contains bugs too. You certainly don''t need to partion the
sequence into three sub-sequences, or do that trick with the metaclass,
and it is more efficient to use list.extend() than sum.
Hang on... stupid crystal ball... that''s somebody else''s code. Maybe you
should just post your code here, so we can look at it?
In the meantime, here''s a simple generator to do permutations with
repetition:
def permute_with_repetitions(seq):
if len(seq) <= 1:
yield list(seq)
else:
for i, item in enumerate(seq):
for tail in permute_with_repetitions(seq[:i] + seq[i+1:]):
yield [item] + tail
It doesn''t do a test for the sequence containing duplicates, and I leave
it as an exercise to do selections of fewer items.
--
Steven.
这篇关于有趣的运动的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
