Optimal algorithm to reorder two arrays putting the common elements first
up vote
1
down vote
favorite
Let's say we have two arrays having some elements in common (the arrays can't contain duplicates)
Array 1 = [A, K, C, F]
Array 2 = [B, D, C, K]
I would like to reorder the two arrays with the following requirements:
- The common elements must be at the beginning of the arrays (without any specific order)
- The common elements in the two arrays must be exactly at the same positions
- The non-common elements can be in any position (after the common ones)
- Swapping two elements which are farther away costs more than swapping two elements which are closed together (we can assume a linear cost function where
cost of swapping elements at indexes i and j = abs(i - j))
For the example above having [C, K] in common, we could produce the following valid rearrangement:
Array 1 = [C, K, A, F]
Array 2 = [C, K, B, D]
Another valid rearrangement could be:
Array 1 = [K, C, A, F]
Array 2 = [K, C, B, D]
Although it is quite trivial to write a basic algorithm that swaps the two input arrays to generate a valid output, it is not clear to me how to write the "optimal" (in sense of minimal costs) one.
I am not even sure if this algorithm could be solved using dynamic programming or similar techniques. Has anyone already seen this problem somewhere before or has an idea on how to solve it?
EDITED: I have just noticed that this question is ill-posed and does not represent the problem I was originally trying to solve. Anyway, a possible solution to the problem as stated here is as following:
- create two new arrays
Array1*andArray2*where the non common elements are removed. - reorder the two arrays just containing common elements as described here
- The global solution is obtained as following:
- Swap all the common elements to the front of the two lists
- Apply the swaps obtained in step 2
I will try to come up with another question describing more accurately the problem I was originally trying to solve.
arrays algorithm optimization dynamic-programming
asked Nov 7 at 22:56
Ciaccia
142112
add a comment |
up vote
1
down vote
favorite
Let's say we have two arrays having some elements in common (the arrays can't contain duplicates)
Array 1 = [A, K, C, F]
Array 2 = [B, D, C, K]
I would like to reorder the two arrays with the following requirements:
- The common elements must be at the beginning of the arrays (without any specific order)
- The common elements in the two arrays must be exactly at the same positions
- The non-common elements can be in any position (after the common ones)
- Swapping two elements which are farther away costs more than swapping two elements which are closed together (we can assume a linear cost function where
cost of swapping elements at indexes i and j = abs(i - j))
For the example above having [C, K] in common, we could produce the following valid rearrangement:
Array 1 = [C, K, A, F]
Array 2 = [C, K, B, D]
Another valid rearrangement could be:
Array 1 = [K, C, A, F]
Array 2 = [K, C, B, D]
Although it is quite trivial to write a basic algorithm that swaps the two input arrays to generate a valid output, it is not clear to me how to write the "optimal" (in sense of minimal costs) one.
I am not even sure if this algorithm could be solved using dynamic programming or similar techniques. Has anyone already seen this problem somewhere before or has an idea on how to solve it?
EDITED: I have just noticed that this question is ill-posed and does not represent the problem I was originally trying to solve. Anyway, a possible solution to the problem as stated here is as following:
- create two new arrays
Array1*andArray2*where the non common elements are removed. - reorder the two arrays just containing common elements as described here
- The global solution is obtained as following:
- Swap all the common elements to the front of the two lists
- Apply the swaps obtained in step 2
I will try to come up with another question describing more accurately the problem I was originally trying to solve.
arrays algorithm optimization dynamic-programming
asked Nov 7 at 22:56
Ciaccia
142112
1
Given a linear cost function, I think the only requirement for a minimal solution is that you avoid moving common elements to the right. Which means that the example in the question is not very good, because there's no temptation to even think about moving a C or K to the right. A better example is[K,A,C,F]and[C,B,D,K]. What you learn from that example is that a common letter that must be moved to the right, should be moved by swapping it with another common letter.
– user3386109
Nov 8 at 0:14
But even[K,A,C,F]and[C,B,D,K]doesn't seem like a very good example, because the order of the common letters doesn't matter. In other words, The solution[C,K,?,?]has the same cost as the solution[K,C,?,?]. So your first challenge is to find an example where the order matters, or to mathematically prove that the order never matters.
– user3386109
Nov 8 at 0:15
Hi @user3386109, by reading your comment I realized that probably there is an equivalent (easier) formulation of the problem. Assuming that the cost of swapping two elements is linear in their distance, we could restate it as following: what is the minimum number of swaps needed to align the two arrays where only adjacent swaps are possible (for example to swap i and i+3 we would need 5 adjacent swaps {i, i+1}, {i+1, i+2}, {i+2,i+3}, {i+1, i+2}, {i, i+1}). More generically, to swap i and i+n elements we need 2*n-1 adjacent swaps.
– Ciaccia
Nov 8 at 9:35
Swapping one at a time to the left is fine. So {i+3, i+2}, {i+2, i+1}, {i+1, i}.
– user3386109
Nov 8 at 17:10
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Let's say we have two arrays having some elements in common (the arrays can't contain duplicates)
Array 1 = [A, K, C, F]
Array 2 = [B, D, C, K]
I would like to reorder the two arrays with the following requirements:
- The common elements must be at the beginning of the arrays (without any specific order)
- The common elements in the two arrays must be exactly at the same positions
- The non-common elements can be in any position (after the common ones)
- Swapping two elements which are farther away costs more than swapping two elements which are closed together (we can assume a linear cost function where
cost of swapping elements at indexes i and j = abs(i - j))
For the example above having [C, K] in common, we could produce the following valid rearrangement:
Array 1 = [C, K, A, F]
Array 2 = [C, K, B, D]
Another valid rearrangement could be:
Array 1 = [K, C, A, F]
Array 2 = [K, C, B, D]
Although it is quite trivial to write a basic algorithm that swaps the two input arrays to generate a valid output, it is not clear to me how to write the "optimal" (in sense of minimal costs) one.
I am not even sure if this algorithm could be solved using dynamic programming or similar techniques. Has anyone already seen this problem somewhere before or has an idea on how to solve it?
EDITED: I have just noticed that this question is ill-posed and does not represent the problem I was originally trying to solve. Anyway, a possible solution to the problem as stated here is as following:
- create two new arrays
Array1*andArray2*where the non common elements are removed. - reorder the two arrays just containing common elements as described here
- The global solution is obtained as following:
- Swap all the common elements to the front of the two lists
- Apply the swaps obtained in step 2
I will try to come up with another question describing more accurately the problem I was originally trying to solve.
arrays algorithm optimization dynamic-programming
asked Nov 7 at 22:56
Ciaccia
142112
Let's say we have two arrays having some elements in common (the arrays can't contain duplicates)
Array 1 = [A, K, C, F]
Array 2 = [B, D, C, K]
I would like to reorder the two arrays with the following requirements:
- The common elements must be at the beginning of the arrays (without any specific order)
- The common elements in the two arrays must be exactly at the same positions
- The non-common elements can be in any position (after the common ones)
- Swapping two elements which are farther away costs more than swapping two elements which are closed together (we can assume a linear cost function where
cost of swapping elements at indexes i and j = abs(i - j))
For the example above having [C, K] in common, we could produce the following valid rearrangement:
Array 1 = [C, K, A, F]
Array 2 = [C, K, B, D]
Another valid rearrangement could be:
Array 1 = [K, C, A, F]
Array 2 = [K, C, B, D]
Although it is quite trivial to write a basic algorithm that swaps the two input arrays to generate a valid output, it is not clear to me how to write the "optimal" (in sense of minimal costs) one.
I am not even sure if this algorithm could be solved using dynamic programming or similar techniques. Has anyone already seen this problem somewhere before or has an idea on how to solve it?
EDITED: I have just noticed that this question is ill-posed and does not represent the problem I was originally trying to solve. Anyway, a possible solution to the problem as stated here is as following:
- create two new arrays
Array1*andArray2*where the non common elements are removed. - reorder the two arrays just containing common elements as described here
- The global solution is obtained as following:
- Swap all the common elements to the front of the two lists
- Apply the swaps obtained in step 2
I will try to come up with another question describing more accurately the problem I was originally trying to solve.
arrays algorithm optimization dynamic-programming
arrays algorithm optimization dynamic-programming
asked Nov 7 at 22:56
Ciaccia
142112
asked Nov 7 at 22:56
Ciaccia
142112
edited 21 hours ago
asked Nov 7 at 22:56
Ciaccia
142112
asked Nov 7 at 22:56
Ciaccia
142112
asked Nov 7 at 22:56
Ciaccia
142112
142112
1
Given a linear cost function, I think the only requirement for a minimal solution is that you avoid moving common elements to the right. Which means that the example in the question is not very good, because there's no temptation to even think about moving a C or K to the right. A better example is[K,A,C,F]and[C,B,D,K]. What you learn from that example is that a common letter that must be moved to the right, should be moved by swapping it with another common letter.
– user3386109
Nov 8 at 0:14
But even[K,A,C,F]and[C,B,D,K]doesn't seem like a very good example, because the order of the common letters doesn't matter. In other words, The solution[C,K,?,?]has the same cost as the solution[K,C,?,?]. So your first challenge is to find an example where the order matters, or to mathematically prove that the order never matters.
– user3386109
Nov 8 at 0:15
Hi @user3386109, by reading your comment I realized that probably there is an equivalent (easier) formulation of the problem. Assuming that the cost of swapping two elements is linear in their distance, we could restate it as following: what is the minimum number of swaps needed to align the two arrays where only adjacent swaps are possible (for example to swap i and i+3 we would need 5 adjacent swaps {i, i+1}, {i+1, i+2}, {i+2,i+3}, {i+1, i+2}, {i, i+1}). More generically, to swap i and i+n elements we need 2*n-1 adjacent swaps.
– Ciaccia
Nov 8 at 9:35
Swapping one at a time to the left is fine. So {i+3, i+2}, {i+2, i+1}, {i+1, i}.
– user3386109
Nov 8 at 17:10
add a comment |
1
Given a linear cost function, I think the only requirement for a minimal solution is that you avoid moving common elements to the right. Which means that the example in the question is not very good, because there's no temptation to even think about moving a C or K to the right. A better example is[K,A,C,F]and[C,B,D,K]. What you learn from that example is that a common letter that must be moved to the right, should be moved by swapping it with another common letter.
– user3386109
Nov 8 at 0:14
But even[K,A,C,F]and[C,B,D,K]doesn't seem like a very good example, because the order of the common letters doesn't matter. In other words, The solution[C,K,?,?]has the same cost as the solution[K,C,?,?]. So your first challenge is to find an example where the order matters, or to mathematically prove that the order never matters.
– user3386109
Nov 8 at 0:15
Hi @user3386109, by reading your comment I realized that probably there is an equivalent (easier) formulation of the problem. Assuming that the cost of swapping two elements is linear in their distance, we could restate it as following: what is the minimum number of swaps needed to align the two arrays where only adjacent swaps are possible (for example to swap i and i+3 we would need 5 adjacent swaps {i, i+1}, {i+1, i+2}, {i+2,i+3}, {i+1, i+2}, {i, i+1}). More generically, to swap i and i+n elements we need 2*n-1 adjacent swaps.
– Ciaccia
Nov 8 at 9:35
Swapping one at a time to the left is fine. So {i+3, i+2}, {i+2, i+1}, {i+1, i}.
– user3386109
Nov 8 at 17:10
1
1
Given a linear cost function, I think the only requirement for a minimal solution is that you avoid moving common elements to the right. Which means that the example in the question is not very good, because there's no temptation to even think about moving a C or K to the right. A better example is
[K,A,C,F] and [C,B,D,K]. What you learn from that example is that a common letter that must be moved to the right, should be moved by swapping it with another common letter.– user3386109
Nov 8 at 0:14
Given a linear cost function, I think the only requirement for a minimal solution is that you avoid moving common elements to the right. Which means that the example in the question is not very good, because there's no temptation to even think about moving a C or K to the right. A better example is
[K,A,C,F] and [C,B,D,K]. What you learn from that example is that a common letter that must be moved to the right, should be moved by swapping it with another common letter.– user3386109
Nov 8 at 0:14
But even
[K,A,C,F] and [C,B,D,K] doesn't seem like a very good example, because the order of the common letters doesn't matter. In other words, The solution [C,K,?,?] has the same cost as the solution [K,C,?,?]. So your first challenge is to find an example where the order matters, or to mathematically prove that the order never matters.– user3386109
Nov 8 at 0:15
But even
[K,A,C,F] and [C,B,D,K] doesn't seem like a very good example, because the order of the common letters doesn't matter. In other words, The solution [C,K,?,?] has the same cost as the solution [K,C,?,?]. So your first challenge is to find an example where the order matters, or to mathematically prove that the order never matters.– user3386109
Nov 8 at 0:15
Hi @user3386109, by reading your comment I realized that probably there is an equivalent (easier) formulation of the problem. Assuming that the cost of swapping two elements is linear in their distance, we could restate it as following: what is the minimum number of swaps needed to align the two arrays where only adjacent swaps are possible (for example to swap i and i+3 we would need 5 adjacent swaps {i, i+1}, {i+1, i+2}, {i+2,i+3}, {i+1, i+2}, {i, i+1}). More generically, to swap i and i+n elements we need 2*n-1 adjacent swaps.
– Ciaccia
Nov 8 at 9:35
Hi @user3386109, by reading your comment I realized that probably there is an equivalent (easier) formulation of the problem. Assuming that the cost of swapping two elements is linear in their distance, we could restate it as following: what is the minimum number of swaps needed to align the two arrays where only adjacent swaps are possible (for example to swap i and i+3 we would need 5 adjacent swaps {i, i+1}, {i+1, i+2}, {i+2,i+3}, {i+1, i+2}, {i, i+1}). More generically, to swap i and i+n elements we need 2*n-1 adjacent swaps.
– Ciaccia
Nov 8 at 9:35
Swapping one at a time to the left is fine. So {i+3, i+2}, {i+2, i+1}, {i+1, i}.
– user3386109
Nov 8 at 17:10
Swapping one at a time to the left is fine. So {i+3, i+2}, {i+2, i+1}, {i+1, i}.
– user3386109
Nov 8 at 17:10
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
I will describe my ideas, sorry for my english:
First, find out which are the common elements.
Second, go through both list, at the same time, from the left to the right. There might be three cases:
a) there are no common elements in the position. You go to the next position.
b) there is one common element in the position. Then you swap the common element and its complement to the most left position not occupied by common elements.
c) there are two common elements in the position. Then you swap the one to the most left position not occupied by common elements or the next position to the right and add the complements.
If this position is also occupied by one or two common elements, you keep these in a store and try to empty this store while moving on. Realize that this store can grow larger than one or two elements.
By this you should be able to extract where to move which element, with an optimal solution with respect to your requirements.
remark: This seems quite logic to me now but it would be nice to know how it worked ;)
To realize why this should yield an optimal answer, u got to realize that for an optimal solution you have to only move objects from the rigth to the left. So the mayor incentive is to avoid moving any object from the left to the right. The steps I described avoid this, as much as possible.
answered Nov 7 at 23:29
Jan Weimer
43
Hi @JanWeimer, thanks a lot for your answer. Could you please explain to me again the step c) in your algorithm (I don't get it) and why it should return an optimal solution?
– Ciaccia
Nov 8 at 9:21
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
I will describe my ideas, sorry for my english:
First, find out which are the common elements.
Second, go through both list, at the same time, from the left to the right. There might be three cases:
a) there are no common elements in the position. You go to the next position.
b) there is one common element in the position. Then you swap the common element and its complement to the most left position not occupied by common elements.
c) there are two common elements in the position. Then you swap the one to the most left position not occupied by common elements or the next position to the right and add the complements.
If this position is also occupied by one or two common elements, you keep these in a store and try to empty this store while moving on. Realize that this store can grow larger than one or two elements.
By this you should be able to extract where to move which element, with an optimal solution with respect to your requirements.
remark: This seems quite logic to me now but it would be nice to know how it worked ;)
To realize why this should yield an optimal answer, u got to realize that for an optimal solution you have to only move objects from the rigth to the left. So the mayor incentive is to avoid moving any object from the left to the right. The steps I described avoid this, as much as possible.
answered Nov 7 at 23:29
Jan Weimer
43
Hi @JanWeimer, thanks a lot for your answer. Could you please explain to me again the step c) in your algorithm (I don't get it) and why it should return an optimal solution?
– Ciaccia
Nov 8 at 9:21
add a comment |
up vote
0
down vote
I will describe my ideas, sorry for my english:
First, find out which are the common elements.
Second, go through both list, at the same time, from the left to the right. There might be three cases:
a) there are no common elements in the position. You go to the next position.
b) there is one common element in the position. Then you swap the common element and its complement to the most left position not occupied by common elements.
c) there are two common elements in the position. Then you swap the one to the most left position not occupied by common elements or the next position to the right and add the complements.
If this position is also occupied by one or two common elements, you keep these in a store and try to empty this store while moving on. Realize that this store can grow larger than one or two elements.
By this you should be able to extract where to move which element, with an optimal solution with respect to your requirements.
remark: This seems quite logic to me now but it would be nice to know how it worked ;)
To realize why this should yield an optimal answer, u got to realize that for an optimal solution you have to only move objects from the rigth to the left. So the mayor incentive is to avoid moving any object from the left to the right. The steps I described avoid this, as much as possible.
answered Nov 7 at 23:29
Jan Weimer
43
Hi @JanWeimer, thanks a lot for your answer. Could you please explain to me again the step c) in your algorithm (I don't get it) and why it should return an optimal solution?
– Ciaccia
Nov 8 at 9:21
add a comment |
up vote
0
down vote
up vote
0
down vote
I will describe my ideas, sorry for my english:
First, find out which are the common elements.
Second, go through both list, at the same time, from the left to the right. There might be three cases:
a) there are no common elements in the position. You go to the next position.
b) there is one common element in the position. Then you swap the common element and its complement to the most left position not occupied by common elements.
c) there are two common elements in the position. Then you swap the one to the most left position not occupied by common elements or the next position to the right and add the complements.
If this position is also occupied by one or two common elements, you keep these in a store and try to empty this store while moving on. Realize that this store can grow larger than one or two elements.
By this you should be able to extract where to move which element, with an optimal solution with respect to your requirements.
remark: This seems quite logic to me now but it would be nice to know how it worked ;)
To realize why this should yield an optimal answer, u got to realize that for an optimal solution you have to only move objects from the rigth to the left. So the mayor incentive is to avoid moving any object from the left to the right. The steps I described avoid this, as much as possible.
answered Nov 7 at 23:29
Jan Weimer
43
I will describe my ideas, sorry for my english:
First, find out which are the common elements.
Second, go through both list, at the same time, from the left to the right. There might be three cases:
a) there are no common elements in the position. You go to the next position.
b) there is one common element in the position. Then you swap the common element and its complement to the most left position not occupied by common elements.
c) there are two common elements in the position. Then you swap the one to the most left position not occupied by common elements or the next position to the right and add the complements.
If this position is also occupied by one or two common elements, you keep these in a store and try to empty this store while moving on. Realize that this store can grow larger than one or two elements.
By this you should be able to extract where to move which element, with an optimal solution with respect to your requirements.
remark: This seems quite logic to me now but it would be nice to know how it worked ;)
To realize why this should yield an optimal answer, u got to realize that for an optimal solution you have to only move objects from the rigth to the left. So the mayor incentive is to avoid moving any object from the left to the right. The steps I described avoid this, as much as possible.
answered Nov 7 at 23:29
Jan Weimer
43
edited Nov 9 at 9:41
answered Nov 7 at 23:29
Jan Weimer
43
answered Nov 7 at 23:29
Jan Weimer
43
answered Nov 7 at 23:29
Jan Weimer
43
43
Hi @JanWeimer, thanks a lot for your answer. Could you please explain to me again the step c) in your algorithm (I don't get it) and why it should return an optimal solution?
– Ciaccia
Nov 8 at 9:21
add a comment |
Hi @JanWeimer, thanks a lot for your answer. Could you please explain to me again the step c) in your algorithm (I don't get it) and why it should return an optimal solution?
– Ciaccia
Nov 8 at 9:21
Hi @JanWeimer, thanks a lot for your answer. Could you please explain to me again the step c) in your algorithm (I don't get it) and why it should return an optimal solution?
– Ciaccia
Nov 8 at 9:21
Hi @JanWeimer, thanks a lot for your answer. Could you please explain to me again the step c) in your algorithm (I don't get it) and why it should return an optimal solution?
– Ciaccia
Nov 8 at 9:21
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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%2fstackoverflow.com%2fquestions%2f53199164%2foptimal-algorithm-to-reorder-two-arrays-putting-the-common-elements-first%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
Given a linear cost function, I think the only requirement for a minimal solution is that you avoid moving common elements to the right. Which means that the example in the question is not very good, because there's no temptation to even think about moving a C or K to the right. A better example is
[K,A,C,F]and[C,B,D,K]. What you learn from that example is that a common letter that must be moved to the right, should be moved by swapping it with another common letter.– user3386109
Nov 8 at 0:14
But even
[K,A,C,F]and[C,B,D,K]doesn't seem like a very good example, because the order of the common letters doesn't matter. In other words, The solution[C,K,?,?]has the same cost as the solution[K,C,?,?]. So your first challenge is to find an example where the order matters, or to mathematically prove that the order never matters.– user3386109
Nov 8 at 0:15
Hi @user3386109, by reading your comment I realized that probably there is an equivalent (easier) formulation of the problem. Assuming that the cost of swapping two elements is linear in their distance, we could restate it as following: what is the minimum number of swaps needed to align the two arrays where only adjacent swaps are possible (for example to swap i and i+3 we would need 5 adjacent swaps {i, i+1}, {i+1, i+2}, {i+2,i+3}, {i+1, i+2}, {i, i+1}). More generically, to swap i and i+n elements we need 2*n-1 adjacent swaps.
– Ciaccia
Nov 8 at 9:35
Swapping one at a time to the left is fine. So {i+3, i+2}, {i+2, i+1}, {i+1, i}.
– user3386109
Nov 8 at 17:10