订购产品 [英] Ordering Products
问题描述
对于那些喜欢排序
算法的人来说，这可能是一个有趣的谜题（而且我不再是一个学生了，而且问题不是一个
学生' 'homework''但与Python中的一个特殊问题有关的问题我正在开发我的
业余时间。
为了激励我们首先定义一些表达式类：
class Expr：
def __init __（self，name =""）：
self.name = name
self.factors = [self]
def __mul __（self，other）：
p = Expr（）
如果isinstance（其他，Expr）：
other_factors = other.factors
else：
other_factors = [其他]
p.factors = self.factors + other_factors
返回p
def __rmul __（self，other）：
p = M（）
p.factors = [other] + self.factors
返回p
def __repr __（自我）：
如果self.name：
返回self.name
else：
return" *" .join（[str（x ）对于self.factors中的x]）
可以创建Expr对象的任意产品（并将数字
混合到产品中）：
a，b，c = Expr（" a"），Expr（" b"），Expr（" c"）
a * b
a * b 7 * a * 8 * 9
7 * a * 8 * 9
目标是评估此类产品和/或简化它们。
表达式如
x = 7 * a * 8 * 9
这可能很容易，因为我们只需要对因子列表进行排序，然后将
乘以数字。
x.factors.sort（）
x
a * 7 * 8 * 9
- > a * 504
x = 7 * a * b * a * 9
x.factors.sort （）
x
a * a * b * 7 * 9
- > （a ** 2）* b * 63
现在让我们放弃a和b通勤的假设。更一般：让我们来b / b $ M $ b M是M的一个子集，其中X的每个元素与M的每个元素通勤：具有多种因素的产品怎么样？在M中是否需要在附加信息的条件下评估/简化
X？
在因子上检查一些排序算法会很有趣
列出了受约束的项目转置。有什么建议吗？
问候，
凯
Kay Schluehr写道：对于那些喜欢排序算法的人来说，这可能是一个有趣的难题（而且我不再是一个学生而且问题不是一个
学生的'家庭作业''但与Python中的计算机代数系统相关的一个特殊问题我正在我的
业余时间开发。
< fold>
x = 7 * a * b * a * 9
x.factors.sort（）
x
a * a * b * 7 * 9
- > （a ** 2）* b * 63
现在让我们放弃a和b通勤的假设。更一般：让我们用一组表达式和X作为M的子集，其中X的每个元素与M的每个元素通信：如何评估具有M中的因子的产品？ /在附加信息的条件下简化X？
检查具有约束项转置的因子列表上的一些排序算法会很有趣。有什么建议吗？
问候，
凯
看起来很有意思凯。
我认为虽然内置排序可以起到方便的作用，但您需要使用
编写自己更专业的方法，包括排序（解析器排序），
和简化方法，并交替调用它们直到没有进一步的更改
。 （您可以在排序过程中将它们组合为
优化。）
约束排序将是拆分（解析）的组合
列入可排序的子列表并对每个子列表进行排序，可能以不同的方式进行分类，然后重新组合。并且这可能会递归地进行，直到没有进一步的改进或者可以进行。
更一般地说，我认为约束排序算法是一个很好的
想法，也可能有更多的一般用途。
我想到的是一种不是给出
函数的东西，你给它一个排序键列表。然后你可以按任意顺序排序
，具体取决于密钥列表。
sort（alist，[0,1,2,3,4] ，5,6,7,8,9]）＃排序号码前进
sort（alist，[9,8,7,6,5,4,3,2,1,0]） ＃反向排序
sort（alist，[1,3,5,7,9,0,2,4,6,8]）＃Odd-Even sort
sort（alist，[int，str，float]）#sorts types
这些只是建议，我还没有弄清楚细节。它可以通过编写一个
自定义比较函数来获取密钥列表，这可能是目前使用内置的pythons完成的。关键
列表的精细程度也是需要解决的问题。可以吗？
处理单词和整数而不是字母和数字？
如何指定哪个？复杂的物体怎么样？
这里是一个快速排序你可以玩的功能..
有更短的版本，但这有一些优化。
总体而言''比大型
列表中排序的pythons慢大约10倍，但考虑到它是用
python而不是C.写的，这比预期好。
干杯，
Ron
＃快速排序
def qsort（x ）：
如果len（x）< 2：
返回x＃无需排序。
＃已经是排序？
j = min = max = x [0]
我在x中的
：
＃在检查时获取最小值和最大值。
如果我< min：min = i
如果我> max：max = i
如果我< j：＃它不是排序，
休息＃所以停止检查和排序。
j = i
else：
返回x＃It已经排好了。
lt = []
eq = []
gt = []
＃猜猜e基于最小值和最大值的中间值。
mid =（min + max）// 2
＃分为三个列表。
for i in x：
如果我< mid：
lt.append（i）
继续
如果我> mid：
gt.append（i）
继续
eq.append（i）
＃递归划分列表然后重新组合它
＃按顺序返回值。
返回q（lt）+ eq + q（gt ）
Kay Schluehr< kay.schluehr< at> gmx.net>写道：
现在让我们放弃a和b通勤的假设。更一般：让我们用一组表达式和X作为M的子集，其中X的每个元素与M的每个元素通信：如何评估具有M中的因子的产品？ /在附加信息的条件下简化X？
检查具有约束项转置的因子列表上的一些排序算法会很有趣。有什么建议吗？
我不认为排序就是这里的答案。
所有恕我直言的首饰你必须添加
附加约束 - 有问题的操作的相关性
所以问题可以减少到使常数
部分比非部分更具关联性常量部分。
你应该可以用解析器来做
。 BNF语法可能如下所示：
expr :: = v_expr" *" v_expr | v_expr
v_expr :: = variable | c_expr
c_expr :: = l_expr" *"字面意思| l_expr
l_expr :: = literal | "（" expr"）"
诀窍是在常量上创建一个更强大的绑定乘法运算符
比在混合
表达式。
这个语法当然是暧昧的 - 所以一个LL（k）甚至LALR都不会工作。
但是，使用spark实现的earley's方法
应该可以解决问题。
如果我找到时间，我会写一个简短的实现
$ b明天$ b。
Diez
Diez B.Roggisch写道：Kay Schluehr< kay.schluehr< at> gmx.net>写道：
现在让我们放弃a和b通勤的假设。更一般：让我们用一组表达式和X作为M的子集，其中X的每个元素与M的每个元素通信：如何评估具有M中的因子的产品？ /在附加信息的条件下简化X？
检查具有约束项转置的因子列表上的一些排序算法会很有趣。有什么建议吗？
我不认为排序是这里的答案。
所有恕我直言的第一个你必须添加一个
附加约束 - 关联性有问题的操作
因此，问题可以减少到使常数
部分比非常数部分更加联想。
你应该能够做到这一点。解析器。
嗨Diez，
我必须承认我不明白你对<的意思br />
表达式的常量部分？
__mul__的关联性为虚拟
等级M完全填充另外一个__eq__方法是通过比较因子
列表来定义的，因为这些列表总是持平的：
def __eq __（self，other）：
if isinstance（其他，M）：
返回self.factors == other.factors
返回False
排序（或更好''组' g''可以通过以特殊方式排序
来表示）有问题的因素实际上是
（非）交换性问题。对于更高级的表达式，还要分组
属性非常重要：
如果a，b位于G组的中心（即他们与任何人交流） />
元素G）和G提供__add__（除了__mul__并且是
因此是一个环）a + b也在G的中心和（a + b）* c = c *（a + b）
适用于G中的任何c。
不强制扩展会更好（并且效率更高）
产品假定__add__和__mul__的分配和
在单个因子转换后的因子分解，但
立即识别a + b是在G的中心，因为
中心是G的一个子群。
问候，
凯
Here might be an interesting puzzle for people who like sorting
algorithms ( and no I''m not a student anymore and the problem is not a
students ''homework'' but a particular question associated with a
computer algebra system in Python I''m currently developing in my
sparetime ).
For motivation lets define some expression class first:
class Expr:
def __init__(self, name=""):
self.name = name
self.factors = [self]
def __mul__(self, other):
p = Expr()
if isinstance(other,Expr):
other_factors = other.factors
else:
other_factors = [other]
p.factors = self.factors+other_factors
return p
def __rmul__(self, other):
p = M()
p.factors = [other]+self.factors
return p
def __repr__(self):
if self.name:
return self.name
else:
return "*".join([str(x) for x in self.factors])
One can create arbitrary products of Expr objects ( and mixing numbers
into the products ):
a,b,c = Expr("a"),Expr("b"),Expr("c")
a*b a*b 7*a*8*9 7*a*8*9
The goal is to evaluate such products and/or to simplify them.
For expressions like
x = 7*a*8*9
this might be easy, because we just have to sort the factor list and
multiply the numbers.
x.factors.sort()
x a*7*8*9
-> a*504
This can be extended to arbitrary products:
x = 7*a*b*a*9
x.factors.sort()
x
a*a*b*7*9
-> (a**2)*b*63
Now lets drop the assumption that a and b commute. More general: let be
M a set of expressions and X a subset of M where each element of X
commutes with each element of M: how can a product with factors in M be
evaluated/simplified under the condition of additional information X?
It would be interesting to examine some sorting algorithms on factor
lists with constrained item transpositions. Any suggestions?
Regards,
Kay
Kay Schluehr wrote:Here might be an interesting puzzle for people who like sorting
algorithms ( and no I''m not a student anymore and the problem is not a
students ''homework'' but a particular question associated with a
computer algebra system in Python I''m currently developing in my
sparetime ).
<folded>
x = 7*a*b*a*9
x.factors.sort()
x
a*a*b*7*9
-> (a**2)*b*63
Now lets drop the assumption that a and b commute. More general: let be
M a set of expressions and X a subset of M where each element of X
commutes with each element of M: how can a product with factors in M be
evaluated/simplified under the condition of additional information X?
It would be interesting to examine some sorting algorithms on factor
lists with constrained item transpositions. Any suggestions?
Regards,
Kay
Looks interesting Kay.
I think while the built in sort works as a convenience, you will need to
write your own more specialized methods, both an ordering (parser-sort),
and simplify method, and call them alternately until no further changes
are made. (You might be able to combine them in the sort process as an
optimization.)
A constrained sort would be a combination of splitting (parsing) the
list into sortable sub lists and sorting each sub list, possibly in a
different manner, then reassembling it back. And doing that possibly
recursively till no further improvements are made or can be made.
On a more general note, I think a constrained sort algorithm is a good
idea and may have more general uses as well.
Something I was thinking of is a sort where instead of giving a
function, you give it a sort key list. Then you can possibly sort
anything in any arbitrary order depending on the key list.
sort(alist, [0,1,2,3,4,5,6,7,8,9]) # Sort numbers forward
sort(alist, [9,8,7,6,5,4,3,2,1,0]) # Reverse sort
sort(alist, [1,3,5,7,9,0,2,4,6,8]) # Odd-Even sort
sort(alist, [int,str,float]) # sort types
These are just suggestions, I haven''t worked out the details. It could
probably be done currently with pythons built in sort by writing a
custom compare function that takes a key list. How fine grained the key
list is is also something that would need to be worked out. Could it
handle words and whole numbers instead of letters and digits? How does
one specify which? What about complex objects?
Here''s a "quick sort" function that you might be able to play with..
There are shorter versions of this, but this has a few optimizations added.
Overall it''s about 10 times slower than pythons built in sort for large
lists, but that''s better than expected considering it''s written in
python and not C.
Cheers,
Ron
# Quick Sort
def qsort(x):
if len(x)<2:
return x # Nothing to sort.
# Is it already sorted?
j = min = max = x[0]
for i in x:
# Get min and max while checking it.
if i<min: min=i
if i>max: max=i
if i<j: # It''s not sorted,
break # so stop checking and sort.
j=i
else:
return x # It''s already sorted.
lt = []
eq = []
gt = []
# Guess the middle value based on min and max.
mid = (min+max)//2
# Divide into three lists.
for i in x:
if i<mid:
lt.append(i)
continue
if i>mid:
gt.append(i)
continue
eq.append(i)
# Recursively divide the lists then reassemble it
# in order as the values are returned.
return q(lt)+eq+q(gt)
Kay Schluehr <kay.schluehr <at> gmx.net> writes:
Now lets drop the assumption that a and b commute. More general: let be
M a set of expressions and X a subset of M where each element of X
commutes with each element of M: how can a product with factors in M be
evaluated/simplified under the condition of additional information X?
It would be interesting to examine some sorting algorithms on factor
lists with constrained item transpositions. Any suggestions?
I don''t think that sorting is the answer here.
Firts of all IMHO you have to add an
additional constraint - associativity of the operation in question
So the problem could be reduced to making the constant
parts be more associative than the non-constant parts.
which you should be able to
do with a parser. The BNF grammar could look like this:
expr ::= v_expr "*" v_expr | v_expr
v_expr ::= variable | c_expr
c_expr ::= l_expr "*" literal | l_expr
l_expr ::= literal | "(" expr ")"
The trick is to create a stronger-binding multiplication operator on constants
than on mixed
expressions.
This grammar is ambigue of course - so a LL(k) or maybe even LALR won''t work.
But earley''s method
implemented in spark should do the trick.
If I find the time, I''ll write an short implementation
tomorrow.
Diez
Diez B.Roggisch wrote:Kay Schluehr <kay.schluehr <at> gmx.net> writes:Now lets drop the assumption that a and b commute. More general: let be
M a set of expressions and X a subset of M where each element of X
commutes with each element of M: how can a product with factors in M be
evaluated/simplified under the condition of additional information X?
It would be interesting to examine some sorting algorithms on factor
lists with constrained item transpositions. Any suggestions?
I don''t think that sorting is the answer here.
Firts of all IMHO you have to add an
additional constraint - associativity of the operation in question
So the problem could be reduced to making the constant
parts be more associative than the non-constant parts.
which you should be able to
do with a parser.
Hi Diez,
I have to admit that I don''t understand what you mean with the
''constant parts'' of an expression?
The associativity of __mul__ is trivially fullfilled for the dummy
class M if an additional __eq__ method is defined by comparing factor
lists because those lists are always flat:
def __eq__(self, other):
if isinstance(other,M):
return self.factors == other.factors
return False
The sorting ( or better ''grouping'' which can be represented by sorting
in a special way ) of factors in question is really a matter of
(non-)commutativity. For more advanced expressions also group
properties are important:
If a,b are in a center of a group G ( i.e. they commute with any
element of G ) and G supplies an __add__ ( besides a __mul__ and is
therefore a ring ) also a+b is in the center of G and (a+b)*c = c*(a+b)
holds for any c in G.
It would be nice ( and much more efficient ) not to force expansion of
the product assuming distributivity of __add__ and __mul__ and
factorization after the transposition of the single factors but
recognizing immediately that a+b is in the center of G because the
center is a subgroup of G.
Regards,
Kay
这篇关于订购产品的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
