Timeline for Upper bound on the number of permutations in a set during an algorithm
Current License: CC BY-SA 3.0
31 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 6, 2017 at 19:39 | comment | added | Matt Samuel | @J.J. worth a shot. I managed to get it down to 16 bytes per permutation, so about 87 TB. I can't think of any other space optimizations. Oddly enough this compressed representation is actually faster. | |
| Dec 6, 2017 at 0:21 | vote | accept | Matt Samuel | ||
| Dec 3, 2017 at 12:10 | comment | added | J.J. Green | @MattSamuel : I know that feeling, I'm in a similar situation myself. Why not be cheeky and ask for a freebie? EC2, Azure etc have plenty of smart kids who will see the intrinsic value, and it would make a good press release for them, so has business value too. At worst they can say no. | |
| Dec 2, 2017 at 15:23 | comment | added | Matt Samuel | @J.J. I could distribute it across 8 16TB instances. However, that would cost a fortune, and I'm not employed by a school or research institution so I doubt I can get a grant. | |
| Dec 1, 2017 at 21:53 | comment | added | Matt Samuel | Yes, the 22 bytes includes a massively compressed representation of the permutation together with a 128-bit integer. | |
| Dec 1, 2017 at 21:50 | comment | added | Gerhard Paseman | If there were a linear relationship between M_n and the OEIS sequence, he probably would not need much memory. My guess is that for each permutation he has to compute a value, and then add them up. The 22 bytes probably holds additional structure he is using for the value computation. Gerhard "That's How I'd Do It" Paseman, 2017.12.01. | |
| Dec 1, 2017 at 21:27 | comment | added | J.J. Green | Could you explain the 22 bytes? 0..15 fits in 4 bits, and 16 of those is 8 bytes. Perhaps I'm being dense here ... | |
| Dec 1, 2017 at 21:05 | comment | added | Matt Samuel | @J.J. My most optimistic estimation using Gerhard's answer is 113TB for n=16. 16TB could get me n=15, which is already known. | |
| Dec 1, 2017 at 21:00 | comment | added | J.J. Green | Might be worth looking at EC2: 4TB instances are available now (x1e.32xlarge) with 16TB in the pipeline. Of course you have to get your wallet out .. | |
| Dec 1, 2017 at 18:52 | answer | added | Gerhard Paseman | timeline score: 2 | |
| Dec 1, 2017 at 17:00 | comment | added | Matt Samuel | @Gerhard Estimate I need about 175GB to compute n=13. I could've done that on the computer I had access to when I was a student, but with my current computer (which is actually a server at the company I work at that really shouldn't be used for this) I only have 72GB of RAM and even less disk space | |
| Dec 1, 2017 at 15:33 | comment | added | Matt Samuel | @Gerhard 13 one or two days, 14 maybe a week or two, 15 several weeks. For any of those values though I need to obtain more memory, so it's not something I can readily do at the moment. | |
| Dec 1, 2017 at 15:26 | comment | added | Gerhard Paseman | How long would it take at present to compute M13 and M14? Days or weeks? Gerhard "Also Has Problems With Memory" Paseman, 2017.12.01. | |
| Dec 1, 2017 at 15:18 | comment | added | Matt Samuel | @Gerhard The amount of space required is at the bare minimum 22 bytes times $M_{16}$. That's many terabytes. No computer I know of has enough RAM, so it will involve permanent storage, which is slow. With RAM it would already take thousands of hours. I'm confident it will eventually be feasible, but not sure about now. | |
| Dec 1, 2017 at 14:41 | comment | added | Gerhard Paseman | Based on the numerics given for 5 through 12, I predict 0.24* 16! is a lower bound. Gerhard "Bordering The Chasm Of Unfeasability" Paseman, 2017.12.01. | |
| Dec 1, 2017 at 11:26 | history | edited | Matt Samuel | CC BY-SA 3.0 |
added 269 characters in body
|
| Dec 1, 2017 at 1:39 | comment | added | Matt Samuel | @fedja I meant $f(b_i)<f(b_i+1)$. Sorry about that. | |
| Dec 1, 2017 at 1:38 | history | edited | Matt Samuel | CC BY-SA 3.0 |
edited body
|
| Dec 1, 2017 at 1:36 | comment | added | fedja | If the ordering of $b$ does not matter, what does the condition $f(b_i)<f(b_{i+1})$ mean? (One can reorder any set $B$ according to $f(b)$. | |
| Nov 30, 2017 at 23:07 | comment | added | Gerhard Paseman | Also, since you are "comparing" them with f, the order of the b's does matter. However, if you are iterating over all permutations of all subsets, then you can show what you do is equivalent to "picking your favorite ordering of B" that gets the job done. Gerhard "It's About Getting It Done" Paseman, 2017.11.30. | |
| Nov 30, 2017 at 22:44 | comment | added | Gerhard Paseman | OK. Your use of maximal, while correct, throws me off because I think of maximal intervals as well. Gerhard "Understanding Is Not Yet Maximal" Paseman, 2017.11.30. | |
| Nov 30, 2017 at 22:10 | comment | added | Matt Samuel | @Ger 1) It doesn't matter if they're ordered, by the condition that they differ by at least $2$ it follows that the transpositions commute. 2) those are all the same permutation. 3) Yes, because $C$ would be another subset of the same type. | |
| Nov 30, 2017 at 22:03 | comment | added | Gerhard Paseman | It is not clear to me if 1) the bi in B are ordered so bi is less than b(i+1) 2) you add all permutations of B by 'also' adding fb2b1... 3) If B is used and C is a proper subset of B then C is also used. Dumb question, but maybe a lower bound of what does not get put in would help: is there a characterization of permutations that never get added? Gerhard "Sometimes Not Solving Is Easier" Paseman, 2017.11.30. | |
| Nov 30, 2017 at 19:05 | comment | added | Matt Samuel | @fedja Yes. This comment is too short. | |
| Nov 30, 2017 at 19:05 | comment | added | fedja | So $15423< 31452$, right? (just to make sure that we have no misunderstanding here) | |
| Nov 30, 2017 at 19:02 | comment | added | Matt Samuel | @fedja From the beginning, increasing. Literally alphabetical order. | |
| Nov 30, 2017 at 18:55 | comment | added | fedja | In which of 4 possible directions does your lexicographical order go? (from the beginning or from the end, increasing or decreasing?) | |
| Nov 30, 2017 at 18:20 | comment | added | Gerhard Paseman | I think the quickest answer will be to compute M13 through M15 first. I do not understand the description well enough to estimate it for you. (Sizes for small n, say n =6, as well as Ak for small k might help. Even knowing if Ak sizes is a unimodular sequence and for which k there is a peak might help.). I encourage you to post an answer with more detail, so that people can refer to the detail separately. Gerhard "Even Though Not An Answer" Paseman, 2017.11.30. | |
| Nov 30, 2017 at 17:20 | history | edited | Matt Samuel | CC BY-SA 3.0 |
deleted 51 characters in body; added 41 characters in body
|
| Nov 30, 2017 at 16:41 | history | edited | Matt Samuel | CC BY-SA 3.0 |
edited body; deleted 12 characters in body
|
| Nov 30, 2017 at 16:30 | history | asked | Matt Samuel | CC BY-SA 3.0 |