Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I think the easiest way to see why the output vector and the number of steps are the same no matter what index you choose at each step is to look at the problem as a bunch of matrix and vector multiplications. </p> <p>For the case where <code>x</code> has 3 components, think of <code>x</code> as a 3x1 vector: <code>x = [x_0 x_1 x_2]'</code> (where <code>'</code> is the transpose operation). Each iteration of the loop will choose to flip one of <code>x_0,x_1,x_2</code>, and the operation it performs on <code>x</code> is identical to multiplication by one of the following matrices:</p> <pre><code> -1 0 0 1 1 0 1 0 1 s_0 = 1 1 0 s_1 = 0 -1 0 s_2 = 0 1 1 1 0 1 0 1 1 0 0 -1 </code></pre> <p>where multiplication by <code>s_0</code> is the operation performed if the index <code>i=0</code>, <code>s_1</code> corresponds to <code>i=1</code>, and <code>s_2</code> corresponds to <code>i=2</code>. With this view, you can interpret the algorithm as multiplying the corresponding <code>s_i</code> matrix by <code>x</code> at each iteration. So in the first example where <code>x_1</code> is flipped at the start, the algorithm computes: <code>s_1*s_2*s_0*s_1*s_2*s_1[4 -1 -2]' = [0 1 0]'</code></p> <p>The fact that the index you choose doesn't affect the final output vector arises from two interesting properties of the <code>s</code> matrices. First, <code>s_i*s_(i-1)*s_i = s_(i-1)*s_i*s(i-1)</code>, where <code>i-1</code> is computed modulo <code>n</code>, the number of matrices. This property is the only one needed to see why you get the same result in the examples with 3 elements: </p> <p><code>s_1*s_2*s_0*s_1*s_2*s_1 = s_1*s_2*s_0*(s_1*s_2*s_1) = s_1*s_2*s_0*(s_2*s_1*s_2)</code>, which corresponds to choosing <code>x_2</code> at the start, and lastly:</p> <p><code>s_1*s_2*s_0*s_2*s_1*s_2 = s_1*(s_2*s_0*s_2)*s_1*s_2 = s_1*(s_0*s_2*s_0)*s1*s2</code>, which corresponds to choosing to flip <code>x_2</code> at the start, but then choosing to flip <code>x_0</code> in the third iteration.</p> <p>The second property only applies when <code>x</code> has 4 or more elements. It is <code>s_i*s_k = s_k*s_i</code> whenever <code>k &lt;= i-2</code> where <code>i-2</code> is again computed modulo <code>n</code>. This property is apparent when you consider the form of matrices when <code>x</code> has 4 elements:</p> <pre><code> -1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 s_0 = 1 1 0 0 s_1 = 0 -1 0 0 s_2 = 0 1 1 0 s_3 = 0 1 0 0 0 0 1 0 0 1 1 0 0 0 -1 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 1 0 0 0 -1 </code></pre> <p>The second property essentially says that you can exchange the order in which non-conflicting flips occur. For example, in a 4 element vector, if you first flipped <code>x_1</code> and then flipped <code>x_3</code>, this has the same effect as first flipping <code>x_3</code> and then flipping <code>x_1</code>.</p>
    singulars
    1. This table or related slice is empty.
    1. POTurning an array of integers into an array of nonnegative integers
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USgwilkins
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POTurning an array of integers into an array of nonnegative integers
      singulars
      1. PTQuestion
    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. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CONice observation, but still not a proof. Although your transformation is mathematically valid, it is possible that `s_i*s_(i-1)*s_i` is a legal sequence of moves while `s_(i-1)*s_i*s_(i-1)` is not a legal sequence of moves (because only negative numbers can be flipped). So you cannot replace one by the other without reference to the vector on which you are operating.
      singulars
      1. PO
      1. USNemo
    2. COActually, if `s_i*s_(i-1)*s_i` is valid, then you are guaranteed that `s_(i-1)*s_i*s_(i-1)` will also be valid. Take `x = [x_0 ... x_(i-1), x_i, ... x_(n-1)]`. If `s_i*s_(i-1)*s_i` is valid, it implies that both `x_i` and `x_(i-1)` are negative, since first flipping the `i`th element and then flipping the `i-1`th element results in `s_(i-1)*s_i*x=[x_0 ... -x(i)-x_(i-1), x_(i-1), ... x_(n-1)]`. If it is legal to flip the `i`th element (as implied by assuming that `s_i*s_(i-1)*s_i` is legal), then the `i`th element, `x_(i-1)`, is negative. So both `x_i` and `x_(i-1)` are negative.
      singulars
      1. PO
      1. USgwilkins
    3. COThis is a great way to think of it. It's essentially the same as the Coxeter proof which uses Bruhat order on the affine symmetric group (generated by s0 s1 s2 with si^2 = id and the braid relations si si-1 si = si-1 si si-1). Not to spoil the fun, but the number of moves is how many multiplications are required to get back to the identity (inversion number, coxeter length, many other names). Modulo the details, this is fantastic.
      singulars
      1. PO
      1. USPengOne
 

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