
Apologies for the shouting but this is important.
When answering a question please:
 Read the question carefully
 Understand that English isn't everyone's first language so be lenient of bad spelling and grammar
 If a question is poorly phrased then either ask for clarification, ignore it, or mark it down. Insults are not welcome
 If the question is inappropriate then click the 'vote to remove message' button
Insults, slapdowns and sarcasm aren't welcome. Let's work to help developers, not make them feel stupid.
cheers,
Chris Maunder
The Code Project Cofounder
Microsoft C++ MVP





For those new to message boards please try to follow a few simple rules when posting your question. Choose the correct forum for your message. Posting a VB.NET question in the C++ forum will end in tears.
 Be specific! Don't ask "can someone send me the code to create an application that does 'X'. Pinpoint exactly what it is you need help with.
 Keep the subject line brief, but descriptive. eg "File Serialization problem"
 Keep the question as brief as possible. If you have to include code, include the smallest snippet of code you can.
 Be careful when including code that you haven't made a typo. Typing mistakes can become the focal point instead of the actual question you asked.
 Do not remove or empty a message if others have replied. Keep the thread intact and available for others to search and read. If your problem was answered then edit your message and add "[Solved]" to the subject line of the original post, and cast an approval vote to the one or several answers that really helped you.
 If you are posting source code with your question, place it inside <pre></pre> tags. We advise you also check the "Encode "<" (and other HTML) characters when pasting" checkbox before pasting anything inside the PRE block, and make sure "Use HTML in this post" check box is checked.
 Be courteous and DON'T SHOUT. Everyone here helps because they enjoy helping others, not because it's their job.
 Please do not post links to your question into an unrelated forum such as the lounge. It will be deleted. Likewise, do not post the same question in more than one forum.
 Do not be abusive, offensive, inappropriate or harass anyone on the boards. Doing so will get you kicked off and banned. Play nice.
 If you have a school or university assignment, assume that your teacher or lecturer is also reading these forums.
 No advertising or soliciting.
 We reserve the right to move your posts to a more appropriate forum or to delete anything deemed inappropriate or illegal.
cheers,
Chris Maunder
The Code Project Cofounder
Microsoft C++ MVP





Suppose your operations on arrays were constrained as follows:
 .get(i) accesses the element at index position ?? in readonly fashion.
 .length() returns the length of the array.
 .flip(i) flips the array up to index position ??. Thus, the {1,2,3,4}.flip(2) operation changes the array to {3,2,1,4}.
Only these three operations are available to you. Also assume that the three operations are in ??(1).
Develop an algorithm that sorts a given array in ??(?? × ?????? ??).
Suppose you have an array of length ?? + 1. You want to correctly sort the element at position ??. The array is already sorted up to ??  1. The correct position of the element at position ?? is index position ??. Find a sequence of flip operations that inserts the element in the correct location.
Problem: I have no idea how to begin
modified 14Dec20 13:06pm.





If you can figure out the last paragraph, you'll have a way to move an element into the correct position when it's out of place. That element might only be part way down the array, in which case you can move it up by only doing flips as far as that element, leaving the elements after it alone.
Start with an actual example, say 1235674. You want to move 4 up into the position currently occupied by 5. Clearly, 4 must be included in the first flip, else it'll never move. So flip(6) is the first operation, which yields 4765321. Now the ball is in your court.





They don't say to flip one way or another. Looks more like a rotate. Poor spec.
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food







Could help me solve this problem pls?
The job is to calculate the degree of discontent of passengers on a bus.
Passengers get on the bus, all at the same point and say at which point they want to stop (that point is the mileage from the point where they get on the bus to where they want to disembark), but the bus can only make k stops, that is, it is a value limited number of stops. The discontent will be calculated as follows (xy) * 2 where x is the place that each passenger chose to stay and y where the bus stopped. The K will be defined after calculating the discontent of each passenger





1. Nobody here is going to do your homework for you.
2. That's a maths problem, not a programming problem.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
 Homer






Hi,
I am building a small web app that allow stamp collectors to swap their stamps. The main problem I am trying to solve is 1on1 (direct) swap. Since usually A needs something from B, but B not always need something from A.
But the solution is to find a circular swap, for example:
A needs from B
B needs from C
C needs from A
result: everyone is happy.
I have a list of collectors, and for each a list of stamps they got, and a list of stamp they are looking for.
I am trying to find a way, to create a circle, by matching the "have" and "want". The problem is that this may take a very long time with lots of collectors and lots of stamps .
What would be the best approach for this?
The straight forward algorithm I think (which is obviously not optimized) is to:
1) look what "B" want.
2) find who got what B want (stamp after stamp)
3) for each one, see if he (C) needs something from A
4) if yes, YAY
5) if not, see what C want (stamp after stamp)
6) for each one, see if (D) has something from A
... and so on ...
long procedure...
Any suggestions will be very welcome. Thank you





Just advertise stamps (for sale) and what the seller wants. Period.
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food





In mathematical terms your problem can be stated as finding the cycles of a directed graph. Collectors A, B, C... are nodes in graph and what they want are graph arcs.
Now, if you Google for "finding graph cycles" one of the first results should be [^]
You might have already found a solution but anyways...
Mircea





Thanks!
Yes, you right, I already find this path of solution and working on it.
Thank you for taking the time to answer





This is my first question in this forum, so suggestions for improvement are welcome.
I have a data set of arrays which contain Floats between 1 and 1 and a new array of the same format.
The arrays have a length of up to 300.
I have to find the array from the data set that has the smallest distance to the new array.
IMPORTANT: The values of the arrays must remain on their position, while it's alowed to sort the arrays in the data set.
How can I achieve this while keeping an acceptable tradeoff between accuracy and scalability?
Of course I could just go through every array but that wouldn't be scalable I guess.
PS: Usually adjacent values have a similar value (so [0.8, 0.3, 0.7, 0.9] would be very unlikely).





CLOSED
modified 16Nov20 11:38am.





By identical, I assume you mean isomorphic. See here[^], which speculates that the problem may be NPintermediate (between P and NPcomplete).
Let's call the two graphs G1 and G2. On the surface, the problem seems NPcomplete because you have to compare G1 and G2 after renaming the n vertices in G2 using names from G1, so there are n! combinations to try. However, some combinations can be filtered out quickly. For example, a vertex in G2 has to have the same degree (number of edges) as the one it is being compared to in G1. But if this check passes, there's still more checking to do, as in the case of the graph with 6 vertices shown in your link.





Message Closed
modified 20Nov20 2:05am.





This "same name" talk is confusing. The general problem is that the two graphs have different names for their vertices, so you have to try all possible ways of mapping one graph onto the other. So even if there's there's a vertex A in G1 and a vertex A in G2, that doesn't mean that you don't have to compare A in G1 with B in G2, and so on. You'd only need to compare A to A if you're deliberately being told to test a specific mapping, ignoring all others, or when you're solving the general problem and evaluating each possible mapping in succession.
The neighbours must be the same, not just the degrees. Your example, where all the vertices have the same degree, shows why the problem is difficult. If it's an undirected graph and all the degrees are n1, then it's easy because both must be complete graphs. If not, then let's say we had a graph with 6 vertices, all of degree 2. How can you tell whether these are two disjoint graphs (two C3's) or a connected bipartite graph? You have to go beyond the vertices' degrees to do that.
On the surface, it looks NPcomplete because there are n! possible mappings, and n! is approximated by an exponential function.





CLOSED
modified 16Nov20 11:39am.





Your first paragraph is correct. So is your second paragraph, but of course all combinations have to be tried before concluding that the graphs are not isomorphic.
Your example shows why the problem is difficult. You have to try all combinations, though optimizations certainly exist. Trivially, the number of vertices in both graphs has to be the same. And if you sort their vertices' degrees, the two sequences have to be the same. But like the 6vertex graph demonstrated, that isn't enough. There are undoubtedly more optimizations, which is why the article that I linked to speculated that the problem is NPincomplete (easier than NPcomplete). But you'd have to search the net to find the details of those algorithms.





CLOSED
modified 16Nov20 11:39am.





It appears that I'm more or less answering a homework question, which isn't a good idea for you.
Yes, you have to satisfy the neighbour condition (which will automatically satisfy the degree condition). n is the number of vertices in G2, but G1 must also have n vertices, otherwise the graphs couldn't possibly be isomorphic. There are n! possibilities because you need to try all possible permutations when mapping G2's vertices to G1's. Maybe you get lucky and discover that they're isomorphic when you check the first permutation, or maybe you get unlucky and have to try them all.





Message Closed
modified 20Nov20 2:05am.





When you are new to this site, any of your posts might be marked as possible spam, in which case it has to be reviewed by one of the admins. It probably happened because your post contained links, and some new members post links that are spam.
This has gone beyond my expertise level. It’s been about 40 years since I last did theoretical computer science. Is the isomorphism problem NPcomplete or not? Well, I would trust your second link more, since it’s actually on a theoretical CS site, which carries more weight with me than GeeksForGeeks.
However, it appears that they're talking about two different things. One form of the isomorphism problem allows the graphs to have a different number of vertices. In that case, the goal is to determine whether the larger graph has a subgraph that is an isomorph of the smaller one. This definitely seems NPcomplete because you first have to pick one of the C(v1,v2) possible subgraphs before you can even check if it is isomorphic, where v1 and v2 are the number of vertices in G1 and G2 respectively. That’s what the GeeksForGeeks post is talking about, whereas the other one seems to be talking about the simpler version of the problem, where G1 and G2 have the same number of vertices.
So it looks like they're both right.




