Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This is not an optimal answer, but i would like to share my attempt as someone may improve it. I did not thought about finding a formula to calculate the minimum number of swaps but rather on the optimal algorithm. The algorithm is based on k = 2.</p> <p>The basic idea is based on information gain. Let us assume that A = {[i,j] : 1&lt;=i&lt;=n, 1&lt;=j&lt;=n} represents a <em>configuration</em>. In each step, we have 4 * (n-1) possible swapping to move from one configuration to another configuration. For example if n = 2 (i.e. A = [ {2,2}, {1,1} ] ), then we have 4 possible swapping A[0][0] &lt;-> A[1][0], A[0][0] &lt;-> A[1][1], A[0][1] &lt;-> A[1][0], and A[0][1] &lt;-> A[1][1]. Thus, our objective is to select the swap that has high information gain when we need to move from one configuration to another configuration.</p> <p>The tricky part will be "how to calculate the information gain". In my solution (below), the information gain is based on the distance of a value from its correct position. Let me show you my code (written in C++) to understand what i am trying to say:</p> <pre><code>const int n = 5; const int k = 2; int gain(int item, int from, int to) { if (to &gt; from) return item - to; else return to - item ; } void swap(int &amp;x, int &amp;y) { int temp = x; x = y; y = temp; } void print_config (int A[][k]) { cout &lt;&lt; "["; for (int i=0; i&lt;n; i++) { cout &lt;&lt; " ["; for (int j=0; j&lt;k; j++) { cout &lt;&lt; A[i][j] &lt;&lt; ", "; } cout &lt;&lt; "\b\b], "; } cout &lt;&lt; "\b\b ]" &lt;&lt; endl; } void compute (int A[][k], int G[][4]) { for (int i=0; i&lt;n-1; i++) { G[i][0] = gain(A[i][0], i+1, i+2) + gain(A[i+1][0], i+2, i+1); G[i][1] = gain(A[i][0], i+1, i+2) + gain(A[i+1][1], i+2, i+1); G[i][2] = gain(A[i][1], i+1, i+2) + gain(A[i+1][0], i+2, i+1); G[i][3] = gain(A[i][1], i+1, i+2) + gain(A[i+1][1], i+2, i+1); } } int main() { int A[n][k]; int G[n-1][k*k]; // construct initial configuration for (int i=0; i&lt;n; i++) for (int j=0; j&lt;k; j++) A[i][j] = n-i; print_config(A); int num_swaps = 0; int r, c; int max_gain; do { compute (A, G); // which swap has high info gain max_gain = -1; for (int i=0; i&lt;n-1; i++) for (int j=0; j&lt;k*k; j++) if (G[i][j] &gt; max_gain) { r = i; c = j; max_gain = G[i][j]; } // Did we gain more information. If not terminate if (max_gain &lt; 0) break; switch (c) { case 0: swap(A[r][0], A[r+1][0]); break; case 1: swap(A[r][0], A[r+1][1]); break; case 2: swap(A[r][1], A[r+1][0]); break; case 3: swap(A[r][1], A[r+1][1]); break; } print_config(A); num_swaps++; } while (1); cout &lt;&lt; "Number of swaps is " &lt;&lt; num_swaps &lt;&lt; endl; } </code></pre> <p>I ran the above code for cases n=1,2,... and 7. Here are the answers (number of swaps) respectively: 0, 2, 5, 10, 15, 23 (very close), and 31. I think that the function gain() does not work well when n is even. Can you confirm that by validating the number of swaps when n = 7. The lower bound of your equation is 31 so this is the optimal number of swaps when n = 7. </p> <p>I am printing here the output when n = 5 (since you are looking for a pattern):</p> <pre><code>[ [5, 5], [4, 4], [3, 3], [2, 2], [1, 1] ] [ [4, 5], [5, 4], [3, 3], [2, 2], [1, 1] ] [ [4, 5], [3, 4], [5, 3], [2, 2], [1, 1] ] [ [4, 5], [3, 4], [2, 3], [5, 2], [1, 1] ] [ [4, 5], [3, 4], [2, 3], [1, 2], [5, 1] ] [ [4, 3], [5, 4], [2, 3], [1, 2], [5, 1] ] [ [4, 3], [2, 4], [5, 3], [1, 2], [5, 1] ] [ [4, 3], [2, 4], [1, 3], [5, 2], [5, 1] ] [ [4, 3], [2, 4], [1, 3], [1, 2], [5, 5] ] [ [4, 3], [2, 1], [4, 3], [1, 2], [5, 5] ] [ [1, 3], [2, 4], [4, 3], [1, 2], [5, 5] ] [ [1, 3], [2, 4], [1, 3], [4, 2], [5, 5] ] [ [1, 3], [2, 1], [4, 3], [4, 2], [5, 5] ] [ [1, 1], [2, 3], [4, 3], [4, 2], [5, 5] ] [ [1, 1], [2, 3], [2, 3], [4, 4], [5, 5] ] [ [1, 1], [2, 2], [3, 3], [4, 4], [5, 5] ] </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POOptimal bubble sorting algorithm for an array of arrays of numbers
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USbadawi
    1. USbadawi
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POOptimal bubble sorting algorithm for an array of arrays of numbers
      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. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COFor n=9, i got 53
      singulars
      1. PO
      1. USbadawi
    2. COThis is interesting, thanks! My lower bound for n=9 gives 51, so if you can actually get 53 that's pretty close and likely optimal. I'll have to think on this a bit, but thanks so much for this!
      singulars
      1. PO
      1. USPengOne
    3. COIn case of n = 7, the algorithm gives your lower bound 31, which is the optimal.
      singulars
      1. PO
      1. USbadawi
 

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