Talk:Last letter-first letter: Difference between revisions
Content added Content deleted
No edit summary |
|||
| Line 3: | Line 3: | ||
: Re input data; I can always host input data if that makes it convenient to work on appropriate data. --[[User:Short Circuit|Michael Mol]] 23:12, 5 June 2011 (UTC) |
: Re input data; I can always host input data if that makes it convenient to work on appropriate data. --[[User:Short Circuit|Michael Mol]] 23:12, 5 June 2011 (UTC) |
||
:: That's not really the problem. A quick breadth first search implementation gave me 646 pokemon names, 1793 pokemon name pairs, 518546 pokemon name triples, 14745709 pokemon name quadruples, and I had to reboot my machine to recover from my attempt to represent all pokemon name quintuples. Inspecting this sequence suggests a search space on the order of 28^28 or about 3e40 sequences to investigate. That exceeds the storage capacity of my laptop. (Not to mention, exceeds my patience). Note that finding a long sequence is not very hard, it's finding the '''longest''' that makes this task hard. --[[User:Rdm|Rdm]] 20:08, 6 June 2011 (UTC) |
:: That's not really the problem. A quick breadth first search implementation gave me 646 pokemon names, 1793 pokemon name pairs, 518546 pokemon name triples, 14745709 pokemon name quadruples, and I had to reboot my machine to recover from my attempt to represent all pokemon name quintuples. Inspecting this sequence suggests a search space on the order of 28^28 or about 3e40 sequences to investigate. That exceeds the storage capacity of my laptop. (Not to mention, exceeds my patience). Note that finding a long sequence is not very hard, it's finding the '''longest''' that makes this task hard. --[[User:Rdm|Rdm]] 20:08, 6 June 2011 (UTC) |
||
::: If the part about using all the pokemon names was changed, it'd be an interesting task. 20 or so names/words/nodes should demonstrate the process well enough without being too slow. [[User:MagiMaster|MagiMaster]] 21:37, 6 June 2011 (UTC) |
|||
Revision as of 21:37, 6 June 2011
Number of names
This is equivalent to asking for the longest path in a directed graph, which is an NP-complete problem. That doesn't rule it out as a task, but running it on a graph with 646 nodes might take too long. Also, since it seems to be rare to use external files to store the data (or at least I haven't seen many tasks that call for that) having all the names in each example would get really cluttered. MagiMaster 20:52, 5 June 2011 (UTC)
- Re input data; I can always host input data if that makes it convenient to work on appropriate data. --Michael Mol 23:12, 5 June 2011 (UTC)
- That's not really the problem. A quick breadth first search implementation gave me 646 pokemon names, 1793 pokemon name pairs, 518546 pokemon name triples, 14745709 pokemon name quadruples, and I had to reboot my machine to recover from my attempt to represent all pokemon name quintuples. Inspecting this sequence suggests a search space on the order of 28^28 or about 3e40 sequences to investigate. That exceeds the storage capacity of my laptop. (Not to mention, exceeds my patience). Note that finding a long sequence is not very hard, it's finding the longest that makes this task hard. --Rdm 20:08, 6 June 2011 (UTC)
- If the part about using all the pokemon names was changed, it'd be an interesting task. 20 or so names/words/nodes should demonstrate the process well enough without being too slow. MagiMaster 21:37, 6 June 2011 (UTC)
- That's not really the problem. A quick breadth first search implementation gave me 646 pokemon names, 1793 pokemon name pairs, 518546 pokemon name triples, 14745709 pokemon name quadruples, and I had to reboot my machine to recover from my attempt to represent all pokemon name quintuples. Inspecting this sequence suggests a search space on the order of 28^28 or about 3e40 sequences to investigate. That exceeds the storage capacity of my laptop. (Not to mention, exceeds my patience). Note that finding a long sequence is not very hard, it's finding the longest that makes this task hard. --Rdm 20:08, 6 June 2011 (UTC)