<p><div><div><div><div data-width="100" data-show-faces="false" data-send="true" data-layout="button_count" data-height="21" data-href="http://www.r-bloggers.com/from-a-set-seed-grows-a-mighty-dataset/"></div></div><div><a data-url="http://www.r-bloggers.com/from-a-set-seed-grows-a-mighty-dataset/" data-counturl="http://www.r-bloggers.com/from-a-set-seed-grows-a-mighty-dataset/" data-count="horizontal" data-text="From a (set.)seed grows a mighty dataset" class="twitter-share-button" data-via="rbloggers" href="https://twitter.com/share"></a></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://jcarroll.com.au/2016/05/30/seed/"> R – Irregularly Scheduled Programming</a></strong>, and kindly contributed to <a rel="nofollow" href="http://www.r-bloggers.com/">R-bloggers)</a> </div>
<p>Can you predict the output from this code?</p>
<pre>
printStr &lt;- function(str) paste(str, collapse=&quot;&quot;)

set.seed(12173423); x &lt;- sample(LETTERS, 5, replace=TRUE)
set.seed(7723132);  y &lt;- sample(LETTERS, 5, replace=TRUE)

paste(printStr(x), printStr(y))
</pre>
<p>Okay, the first bit is straightforward; it’s a function that puts two string together into one. The next two lines appear to provide a random integer to the <code>set.seed</code> function then sample the pool of <code>LETTERS</code> 5 times with replacement. The last line uses the function from the first line to combine those samples of letters together into one string. Easy enough. Looks like it will produce a random string. Give it a try… go on, the seeds should make it reproducible.</p>
<pre>[1] &quot;HELLO WORLD&quot;</pre>
<p>Whoa! What are the odds of that!?! Of all the possible letters we could have sampled, we get that!</p>
<p>Okay, yes, it’s rigged. Pretty neat choice of values for <code>set.seed</code> there, right? I came across the <a target="_blank" href="http://stackoverflow.com/questions/15182496/why-does-this-code-using-random-strings-print-hello-world">Java variant of this</a> via StackOverflow’s ‘Hot Network Questions’ sidebar (a rabbit-hole equal in depth to a Wikipedia <a target="_blank" href="http://www.urbandictionary.com/define.php?term=wiki-hole">wiki-hole</a>). The seeds just happen to be ones that when sampled 5 times with replacement produce the right values to extract those letters in order. That seems simple enough until you want to find them.</p>
<p>The possible combinations of 5 letters, chosen with replacement, from the pool of 26 is <img title="26^5" alt="26^5" class="latex" src="http://s0.wp.com/latex.php?latex=26%5E5&bg=ffffff&%23038;fg=000&%23038;s=0"> which is a lot, but not insanely many. I work with multi-million row datasets frequently enough. So, we could just run a loop over all integers (<code>set.seed</code> rounds to nearest integer anyway; refer to <code>?set.seed</code>), set the seed to that value, and save the sampled letters. The first combination will be</p>
<pre>set.seed(1L)
sample(LETTERS, 5, replace=TRUE)
[1] &quot;G&quot; &quot;J&quot; &quot;O&quot; &quot;X&quot; &quot;F&quot;</pre>
<p>So, we write a loop and iterate over the seed, saving the outputs. But wait, you may wonder, what’s to guarantee that we don’t get the same sample twice? Nothing. It’s a random sample starting from a different seed every time; there’s no control over the results after the fact. A quick check confirms this; here’s a duplicate of the first record appearing at seed 3415066L</p>
<pre>set.seed(1L);       sample1 &lt;- sample(LETTERS, 5, replace=TRUE)
set.seed(3415066L); sample2 &lt;- sample(LETTERS, 5, replace=TRUE)
identical(sample1, sample2)
[1] TRUE</pre>
<p>So, <code>set.seed(1L)</code> produces the same 5 letter sample as <code>set.seed(3415066L)</code>. There’s definitely duplicates of other combinations between those two too. Okay, so we’re not going to be limited to <img title="26^5" alt="26^5" class="latex" src="http://s0.wp.com/latex.php?latex=26%5E5&bg=ffffff&%23038;fg=000&%23038;s=0">. How many though? Who knows? What’s the distribution of duplication? Without knowing how many we need to try for, we can take the upper limit and go for that; on my machine I get <code>.Machine$integer.max = </code>2147483647 which is certainly a bigger number, but not out of the realm of possibility.</p>
<p>To make life easier, we can split the problem up. It’s “embarrassingly parallel” (each iteration is completely independent of the others) so it’s perfect for parallelisation. If you haven’t read <a target="_blank" href="https://wrathematics.github.io/">Drew Schmidt a.k.a wrathematics’</a> <a target="_blank" href="https://wrathematics.github.io/RparallelGuide/">semi-NSFW guide to Parallelism, R, and OpenMP</a> then stop reading this and go read that.</p>
<p>You’re back, great. Let’s assume for now that you too have access to a big, fast computer and want to parallelise the loop over all positive integers. If you’re lucky, it’s as easy as</p>
<pre>library(parallel)
cl &lt;- makeCluster(7) ## 8-core machine, leave one out to remain stable
clusterApply(cl, seq(1, (.Machine$integer.max-1), 1e7), function(x) {
   wordvec &lt;- data.frame(word=character(1e7L), seed=integer(1e7L))
   for(iloop in 1:(1e7)) {
      iseed &lt;- x + iloop - 1
      if(abs(iseed) &lt; .Machine$integer.max) {
         set.seed(iseed)
         wordvec[iloop, &quot;word&quot;] &lt;- paste0(LETTERS[sample(26, 5, replace=TRUE)], collapse=&quot;&quot;)
         wordvec[iloop, &quot;word&quot;] &lt;- iseed
      }
   }
   write.csv(wordvec, file=paste0(&quot;seeded_words_&quot;,as.character(x),&quot;.csv&quot;))
   }
})</pre>
<p>but life’s not that easy. This is slow as a week of Mondays. For starters, updating the <code>data.frame</code> this many times will probably exhaust your RAM. This was run on a machine with 32GB available, and it got full, fast. Writing out large <code>.csv</code> files is slow, and given that each of them has ten million rows, the 215 files aren’t particularly small; there are a lot of duplicate entries.</p>
<p>We can make this better with a few adjustments;</p>
<pre>library(parallel)
cl &lt;- makeCluster(7) ## 8-core machine, leave one out to remain stable
clusterApply(cl, seq(1, (.Machine$integer.max-1), 1e7), function(x) {
   library(data.table)
   wordvec &lt;- data.table(word=character(1e7L), seed=integer(1e7L))
   for(iloop in 1:(1e7)) {
      iseed &lt;- x + iloop - 1
      if(abs(iseed) &lt; .Machine$integer.max) {
         set.seed(iseed)
         set(wordvec, i=iloop, j=&quot;word&quot;, value=paste0(LETTERS[sample(26, 5, replace=TRUE)], collapse=&quot;&quot;))
         set(wordvec, i=iloop, j=&quot;seed&quot;, value=iseed)
      }
   }
   unique_wordvec &lt;- unique(wordvec, by=&quot;word&quot;)
   save(unique_wordvec, file=paste0(&quot;seeded_words_&quot;,as.character(x),&quot;.rds&quot;))
   }
})</pre>
<p>Using <code>data.table</code> means that the <code>set()</code> operations <a target="_blank" href="https://gist.github.com/jonocarroll/a738212afde6394b4f251c7cac7f3348">are all in-memory</a> and this alone speeds up the loops. Removing duplicates using <code>unique</code> (now dispatched for <code>data.table</code>) and saving as a compressed binary <code>.rds</code> file makes this a little less bulky. All in all, this can be completed in a few hours on a decent enough machine. I did try using <a target="_blank" href="https://cran.r-project.org/web/packages/feather/index.html">feather</a> for the saving of files and my early tests using smaller subsets showed it to be amazingly fast. Unfortunately there are still some bugs to be ironed out of that package for large files/lots of rows, and my 215 files ended up small, but unreadable.</p>
<p>Given that there’s only <img title="26^5 = 11881376" alt="26^5 = 11881376" class="latex" src="http://s0.wp.com/latex.php?latex=26%5E5+%3D+11881376&bg=ffffff&%23038;fg=000&%23038;s=0"> combinations that we’re looking for, depending on how often duplicates come up, we probably don’t need all the results. I’ll save you the trouble and let you know that the loop only needs to go up to at most, <code>113449118</code>. Reading all of the files back in and merging them again requires some careful considerations. <code>R</code> isn’t too keen on creating objects larger than 2GB, so we can’t really just merge 113449118 lines of data. Taking it step-wise, I managed to get it to work</p>
<pre>library(data.table)
library(dplyr)
load(&quot;seeded_words_1.rds&quot;) ## load the first file
bigdf &lt;- unique_wordvec    ## objects were saved as unique_wordvec so save 
                           ## to a new name to avoid overwriting
rm(unique_wordvec)         ## then drop the saved version

allfiles &lt;- list.files(pattern=&quot;01.rds&quot;)

## files were saved as 'seeded_words_X.rds' where x was steps of 1e7
## sorting alphabetically gives the wrong order
for (file in allfiles[order(as.numeric(sub(&quot;\.rds&quot;,&quot;&quot;,sub(&quot;[a-z_]*&quot;,&quot;&quot;,allfiles))))]) {
  cat(paste0(&quot;** Processing file &quot;,file,&quot;n&quot;)) ## show notifications on the screen
  load(file)
  bigdf &lt;- unique(data.table(bind_rows(bigdf, unique_wordvec)), by=&quot;word&quot;) ## drop duplicates as we go
  rm(unique_wordvec)
  if(nrow(bigdf)&amp;gt;=26^5) { 
    cat(paste0(&quot;** Processing OUTPUT file.n&quot;))
    save(bigdf, file=&quot;all_seeded_words.rds&quot;)
    stop()
  }
}</pre>
<p>This results in a 75MB <code>.rds</code> of all unique combinations of 5 letters sampled with replacement, and the seed that generates them. Not particularly share-able or convenient. We’re mainly interested in actual words. We can filter this list down to English words if we can think of some way to do that (with the associated assumptions and limitations that may bring). Here’s one <code>R</code> option:</p>
<pre>library(ScrabbleScore)
words &lt;- bigdf[is.twl06.word(bigdf$word), ]</pre>
<p>This filters the generated 5-letter words against a <a target="_blank" href="https://en.wikipedia.org/wiki/Official_Tournament_and_Club_Word_List">Scrabble Official Tournament and Club Word List</a> which is as close as I can be bothered getting to ‘English’ words. What’s left is a list of <code>8938</code> 5-letter words with their associated generating seeds. Sure enough, filtering the <code>twl06</code> wordlist down to the 5-letter words gives exactly that many; we’ve generated all the 5-letter words in that data set. Cool. What were we hoping to do with it? Oh, right.</p>
<pre>print(words[&quot;HELLO&quot;])
     word     seed
 1: HELLO 12173423
print(words[&quot;WORLD&quot;])
     word    seed
 1: WORLD 7723132
</pre>
<p>There we go, the seeds used in the original question for this post. If we wanted, we could write other words or phrases in this way.</p>
<pre>set.seed(5360994);   x &lt;- sample(LETTERS, 5, replace=TRUE)
set.seed(21732771);  y &lt;- sample(LETTERS, 5, replace=TRUE)

paste(printStr(x), printStr(y))

[1] &quot;STATS RULES&quot;</pre>
<p>We might be interested in what the distribution of unique, English words looks like. Here you go;</p>
<pre>
library(ggplot2)
gg &lt;- ggplot(words, aes(x=seq_along(seed), y=seed)) 
gg &lt;- gg + geom_point(alpha=0.6, col=&quot;steelblue1&quot;, pch=20, size=2) 
gg &lt;- gg + theme_bw()
gg &lt;- gg + labs(title=&quot;Seed that generates unique, English words&quot;, 
                subtitle=&quot;Filtered as valid Scrabble TW06 words&quot;,
                caption=&quot;https://en.wikipedia.org/wiki/Official_Tournament_and_Club_Word_List&quot;,
                x=&quot;Index&quot;,
                y=&quot;Seed&quot;)
gg
</pre>
<p>I’ve converted that using the excellent <a target="_blank" href="https://plot.ly/ggplot2/"><code>plotly::ggplotly()</code> function</a> so you can mouseover each point to see the corresponding word.</p>
<p><iframe height="800" width="600" src="https://plot.ly/~jonocarroll/4.embed"></iframe></p>
<p>Fairly uniform looking in that plot. How about the density?</p>
<pre>
library(ggplot2)
gv &lt;- ggplot(words, aes(x=factor(0), y=seed)) 
gv &lt;- gv + geom_violin(fill=&quot;steelblue1&quot;) 
gv &lt;- gv + theme_bw()
gv &lt;- gv + theme(axis.title.x=element_blank(),
                 axis.text.x=element_blank(),
                 axis.ticks.x=element_blank())
gv &lt;- gv + labs(title=&quot;Violin plot of seed that generates unique, English words&quot;, 
                subtitle=&quot;Filtered as valid Scrabble TW06 words&quot;,
                caption=&quot;https://en.wikipedia.org/wiki/Official_Tournament_and_Club_Word_List&quot;,
                y=&quot;Seed&quot;)
gv
</pre>
<p><a target="_blank" href="http://i2.wp.com/jcarroll.com.au/wp-content/uploads/2016/05/violinplot-1.png"><img sizes="(max-width: 665px) 100vw, 665px" srcset="http://i2.wp.com/jcarroll.com.au/wp-content/uploads/2016/05/violinplot-1.png?w=665 665w, http://i2.wp.com/jcarroll.com.au/wp-content/uploads/2016/05/violinplot-1.png?resize=300%2C193 300w" alt="violinplot" class="wp-image-934" src="http://i2.wp.com/jcarroll.com.au/wp-content/uploads/2016/05/violinplot-1.png?resize=665%2C428" data-recalc-dims="1"></a></p>
<p>which looks pretty nicely vanishing as more duplicates are produced.</p>
<p>Finally, what about the distribution by starting letter?</p>
<p><iframe height="800" width="600" src="https://plot.ly/~jonocarroll/2.embed"></iframe></p>
<p>Unsurprisingly; not many words starting with “X” (13) and lots starting with “S” (1084). The last word produced (the one with the largest unique seed before we run out of unique words) is “HUTCH” at 113449118.</p>
<p>Can we do anything else with this? The first thing that comes to mind is using this to encode a message. This method is reminiscent of a hash function; it takes some data and via a 1-way mechanism, produces an encoded message. Of course, the 1-way nature of this takes a word and encodes it to an integer that can’t be easily predicted, so hopefully your message is all integers. Many reasons make this a bad idea to actually use for this purpose. The first being that in the world of digital security, if you’re thinking of rolling your own, you’re setting yourself up for trouble. Much smarter people than you or I have spent a lot of time getting digital security right, and it still isn’t.</p>
<p>As for actual technical issues, the obvious one is that it can be brute-forced (as we just showed) easily. I produced the list of all 5-letter combinations produced from all possible integers in a few hours. Modern GPU processing can perform many millions of these calculations per second. Another technical fault of this would be that collisions are all too easy, as demonstrated by our duplicates. A good encoding should only generate the hashed value from the input, not any other input. <a target="_blank" href="http://www.mathstat.dal.ca/~selinger/md5collision/">MD5 has this flaw</a>. If you were to try and use this encoding to validate a message (say, the integer represents a checksum of the message contents, encoded as a difficult to predict word) then it would be far too easy for a malicious entity to produce the same word from their own message padded out with junk data.</p>
<p>So, not very useful for encryption/hashing (not that it should be). I don’t really have a useful application for this apart from the riddle at the start of this post, but it’s been an interesting journey through optimisation, parallelisation, filtering, and file input/output. I’d say that has made it worthwhile enough.</p>
<p>The data file of valid Scrabble words can be <a target="_blank" href="https://github.com/jonocarroll/wp_content/raw/master/_data/scrabble_words.rds">downloaded here</a> if you’d like it. I’ll gladly provide the full 5-letter list on request.</p>
<p>The original content (not updated on RSS feed scraped syndicators) of this post is available on GitHub and you’re welcome to <a target="_blank" href="https://github.com/jonocarroll/wp_content/blob/master/_posts/2016-05-30-seed.md">provide suggestions/edits.</a></p>
<p>I’m not a data-security expert so any and all of my advice there is liable to be rubbish. Do you know a better way to generate this data, or an aspect I haven’t considered? Hit the comments and let me know.</p>
<p>Title image: <a target="_blank" href="https://www.flickr.com/photos/usdagov/16024807396/">CC-BY U.S. Department of Agriculture</a></p>
<p><div><div><div><div data-width="55" data-show-faces="false" data-send="true" data-layout="box_count" data-height="62" data-href="http://www.r-bloggers.com/from-a-set-seed-grows-a-mighty-dataset/"></div></div><div><a data-url="http://www.r-bloggers.com/from-a-set-seed-grows-a-mighty-dataset/" data-counturl="http://www.r-bloggers.com/from-a-set-seed-grows-a-mighty-dataset/" data-count="vertical" data-text="From a (set.)seed grows a mighty dataset" class="twitter-share-button" data-via="rbloggers" href="https://twitter.com/share"></a></div><div></div></div><div></div></div>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="http://jcarroll.com.au/2016/05/30/seed/"> R – Irregularly Scheduled Programming</a></strong>.</div>
<hr>
<a rel="nofollow" href="http://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="http://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a title="The R Project for Statistical Computing" rel="nofollow" href="http://www.r-project.org/">R</a> news and <a title="R tutorials" rel="nofollow" href="http://www.r-bloggers.com/?s=tutorial">tutorials</a> on topics such as: <a title="Data science" rel="nofollow" href="http://www.r-bloggers.com/?s=data%20science">Data science</a>, <a title="Big Data" rel="nofollow" href="http://www.r-bloggers.com/?s=Big%20Data">Big Data, <a title="R jobs" rel="nofollow" href="http://www.r-users.com/">R jobs</a>, visualization (<a title="ggplot and ggplot2 tutorials" rel="nofollow" href="http://www.r-bloggers.com/?s=ggplot2">ggplot2</a>, <a title="Boxplots using lattice and ggplot2 tutorials" rel="nofollow" href="http://www.r-bloggers.com/?s=boxplot">Boxplots</a>, <a title="Maps and gis" rel="nofollow" href="http://www.r-bloggers.com/?s=map">maps</a>, <a title="Animation in R" rel="nofollow" href="http://www.r-bloggers.com/?s=animation">animation</a>), programming (<a title="RStudio IDE for R" rel="nofollow" href="http://www.r-bloggers.com/?s=RStudio">RStudio</a>, <a title="Sweave and literate programming" rel="nofollow" href="http://www.r-bloggers.com/?s=sweave">Sweave</a>, <a title="LaTeX in R" rel="nofollow" href="http://www.r-bloggers.com/?s=LaTeX">LaTeX</a>, <a title="SQL and databases" rel="nofollow" href="http://www.r-bloggers.com/?s=SQL">SQL</a>, <a title="Eclipse IDE for R" rel="nofollow" href="http://www.r-bloggers.com/?s=eclipse">Eclipse</a>, <a title="git and github, Version Control System" rel="nofollow" href="http://www.r-bloggers.com/?s=git">git</a>, <a title="Large data in R using Hadoop" rel="nofollow" href="http://www.r-bloggers.com/?s=hadoop">hadoop</a>, <a title="Web Scraping of google, facebook, yahoo, twitter and more using R" rel="nofollow" href="http://www.r-bloggers.com/?s=Web+Scraping">Web Scraping</a>) statistics (<a title="Regressions and ANOVA analysis tutorials" rel="nofollow" href="http://www.r-bloggers.com/?s=regression">regression</a>, <a title="principal component analysis tutorial" rel="nofollow" href="http://www.r-bloggers.com/?s=PCA">PCA</a>, <a title="Time series" rel="nofollow" href="http://www.r-bloggers.com/?s=time+series">time series</a>, <a title="finance trading" rel="nofollow" href="http://www.r-bloggers.com/?s=trading">trading</a>) and more...
<img height="1" alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/sc29y8wr9uA"></a></div>