StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
18294951
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
6
CommunityOwnedDate
CreationDate
2013-08-18T01:49:01.567
FavoriteCount
0
LastActivityDate
2014-05-16T05:50:25.277
LastEditDate
2017-05-23T12:08:30.093
LastEditorUserId
-1
OwnerUserId
2376331
ParentId
18292202
PostTypeId
2
Score
3
ViewCount
0
LastEditorDisplayName
text
Body
You can construct the "difference" strings <code>S</code> and <code>S'</code>, i.e. a string which contains the characters at the differing positions of the two strings, e.g. for <code>acbacb</code> and <code>abcabc</code> it will be <code>cbcb</code> and <code>bcbc</code>. Let us say this contains n characters. You can now construct a "permutation graph" G which will have <code>n</code> nodes and an edge from <code>i</code> to <code>j</code> if <code>S[i] == S'[j]</code>. In the case of all unique characters, it is easy to see that the required number of swaps will be (n - number of cycles in G), which can be found out in O(n) time. However, in the case where there are any number of duplicate characters, this reduces to the problem of finding out the largest number of cycles in a directed graph, which, I think, is NP-hard, (e.g. check out: <a href="http://www.math.ucsd.edu/~jverstra/dcig.pdf" rel="nofollow noreferrer">http://www.math.ucsd.edu/~jverstra/dcig.pdf</a> ). In that paper a few greedy algorithms are pointed out, one of which is particularly simple: <ol> <li>At each step, find the minimum length cycle in the graph (e.g. <a href="https://stackoverflow.com/questions/3911626/find-cycle-of-shortest-length-in-a-directed-graph-with-positive-weights">Find cycle of shortest length in a directed graph with positive weights</a> )</li> <li>Delete it</li> <li>Repeat until all vertexes have not been covered.</li> </ol> However, there may be efficient algorithms utilizing the properties of your case (the only one I can think of is that your graphs will be K-partite, where K is the number of unique characters in <code>S</code>). Good luck! Edit: Please refer to David's answer for a fuller and correct explanation of the problem.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POFinding the minimum number of swaps to convert one string to another, where the strings may have repeated characters
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USCommunity
UserOwnerUserId
1. USSubhasis Das
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. This table or related slice is empty.
CommentsPostId
1. This table or related slice is empty.

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.