Timeline for Reconstructing an ordering of a multiset from its consecutive submultisets
Current License: CC BY-SA 2.5
33 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 2, 2010 at 6:15 | answer | added | Aaron Meyerowitz | timeline score: 0 | |
| Feb 3, 2010 at 2:11 | vote | accept | Rob Grey | ||
| Feb 3, 2010 at 2:11 | vote | accept | Rob Grey | ||
| Feb 3, 2010 at 2:11 | |||||
| Feb 3, 2010 at 2:10 | vote | accept | Rob Grey | ||
| Feb 3, 2010 at 2:11 | |||||
| Jan 20, 2010 at 1:20 | comment | added | Steve Huntsman | @Qiaochu: In my usage the generalized de Bruijn graph depends intimately on the word in question. It looks like your B(r,j) is a standard de Bruijn graph on an alphabet that is not necessarily binary. | |
| Jan 19, 2010 at 21:04 | comment | added | Qiaochu Yuan | Now that I understand the graph-theoretic formulation of the problem, I've added it back into the question. | |
| Jan 19, 2010 at 21:03 | history | edited | Qiaochu Yuan | CC BY-SA 2.5 |
Added a restatement of the problem.
|
| Jan 19, 2010 at 15:10 | answer | added | Qiaochu Yuan | timeline score: 2 | |
| Jan 19, 2010 at 5:21 | answer | added | Steve Huntsman | timeline score: 0 | |
| Jan 19, 2010 at 4:34 | answer | added | Steve Huntsman | timeline score: 2 | |
| Jan 19, 2010 at 3:37 | answer | added | Harrison Brown | timeline score: 3 | |
| Jan 19, 2010 at 2:54 | history | edited | Qiaochu Yuan | CC BY-SA 2.5 |
deleted 1 characters in body
|
| Jan 19, 2010 at 2:43 | history | edited | Qiaochu Yuan | CC BY-SA 2.5 |
added 71 characters in body
|
| Jan 18, 2010 at 23:05 | comment | added | Rob Grey | Qiaochu, "...are you given the order of the scrambled multisets..." - No, and that's why I've been having trouble with this problem. With the order (and no gaps), one should be able to infer the original permutation just by lining them up and looking at which elements change between subsets. Lack of subset order information is also why having subsets with the same number of distinctive members is such a problem. | |
| Jan 18, 2010 at 22:59 | comment | added | Qiaochu Yuan | The extra information after your statement of the question was lagging my browser, so I deleted it; it's still available in the edit history if you put it back, but for now I think the question is a little clearer without it. A final point of clarification: are you given the order of the scrambled multisets, i.e. do you know which one corresponds to the first J entries, etc.? | |
| Jan 18, 2010 at 22:55 | history | edited | Qiaochu Yuan | CC BY-SA 2.5 |
Rephrased question.; deleted 3235 characters in body
|
| Jan 18, 2010 at 22:37 | comment | added | Rob Grey | Qiaochu, yes, that's precisely what I mean. I appreciate any editing help. | |
| Jan 18, 2010 at 22:36 | comment | added | Rob Grey | Qiaochu, point taken and I understand the importance of proper notation. In this particular case, an issue is that I'm talking about very large multisets with only a few elements. That's what I thought I might write what I did with the appended note that I was talking about "distinct elements" up to $R$. For the binary string example, I was trying to illustrate a particular permutation of the multiset. | |
| Jan 18, 2010 at 22:35 | comment | added | Qiaochu Yuan | Let me make sure I understand what you mean by point 3. We want to deduce a particular ordering on a multiset, e.g. 2111223 being an ordering of the multiset {1, 1, 1, 2, 2, 3}, given only the number of elements of type 1, 2, 3 in each consecutive block of J elements, e.g. {1, 2}, {1, 1}, {1, 1}, {1, 2}, {2, 2}, {2, 3} when J = 2. Is this correct? If so, do you mind if I edit your question a little for clarity? | |
| Jan 18, 2010 at 22:29 | comment | added | Qiaochu Yuan | Another point of clarification: the "proper" way to represent a multiset on 0, 1, ... R-1 (I assume this is what you meant) is to write out the elements in increasing order, e.g. 0000112333... This is because multisets, like sets, don't come with a preferred order for writing their elements down. | |
| Jan 18, 2010 at 22:26 | history | edited | Rob Grey | CC BY-SA 2.5 |
Added note that initial segment of permutation is available to you.
|
| Jan 18, 2010 at 22:20 | history | edited | Rob Grey | CC BY-SA 2.5 |
Changed 'set' to 'multiset' due to sets only having distinctive elements.
|
| Jan 18, 2010 at 22:17 | comment | added | Rob Grey | Yikes, apologies... I'll make the fix. Thanks! | |
| Jan 18, 2010 at 22:15 | comment | added | Qiaochu Yuan | Oh! Rob, in mathematics a set is always defined to have distinct elements. The object you're talking about is a multiset. | |
| Jan 18, 2010 at 22:11 | comment | added | Qiaochu Yuan | Your notation is very confusing. What does R = 2 mean if there are T elements in your set? | |
| Jan 18, 2010 at 22:11 | history | edited | Rob Grey | CC BY-SA 2.5 |
edited body
|
| Jan 18, 2010 at 22:09 | comment | added | Rob Grey | Qiaochu, I was talking about representing a unique permutation of two elements as a binary string (and only talking about binary strings as an illustrative example), not trying to enumerate permutations or list permutations. My objective here is to try to recover a unique permutation in S with the scrambled subsets. Does that make more sense to you, or should I try to rewrite the question? | |
| Jan 18, 2010 at 22:03 | comment | added | Qiaochu Yuan | Rob, I'm still confused. How are you writing permutations as binary strings? | |
| Jan 18, 2010 at 21:56 | answer | added | Gerhard Paseman | timeline score: 3 | |
| Jan 18, 2010 at 21:54 | history | edited | Rob Grey | CC BY-SA 2.5 |
Changed 'ordered set' to 'permutation of set', fixed brackets, cleared up what the subsets of S are...; added 21 characters in body
|
| Jan 18, 2010 at 21:45 | comment | added | Rob Grey | Dear Tom, the square brackets have no special meaning, I was using them because jsMath was making '{}' brackets disappear (I'll fix it because it's caused concern) - for [0,1,...,R] I'm simply referring to a set with up to 'R' unique elements in it. Also, I meant 'ordered set $S$' in a loose computer-science sense (again, sloppy) - I should say 'permutation of a set $S$'. The idea is that with two unique elements in $S$, a binary string with a length equal to the cardinality of $S$ would represent a particular permutation. | |
| Jan 18, 2010 at 21:14 | comment | added | Tom Leinster | Rob, there are some things about your question I don't understand. When you write "[0,1,...,R]", what do the square brackets mean? When you say that the ordered set S can be represented as a binary string, what do you mean? I wonder whether you're using the term "ordered set" in the usual mathematical sense, as for instance in en.wikipedia.org/wiki/Order_theory . If not, some clarification would be good. | |
| Jan 18, 2010 at 18:23 | history | asked | Rob Grey | CC BY-SA 2.5 |