StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
17029269
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
2013-06-14T15:58:08.487
CreationDate
2013-06-10T17:10:08.170
FavoriteCount
0
LastActivityDate
2013-06-14T15:58:08.487
LastEditDate
2013-06-14T15:58:08.487
LastEditorUserId
1828879
OwnerUserId
1828879
ParentId
17017903
PostTypeId
2
Score
7
ViewCount
0
LastEditorDisplayName
text
Body
<h1>Naive solution</h1> A naive solution to consider is to generate every possible <code>n</code>-by-<code>n</code> matrix <code>E</code> where each component is a nonnegative integer no greater than <code>n</code>, then take from those only the matrices that satisfy the additional constraints. What would be the complexity of that? Each component can take on <code>n + 1</code> values, and there are <code>n^2</code> components, so there are <code>O((n+1)^(n^2))</code> candidate matrices. That has an insanely high growth rate. Link: <a href="http://www.wolframalpha.com/input/?i=%28n%2B1%29%5E%28n%5E2%29" rel="nofollow">WolframAlpha analysis of <code>(n+1)^(n^2)</code></a> I think it's safe to safe that this not a feasible approach. <h1>Better solution</h1> A better solution follows. It involves a lot of math. Let <code>S</code> be the set of all matrices <code>E</code> that satisfy your requirements. Let <code>N = {1, 2, ..., n}</code>. Definitions: <ul> <li>Let a metric on <code>N</code> to have the usual definition, except with the requirement of symmetry omitted.</li> <li>Let <code>I</code> and <code>J</code> partition the set <code>N</code>. Let <code>D(I,J)</code> be the <code>n</code> x <code>n</code> matrix that has <code>D_ij = 1</code> when <code>i</code> is in <code>I</code> and <code>j</code> is in <code>J</code>, and <code>D_ij = 0</code> otherwise.</li> <li>Let <code>A</code> and <code>B</code> be in <code>S</code>. Then <code>A</code> is adjacent to <code>B</code> if and only if there exist <code>I</code> and <code>J</code> partitioning <code>N</code> such that <code>A + D(I,J) = B</code>. We say <code>A</code> and <code>B</code> are adjacent if and only if <code>A</code> is adjacent to <code>B</code> or <code>B</code> is adjacent to <code>A</code>.</li> <li>Two matrices <code>A</code> and <code>B</code> in <code>S</code> are path-connected if and only if there exists a sequence of adjacent elements of <code>S</code> between them.</li> <li>Let the function <code>M(E)</code> denote the sum of the elements of matrix <code>E</code>.</li> </ul> Lemma 1: <code>E = D(I,J)</code> is a metric on <code>N</code>. <blockquote> Proof: This is a trivial statement except for the case of an edge going from <code>I</code> to <code>J</code>. Let <code>i</code> be in <code>I</code> and <code>j</code> be in <code>J</code>. Then <code>E_ij = 1</code> by definition of <code>D(I,J)</code>. Let <code>k</code> be in <code>N</code>. If <code>k</code> is in <code>I</code>, then <code>E_ik = 0</code> and <code>E_kj = 1</code>, so <code>E_ik + E_kj >= E_ij</code>. If <code>k</code> is in <code>J</code>, then <code>E_ik = 1</code> and <code>E_kj = 0</code>, so <code>E_ij + E_kj >= E_ij</code>. </blockquote> Lemma 2: Let <code>E</code> be in <code>S</code> such that <code>E != zeros(n,n)</code>. Then there exist <code>I</code> and <code>J</code> partitioning <code>N</code> such that <code>E' = E - D(I,J)</code> is in <code>S</code> with <code>M(E') < M(E)</code>. <blockquote> Proof: Let <code>(i,j)</code> be such that <code>E_ij > 0</code>. Let <code>I</code> be the subset of <code>N</code> that can be reached from <code>i</code> by a directed path of cost <code>0</code>. <code>I</code> cannot be empty, because <code>i</code> is in <code>I</code>. <code>I</code> cannot be <code>N</code>, because <code>j</code> is not in <code>I</code>. This is because <code>E</code> satisfies the triangle inequality and <code>E_ij > 0</code>. Let <code>J = N - I</code>. Then <code>I</code> and <code>J</code> are both nonempty and partition <code>N</code>. By the definition of <code>I</code>, there does not exist any <code>(x,y)</code> such that <code>E_xy = 0</code> and <code>x</code> is in <code>I</code> and <code>y</code> is in <code>J</code>. Therefore <code>E_xy >= 1</code> for all <code>x</code> in <code>I</code> and <code>y</code> in <code>J</code>. Thus <code>E' = E - D(I,J) >= 0</code>. That <code>M(E') < M(E)</code> is obvious, because all we have done is subtract from elements of <code>E</code> to get <code>E'</code>. Now, since <code>E</code> is a metric on <code>N</code> and <code>D(I,J)</code> is a metric on <code>N</code> (by Lemma 1) and <code>E >= D(I,J)</code>, we have <code>E'</code> is a metric on <code>N</code>. Therefore <code>E'</code> is in <code>S</code>. </blockquote> Theorem: Let <code>E</code> be in <code>S</code>. Then <code>E</code> and <code>zeros(n,n)</code> are path-connected. <blockquote> Proof (by induction): If <code>E = zeros(n,n)</code>, then the statement is trivial. Suppose <code>E != zeros(n,n)</code>. Let <code>M(E)</code> be the sum of the values in <code>E</code>. Then, by induction, we can assume that the statement is true for any matrix <code>E'</code> having <code>M(E') < M(E)</code>. Since <code>E != zeros(n,n)</code>, by Lemma 2 we have some <code>E'</code> in <code>S</code> such that <code>M(E') < M(E)</code>. Then by the inductive hypothesis <code>E'</code> is path-connected to <code>zeros(n,n)</code>. Therefore <code>E</code> is path-connected to <code>zeros(n,n)</code>. </blockquote> Corollary: The set <code>S</code> is path-connected. <blockquote> Proof: Let <code>A</code> and <code>B</code> be in <code>S</code>. By the Theorem, <code>A</code> and <code>B</code> are both path-connected to <code>zeros(n,n)</code>. Therefore <code>A</code> is path-connected to <code>B</code>. </blockquote> <h1>Algorithm</h1> The Corollary tells us that everything in <code>S</code> is path-connected. So an effective way to discover all of the elements of <code>S</code> is to perform a breadth-first search over the graph defined by the following. <ul> <li>The elements of <code>S</code> are the nodes of the graph</li> <li>Nodes of the graph are connected by an edge if and only if they are adjacent</li> </ul> Given a node <code>E</code>, you can find all of the (potentially) unvisited neighbors of <code>E</code> by simply enumerating all of the possible matrices <code>D(I,J)</code> (of which there are <code>2^n</code>) and generating <code>E' = E + D(I,J)</code> for each. Enumerating the <code>D(I,J)</code> should be relatively straightforward (there is one for every possible subset <code>I</code> of <code>D</code>, except for the empty set and <code>D</code>). Note that, in the preceding paragraph, <code>E</code> and <code>D(I,J)</code> are both metrics on <code>N</code>. So when you generate <code>E' = E + D(I,J)</code>, you don't have to check that it satisfies the triangle inequality - <code>E'</code> is the sum of two metrics, so it is a metric. To check that <code>E'</code> is in <code>S</code>, all you have to do is verify that the maximum element in <code>E'</code> does not exceed <code>n</code>. You can start the breadth-first search from any element of <code>S</code> and be guaranteed that you won't miss any of <code>S</code>. So you can start the search with <code>zeros(n,n)</code>. <hr> Be aware that the cardinality of the set <code>S</code> grows extremely fast as <code>n</code> increases, so computing the entire set <code>S</code> will only be tractable for small <code>n</code>.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POHow to generate matrices which satisfy the triangle inequality?
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USTimothy Shields
UserOwnerUserId
1. USTimothy Shields
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POHow to generate matrices which satisfy the triangle inequality?
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
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.