Detect a Symmetric polynomial

8

2

A symmetric polynomial is a polynomial which is unchanged under permutation of its variables.

In other words, a polynomial f(x,y) is symmetric if and only if f(x,y) = f(y,x); a polynomial g(x,y,z) is symmetric iff g(x,y,z) = g(x,z,y) = g(y,x,z) = etc.

For example, x^2+2xy+y^2, xy and x^3+x^2y+xy^2+y^3 are symmetric polynomials, where 2x+y and x^2+y are not.


The challenge

You will be given a polynomial, and your program should output truthy/falsy values, depending on if the given polynomial is a symmetric polynomial.

The input format is allowed in two ways. A string, and an array, like ["x^2","2xy","y^2"], where the polynomial is the sum of each elements.


Example

x^2+2xy+y^2 => true
xy => true
xy+yz+xz-3xyz => true
(x+y)(x-y) => false
2x+y => false
x^2+y => false
x+2y+3 => false

Specs

The operation has orders, just like in normal math. the order is like this:

() => ^ => * => +-

rules apply.

All the characters in the alphabet (a~z) are accepted as variables, everything else are numbers.

The given polynomial will have 2 or more variables.

Multiplication does not require the * operator, You only need to detect juxtaposition. (detecting by juxtaposition is not neccessary, use the better option)

Matthew Roh

Posted 2017-02-04T05:21:00.543

Reputation: 5 043

Question was closed 2017-02-10T13:32:54.603

Is a function a valid input? – Pavel – 2017-02-04T05:36:37.013

@Pavel Write the input format on your answer and I'll consider if it's valid. – Matthew Roh – 2017-02-04T05:38:42.490

I'm fairly certain that, due to Richardson's Theorem, this problem is undecidable.

– Mego – 2017-02-04T05:39:59.887

@Mego Mathematica would like to disagree. – Pavel – 2017-02-04T05:41:20.260

@Mego Of course it's decidable; you can expand each permutation to a sum of terms of the form a^n1 b^n2 c^n3 etc. – feersum – 2017-02-04T05:41:32.400

2Please specify the allowed inputs exactly and include test cases that cover the space well. – xnor – 2017-02-04T07:45:03.130

2I don´t think its fair to ask someone to spend time writing an answer and then you decide if it´s valid. So I agree with @xnor. Also you indicated () => ^ => */ => +- but your examples do not show all these. I would have imagined we could expect - but not /. As you have mentioned () are we expected to handle in the format (-1+x)(-y-3)? – Level River St – 2017-02-04T10:43:22.517

/ is not a valid operation for polynomials, unless applied on constants. Similarly, ^ can only be used to raised variables to integer powers. – orlp – 2017-02-04T13:03:52.397

Edited! Now you might be easier to golf! – Matthew Roh – 2017-02-04T14:43:32.967

Will there ever be a negative sign in the input? For the array format, I assume you mean something like '+'.join(inputlist), so for a negative one item will start with -, making x^2+-x+1? – Rɪᴋᴇʀ – 2017-02-04T14:51:24.647

@EasterlyIrk Yes. – Matthew Roh – 2017-02-04T14:53:20.130

2This is still unclear. Can arbitrary degree polynomials be multiplied? Can operations be done to exponents? Where can minus signs appear? – xnor – 2017-02-04T18:35:10.730

What's the allowed syntax for variables? Also, how do we figure out which variables are involved? 2x+y is symmetrical if you exchange w and z! – None – 2017-02-05T17:03:36.307

Example (x+y)(x-y) => true seems wrong to me – Leo – 2017-02-05T21:55:49.087

@Leo Thanks! Didn't see that. – Matthew Roh – 2017-02-06T03:52:40.140

@ais513 I said two of the given variables. Where the variables are all the alphabetic letters given in the polynomial – Matthew Roh – 2017-02-06T03:54:37.597

1"The input format is allowed in two ways" but they give two very different challenges, and a lot of the "spec" section is irrelevant if the second one if chosen. – Peter Taylor – 2017-02-06T17:49:02.157

Your comments allowing functions as input contradicts the spec. Also, one of the answers uses * for multiplication, which seems to be forbidden by the spec, but you haven't left a comment on that answer. – Dennis – 2017-02-06T18:05:23.683

Answers

5

Maxima, 40 bytes

f(p):=listp(tpartpol(p,showratvars(p)));

Try It Online!

A function that takes a polynomial as input and returns true if it is symmetric else returns false

rahnema1

Posted 2017-02-04T05:21:00.543

Reputation: 5 435

8

Mathematica, 43 bytes

Last@SymmetricReduction[#,Variables@#]===0&

Unnamed function taking as input a polynomial in the given format (except that juxtaposed variables must be separated by a space) and returning True or False. Variables@# detects the variables appearing in the input (and thus the input can contain all kinds of weird variable names, not just single letters). SymmetricReduction returns an ordered pair of polynomials, where the first one is symmetric and the two sum to the original polynomial; therefore we can detect whether the input is symmetric by seeing whether the second polynomial is identically 0.

Greg Martin

Posted 2017-02-04T05:21:00.543

Reputation: 13 940

According to OP, you take input as a function, which could maybe let you golf that more. – Pavel – 2017-02-04T05:40:25.217

1

TI-Basic, 46 bytes

Basically, how this works is the polynomial is entered into a (two-byte) variable type that is dynamically evaluated. Then, we swap the X and Y values enough times to see if the function is symmetric.

Prompt u
For(I,0,8
rand->X
Ans->W
rand->Y
u->Z
Y->X
W->Y
If u=W
End
Ans=9

Timtech

Posted 2017-02-04T05:21:00.543

Reputation: 12 038

I know the spec is shaky, so: this program takes input as a string, works with either juxtaposition or the * operator, and outputs 1 for true and 0 for false. – Timtech – 2017-02-10T12:00:29.250

Sure, that should be enough to detect one. – Matthew Roh – 2017-02-11T12:26:38.123