- Forum
- General C++ Programming
- Algorithm required
Algorithm required
Your school has ordered some equipment that has been delivered in a number of very heavy
cartons. Each carton has a serial number and the cartons are all lined up in a row. Unfortunately, your teacher asked for the cartons to be placed in a particular sequence and you
forgot to tell the people who unloaded the cartons about this. You now have to quickly
restore the cartons to the correct order before the teacher comes and sees how you have
messed up her instructions.
Since the cartons are very heavy, you cannot carry them over long distances. In each
step, all you can do is to exchange the position of two adjacent cartons.
For instance, suppose the serial numbers on the cartons in the order in which they are
unloaded are 34, 29, 12, 78 and 90 and the order in which the cartons were supposed to be
arranged is 90, 29, 78, 34, 12. These cartons can be rearranged in the desired order with 7
exchanges, as follows:
• Exchange 78, 90 — 34, 29, 12, 90, 78
• Exchange 12, 90 — 34, 29, 90, 12, 78
• Exchange 34, 29 — 29, 34, 12, 90, 78
• Exchange 12, 78 — 29, 34, 90, 78, 12
• Exchange 34, 90 — 29, 90, 34, 78, 12
• Exchange 29, 90 — 90, 29, 34, 78, 12
• Exchange 34, 78 — 90, 29, 78, 34, 12
In this example, it can be shown that 7 exchanges are needed to reorder the cartons as
desired.
Clearly, you want to get the job done with minimum effort. Given the initial arrangement
of the cartons and the final sequence that the teacher wants, your goal is to compute the
minimum number of exchanges required to rearrange the cartons in the desired order
Please give me a general algorithm or Simple codes in turbo C++
cartons. Each carton has a serial number and the cartons are all lined up in a row. Unfortunately, your teacher asked for the cartons to be placed in a particular sequence and you
forgot to tell the people who unloaded the cartons about this. You now have to quickly
restore the cartons to the correct order before the teacher comes and sees how you have
messed up her instructions.
Since the cartons are very heavy, you cannot carry them over long distances. In each
step, all you can do is to exchange the position of two adjacent cartons.
For instance, suppose the serial numbers on the cartons in the order in which they are
unloaded are 34, 29, 12, 78 and 90 and the order in which the cartons were supposed to be
arranged is 90, 29, 78, 34, 12. These cartons can be rearranged in the desired order with 7
exchanges, as follows:
• Exchange 78, 90 — 34, 29, 12, 90, 78
• Exchange 12, 90 — 34, 29, 90, 12, 78
• Exchange 34, 29 — 29, 34, 12, 90, 78
• Exchange 12, 78 — 29, 34, 90, 78, 12
• Exchange 34, 90 — 29, 90, 34, 78, 12
• Exchange 29, 90 — 90, 29, 34, 78, 12
• Exchange 34, 78 — 90, 29, 78, 34, 12
In this example, it can be shown that 7 exchanges are needed to reorder the cartons as
desired.
Clearly, you want to get the job done with minimum effort. Given the initial arrangement
of the cartons and the final sequence that the teacher wants, your goal is to compute the
minimum number of exchanges required to rearrange the cartons in the desired order
Please give me a general algorithm or Simple codes in turbo C++
If we do this for you, what will you learn from it? The point of assignments like these are to get better at programming by solving problems, and you're not getting that by making others do them for you. If you're stuck on specific part, post your code and ask a specific question. Hint: To make the algorithm easier to understand and implement, make a step-by-step list of all the actions that needs to be done.
Imagine a graph where every vertex represents an ordering of boxes. Two vertices have an edge between them if you can turn one into the other by swapping two adjacent boxes. Your task is to find the shortest path between the starting and ending vertex.
@kev82 Could you please explain?? What sort of graph are you suggesting ,if you have each permutation represent a vertex how would you decide where the vertex would be on the graph?
@Stupebrett: I don't really know where to start . I mean i am not really sure how to develop a general algorithm in such problems, like in the example suppose i want to put 90 in its place first, How exactly do you know you have to exchange 29 and 34 first to make the steps less ??
@Stupebrett: I don't really know where to start . I mean i am not really sure how to develop a general algorithm in such problems, like in the example suppose i want to put 90 in its place first, How exactly do you know you have to exchange 29 and 34 first to make the steps less ??
Here is the graph for the permutations of 3 elements. X is the edge that means swapping the 1st and 2nd element, Y is the edge that means swapping the second and third.
http://postimage.org/image/vlyfgwq9r/
You will need to somehow represent this graph for your number of elements (or the necessary parts of it) in the computer's memory. You can then use one of the many well known and documented shortest path algorithms to find the solution.
http://postimage.org/image/vlyfgwq9r/
You will need to somehow represent this graph for your number of elements (or the necessary parts of it) in the computer's memory. You can then use one of the many well known and documented shortest path algorithms to find the solution.
Last edited on
Ok so you want to generate all permutations first and then link those which can be obtained by a single interchange and then find shortest distance between them... Sounds awesome... Thanks a lot i will try that...
Topic archived. No new replies allowed.