Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Instead of iterating over all possible permutations, assume one exists and attempt to construct it. I believe that done in the right way, failure of the algorithm would imply inexistence of the permutation.</p> <p>Here is the outline of the idea applied to the expressions above:</p> <p>let:</p> <pre><code>str1 = "A m * B s / (A m + C m)" str2 = "C m * B s / (C m + A m)" </code></pre> <p>We're looking for a permutation of the set (A, C) that would render the expressions identical. Relabel A and C as X1 and X2 according to the order of their first appearance in str2, so:</p> <pre><code>X1 = C X2 = A </code></pre> <p>because C appears before A in str2. Next, create the array Y such that y[i] is the ith symbol A or C in order of first appearance in str1. So:</p> <pre><code>Y[1] = A Y[2] = C </code></pre> <p>Because A appears before C in str1.</p> <p>Now construct str3 from str2 by replacing A and C with X1 and X2:</p> <pre><code>str3 = "X1 m * B s / (X1 m + X2 m)" </code></pre> <p>And then start substituting Xi for Y[i]. First, X1 becomes Y[1]=A:</p> <pre><code>str3_1 = "A m * Bs / (A m + X2 m)" </code></pre> <p>At this stage, compare str3_1 and str1 up to the first occurrence of any of the Xi's, in this case X2, so because these two strings are equal:</p> <pre><code>str3_1[:18] = "A m * B s / (A m + " str1[:18] = "A m * B s / (A m + " </code></pre> <p>You have a chance of constructing the permutation. If they were unequal, you'd have proven no suitable permutation exists (because any permutation would have had to make at least that substitution) and could deduce inequivalence. But they are equal, so you proceed to the next step, substituting X2 for Y[2]=C:</p> <pre><code>str3_2 = "A m * B s / (A m + C m)" </code></pre> <p>And this is equal to str1, so you have your permutation (A->C, C->A) and have shown the equivalence of the expressions.</p> <p>This is only a demonstration of the algorithm to a particular case, but it should generalize. Not sure what the lowest order you could get it down to is, but it should be quicker than the n! of generating all permutations on n variables.</p> <p>If I understand the significance of the units correctly, they limit which variables may be swapped for which others by the permutations. So that A can be substituted with C in the above expressions because both have 'm' units, but not with B which has 's' units. You can handle this in the following way: </p> <p>construct expressions str1_m and str2_m from str1 and str2 by removing all symbols that don't have m units, and then carry out the above algorithm for str1_m and str2_m. If construction fails, no permutation exists. If construction succeeds, keep that permutation (call it the m-permutation) and construct str1_s and str2_s from str1 and str2 by removing all symbols that don't have s units, then carry out the algorithm again for str1_s and str2_s. If construction fails, they are not equivalent. If it succeeds, the final permutation will be a combination of the m-permutation and the s-permutation (although you probably don't even need to construct it, you just care that it exists).</p>
    singulars
    1. This table or related slice is empty.
    1. POTesting equivalence of mathematical expressions in Python
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USAmos Joshua
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COInteresting approach. I'll read through it more thoroughly tomorrow.
      singulars
      1. PO
      1. USMichael Schubert
    2. COOk, the main issue I see is that it tests for identical expressions, not mathematically equivalent ones. It won't find 2*X = X+X for instance.
      singulars
      1. PO
      1. USMichael Schubert
    3. COIs there some canonical form to algebraic expressions that is afforded by sympy? For instance, you could run things through sympy.together, and then try the above algorithm on the resulting string. I put together some code that implements a simplified version of the above algorithm, I'll post it in a bit.
      singulars
      1. PO
      1. USAmos Joshua
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload