The complexity of sorting a list having one free cell
up vote
1
down vote
favorite
Making a standard bureocracy (using Word tables), I arrived to the following
Problem. Assume that we have a table with $n+1$ rows. The first $n$ rows are filled with names of students (and say topics of their Master works) and the last row is empty. It is required to sort this table in alphabetic order (of student names) using the operations of cut and copy-past over rows. What is the complexity of this problem (i.e., the smallest number of cut-copy-past operations in the worst case)?
I suspect that this problem has been considered (say in Computer Sciences) but I can not find a proper reference.
Remark. A simple argument shows that this worst case complexity is between $n$ and $frac32n$ (more precisely, $lfloorfrac32nrfloor+1$).
Can we always do better than $frac32n$?
algorithms computational-complexity permutations
asked Nov 10 at 17:26
Taras Banakh
15k13187
add a comment |
up vote
1
down vote
favorite
Making a standard bureocracy (using Word tables), I arrived to the following
Problem. Assume that we have a table with $n+1$ rows. The first $n$ rows are filled with names of students (and say topics of their Master works) and the last row is empty. It is required to sort this table in alphabetic order (of student names) using the operations of cut and copy-past over rows. What is the complexity of this problem (i.e., the smallest number of cut-copy-past operations in the worst case)?
I suspect that this problem has been considered (say in Computer Sciences) but I can not find a proper reference.
Remark. A simple argument shows that this worst case complexity is between $n$ and $frac32n$ (more precisely, $lfloorfrac32nrfloor+1$).
Can we always do better than $frac32n$?
algorithms computational-complexity permutations
asked Nov 10 at 17:26
Taras Banakh
15k13187
1
To clarify: A move consists of switching an occupied row with the empty row?
– Stefan Mesken
Nov 10 at 17:50
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Making a standard bureocracy (using Word tables), I arrived to the following
Problem. Assume that we have a table with $n+1$ rows. The first $n$ rows are filled with names of students (and say topics of their Master works) and the last row is empty. It is required to sort this table in alphabetic order (of student names) using the operations of cut and copy-past over rows. What is the complexity of this problem (i.e., the smallest number of cut-copy-past operations in the worst case)?
I suspect that this problem has been considered (say in Computer Sciences) but I can not find a proper reference.
Remark. A simple argument shows that this worst case complexity is between $n$ and $frac32n$ (more precisely, $lfloorfrac32nrfloor+1$).
Can we always do better than $frac32n$?
algorithms computational-complexity permutations
asked Nov 10 at 17:26
Taras Banakh
15k13187
Making a standard bureocracy (using Word tables), I arrived to the following
Problem. Assume that we have a table with $n+1$ rows. The first $n$ rows are filled with names of students (and say topics of their Master works) and the last row is empty. It is required to sort this table in alphabetic order (of student names) using the operations of cut and copy-past over rows. What is the complexity of this problem (i.e., the smallest number of cut-copy-past operations in the worst case)?
I suspect that this problem has been considered (say in Computer Sciences) but I can not find a proper reference.
Remark. A simple argument shows that this worst case complexity is between $n$ and $frac32n$ (more precisely, $lfloorfrac32nrfloor+1$).
Can we always do better than $frac32n$?
algorithms computational-complexity permutations
algorithms computational-complexity permutations
asked Nov 10 at 17:26
Taras Banakh
15k13187
asked Nov 10 at 17:26
Taras Banakh
15k13187
edited Nov 10 at 18:59
asked Nov 10 at 17:26
Taras Banakh
15k13187
asked Nov 10 at 17:26
Taras Banakh
15k13187
asked Nov 10 at 17:26
Taras Banakh
15k13187
15k13187
1
To clarify: A move consists of switching an occupied row with the empty row?
– Stefan Mesken
Nov 10 at 17:50
add a comment |
1
To clarify: A move consists of switching an occupied row with the empty row?
– Stefan Mesken
Nov 10 at 17:50
1
1
To clarify: A move consists of switching an occupied row with the empty row?
– Stefan Mesken
Nov 10 at 17:50
To clarify: A move consists of switching an occupied row with the empty row?
– Stefan Mesken
Nov 10 at 17:50
add a comment |
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
No, $frac32n$ is optimal. Consider the case in which the initial order has the elements swapped in pairs, $BADCFEHG...$. Take any possible sequence of moves that sorts them; we shall show that this sequence contains at least $frac32n$ moves.
Focus on the first two locations 1 and 2 (those that contain $BA$ initially). We associate to them three distinct operations among the ones in the sequence:
- the first operation that involves one of the first two elements (locations 1-2 in the list), which will swap one of the initial elements appearing in it with the empty space;
- the operation that writes $A$ in location 1 (for the last time, if there is more than one);
- the operation that writes $B$ in location 2 (for the last time, if there is more than one).
Note that these are three distinct operations, and they all involve cutting-and-pasting either the letter $A$ or the letter $B$.
Similarly, we can associate three distinct operations of the sequence to each pair of consecutive locations $(2i-1,2i)$: the first one that involves either location $2i-1$ or $2i$, the last one that involves location $2i-1$, and the last one that involves location $2i$. All of these involve cutting-and-pasting one of the two letters that go in those locations, hence there cannot be duplicates with the ones associated to a different pair.
We have built a list of $frac32n$ distinct operations among those in the sequence, so this proves that the sequence has length at least $frac32n$.
For completeness: the $frac32n$ optimal algorithm is: we have to apply a certain permutation of the letters; decompose this permutation into disjoint cycles; each $k$-cycle permutation can be applied in $k+1$ distinct operations using the empty location $X$; for instance $$BCDAXto BCDXA to BCXDA to BXCDA to XBCDA to ABCDX$$
I hope the general strategy is clear to see from this example: swap $X$ with the preceding letter $k$ times, then move back $A$ into place.
answered Nov 10 at 18:07
Federico Poloni
12.6k25481
Ok. But this is just one example of an argorithm that fulfils this task. Why is this algorithm optimal? How to prove that any argorithm sorting the list of n/2 pairs will require at least 3n/2 operations?
– Taras Banakh
Nov 10 at 18:26
@TarasBanakh The first half of my answer is an optimality proof. For any algorithm that accomplishes the task, we build a list of $frac32n$ distinct moves that appear in it.
– Federico Poloni
Nov 10 at 18:33
Yes you are right. So I accept your answer. Thank you.
– Taras Banakh
Nov 10 at 18:36
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
No, $frac32n$ is optimal. Consider the case in which the initial order has the elements swapped in pairs, $BADCFEHG...$. Take any possible sequence of moves that sorts them; we shall show that this sequence contains at least $frac32n$ moves.
Focus on the first two locations 1 and 2 (those that contain $BA$ initially). We associate to them three distinct operations among the ones in the sequence:
- the first operation that involves one of the first two elements (locations 1-2 in the list), which will swap one of the initial elements appearing in it with the empty space;
- the operation that writes $A$ in location 1 (for the last time, if there is more than one);
- the operation that writes $B$ in location 2 (for the last time, if there is more than one).
Note that these are three distinct operations, and they all involve cutting-and-pasting either the letter $A$ or the letter $B$.
Similarly, we can associate three distinct operations of the sequence to each pair of consecutive locations $(2i-1,2i)$: the first one that involves either location $2i-1$ or $2i$, the last one that involves location $2i-1$, and the last one that involves location $2i$. All of these involve cutting-and-pasting one of the two letters that go in those locations, hence there cannot be duplicates with the ones associated to a different pair.
We have built a list of $frac32n$ distinct operations among those in the sequence, so this proves that the sequence has length at least $frac32n$.
For completeness: the $frac32n$ optimal algorithm is: we have to apply a certain permutation of the letters; decompose this permutation into disjoint cycles; each $k$-cycle permutation can be applied in $k+1$ distinct operations using the empty location $X$; for instance $$BCDAXto BCDXA to BCXDA to BXCDA to XBCDA to ABCDX$$
I hope the general strategy is clear to see from this example: swap $X$ with the preceding letter $k$ times, then move back $A$ into place.
answered Nov 10 at 18:07
Federico Poloni
12.6k25481
Ok. But this is just one example of an argorithm that fulfils this task. Why is this algorithm optimal? How to prove that any argorithm sorting the list of n/2 pairs will require at least 3n/2 operations?
– Taras Banakh
Nov 10 at 18:26
@TarasBanakh The first half of my answer is an optimality proof. For any algorithm that accomplishes the task, we build a list of $frac32n$ distinct moves that appear in it.
– Federico Poloni
Nov 10 at 18:33
Yes you are right. So I accept your answer. Thank you.
– Taras Banakh
Nov 10 at 18:36
add a comment |
up vote
3
down vote
accepted
No, $frac32n$ is optimal. Consider the case in which the initial order has the elements swapped in pairs, $BADCFEHG...$. Take any possible sequence of moves that sorts them; we shall show that this sequence contains at least $frac32n$ moves.
Focus on the first two locations 1 and 2 (those that contain $BA$ initially). We associate to them three distinct operations among the ones in the sequence:
- the first operation that involves one of the first two elements (locations 1-2 in the list), which will swap one of the initial elements appearing in it with the empty space;
- the operation that writes $A$ in location 1 (for the last time, if there is more than one);
- the operation that writes $B$ in location 2 (for the last time, if there is more than one).
Note that these are three distinct operations, and they all involve cutting-and-pasting either the letter $A$ or the letter $B$.
Similarly, we can associate three distinct operations of the sequence to each pair of consecutive locations $(2i-1,2i)$: the first one that involves either location $2i-1$ or $2i$, the last one that involves location $2i-1$, and the last one that involves location $2i$. All of these involve cutting-and-pasting one of the two letters that go in those locations, hence there cannot be duplicates with the ones associated to a different pair.
We have built a list of $frac32n$ distinct operations among those in the sequence, so this proves that the sequence has length at least $frac32n$.
For completeness: the $frac32n$ optimal algorithm is: we have to apply a certain permutation of the letters; decompose this permutation into disjoint cycles; each $k$-cycle permutation can be applied in $k+1$ distinct operations using the empty location $X$; for instance $$BCDAXto BCDXA to BCXDA to BXCDA to XBCDA to ABCDX$$
I hope the general strategy is clear to see from this example: swap $X$ with the preceding letter $k$ times, then move back $A$ into place.
answered Nov 10 at 18:07
Federico Poloni
12.6k25481
Ok. But this is just one example of an argorithm that fulfils this task. Why is this algorithm optimal? How to prove that any argorithm sorting the list of n/2 pairs will require at least 3n/2 operations?
– Taras Banakh
Nov 10 at 18:26
@TarasBanakh The first half of my answer is an optimality proof. For any algorithm that accomplishes the task, we build a list of $frac32n$ distinct moves that appear in it.
– Federico Poloni
Nov 10 at 18:33
Yes you are right. So I accept your answer. Thank you.
– Taras Banakh
Nov 10 at 18:36
add a comment |
up vote
3
down vote
accepted
up vote
3
down vote
accepted
No, $frac32n$ is optimal. Consider the case in which the initial order has the elements swapped in pairs, $BADCFEHG...$. Take any possible sequence of moves that sorts them; we shall show that this sequence contains at least $frac32n$ moves.
Focus on the first two locations 1 and 2 (those that contain $BA$ initially). We associate to them three distinct operations among the ones in the sequence:
- the first operation that involves one of the first two elements (locations 1-2 in the list), which will swap one of the initial elements appearing in it with the empty space;
- the operation that writes $A$ in location 1 (for the last time, if there is more than one);
- the operation that writes $B$ in location 2 (for the last time, if there is more than one).
Note that these are three distinct operations, and they all involve cutting-and-pasting either the letter $A$ or the letter $B$.
Similarly, we can associate three distinct operations of the sequence to each pair of consecutive locations $(2i-1,2i)$: the first one that involves either location $2i-1$ or $2i$, the last one that involves location $2i-1$, and the last one that involves location $2i$. All of these involve cutting-and-pasting one of the two letters that go in those locations, hence there cannot be duplicates with the ones associated to a different pair.
We have built a list of $frac32n$ distinct operations among those in the sequence, so this proves that the sequence has length at least $frac32n$.
For completeness: the $frac32n$ optimal algorithm is: we have to apply a certain permutation of the letters; decompose this permutation into disjoint cycles; each $k$-cycle permutation can be applied in $k+1$ distinct operations using the empty location $X$; for instance $$BCDAXto BCDXA to BCXDA to BXCDA to XBCDA to ABCDX$$
I hope the general strategy is clear to see from this example: swap $X$ with the preceding letter $k$ times, then move back $A$ into place.
answered Nov 10 at 18:07
Federico Poloni
12.6k25481
No, $frac32n$ is optimal. Consider the case in which the initial order has the elements swapped in pairs, $BADCFEHG...$. Take any possible sequence of moves that sorts them; we shall show that this sequence contains at least $frac32n$ moves.
Focus on the first two locations 1 and 2 (those that contain $BA$ initially). We associate to them three distinct operations among the ones in the sequence:
- the first operation that involves one of the first two elements (locations 1-2 in the list), which will swap one of the initial elements appearing in it with the empty space;
- the operation that writes $A$ in location 1 (for the last time, if there is more than one);
- the operation that writes $B$ in location 2 (for the last time, if there is more than one).
Note that these are three distinct operations, and they all involve cutting-and-pasting either the letter $A$ or the letter $B$.
Similarly, we can associate three distinct operations of the sequence to each pair of consecutive locations $(2i-1,2i)$: the first one that involves either location $2i-1$ or $2i$, the last one that involves location $2i-1$, and the last one that involves location $2i$. All of these involve cutting-and-pasting one of the two letters that go in those locations, hence there cannot be duplicates with the ones associated to a different pair.
We have built a list of $frac32n$ distinct operations among those in the sequence, so this proves that the sequence has length at least $frac32n$.
For completeness: the $frac32n$ optimal algorithm is: we have to apply a certain permutation of the letters; decompose this permutation into disjoint cycles; each $k$-cycle permutation can be applied in $k+1$ distinct operations using the empty location $X$; for instance $$BCDAXto BCDXA to BCXDA to BXCDA to XBCDA to ABCDX$$
I hope the general strategy is clear to see from this example: swap $X$ with the preceding letter $k$ times, then move back $A$ into place.
answered Nov 10 at 18:07
Federico Poloni
12.6k25481
edited Nov 10 at 18:49
answered Nov 10 at 18:07
Federico Poloni
12.6k25481
answered Nov 10 at 18:07
Federico Poloni
12.6k25481
answered Nov 10 at 18:07
Federico Poloni
12.6k25481
12.6k25481
Ok. But this is just one example of an argorithm that fulfils this task. Why is this algorithm optimal? How to prove that any argorithm sorting the list of n/2 pairs will require at least 3n/2 operations?
– Taras Banakh
Nov 10 at 18:26
@TarasBanakh The first half of my answer is an optimality proof. For any algorithm that accomplishes the task, we build a list of $frac32n$ distinct moves that appear in it.
– Federico Poloni
Nov 10 at 18:33
Yes you are right. So I accept your answer. Thank you.
– Taras Banakh
Nov 10 at 18:36
add a comment |
Ok. But this is just one example of an argorithm that fulfils this task. Why is this algorithm optimal? How to prove that any argorithm sorting the list of n/2 pairs will require at least 3n/2 operations?
– Taras Banakh
Nov 10 at 18:26
@TarasBanakh The first half of my answer is an optimality proof. For any algorithm that accomplishes the task, we build a list of $frac32n$ distinct moves that appear in it.
– Federico Poloni
Nov 10 at 18:33
Yes you are right. So I accept your answer. Thank you.
– Taras Banakh
Nov 10 at 18:36
Ok. But this is just one example of an argorithm that fulfils this task. Why is this algorithm optimal? How to prove that any argorithm sorting the list of n/2 pairs will require at least 3n/2 operations?
– Taras Banakh
Nov 10 at 18:26
Ok. But this is just one example of an argorithm that fulfils this task. Why is this algorithm optimal? How to prove that any argorithm sorting the list of n/2 pairs will require at least 3n/2 operations?
– Taras Banakh
Nov 10 at 18:26
@TarasBanakh The first half of my answer is an optimality proof. For any algorithm that accomplishes the task, we build a list of $frac32n$ distinct moves that appear in it.
– Federico Poloni
Nov 10 at 18:33
@TarasBanakh The first half of my answer is an optimality proof. For any algorithm that accomplishes the task, we build a list of $frac32n$ distinct moves that appear in it.
– Federico Poloni
Nov 10 at 18:33
Yes you are right. So I accept your answer. Thank you.
– Taras Banakh
Nov 10 at 18:36
Yes you are right. So I accept your answer. Thank you.
– Taras Banakh
Nov 10 at 18:36
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f315027%2fthe-complexity-of-sorting-a-list-having-one-free-cell%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
To clarify: A move consists of switching an occupied row with the empty row?
– Stefan Mesken
Nov 10 at 17:50