title: Generate multiple permutations of vector with non-repeating elements
body: <p>I have a vector:</p>
  
  <pre><code>seq1&lt;-c('a','b','c','b','a','b','c','b','a','b','c')
  </code></pre>
  
  <p>I wish to permute the elements of this vector to create multiple (ideally up to 5000) vectors with the condition that the permuted vectors cannot have repeated elements within the vector in consecutive elements. e.g. "abbca...." is not allowed as 'b-b' is a repeat.</p>
  
  <p>I realize that for this small example there probably are not 5000 solutions. I am typically dealing with much larger vectors.    I am also willing to consider sampling with replacement, though currently I'm working on solutions without replacement.</p>
  
  <p>I am looking for better solutions than my current thinking.</p>
  
  <p><strong>Option 1. - brute force.</strong></p>
  
  <p>Here, I just repeatedly sample and check if any successive elements are duplicates.  </p>
  
  <pre><code>set.seed(18)
  seq1b &lt;-  sample(seq1a)
  seq1b
  #[1] "b" "b" "a" "a" "c" "b" "b" "c" "a" "c" "b"
  sum(seq1b[-length(seq1b)]==seq1b[-1])  #3
  </code></pre>
  
  <p>This is not a solution as there are 3 duplicated consecutive elements.  I also realize that <code>lag</code> is probably a better way to check for duplicated elements but for some reason it is being finicky (I think it is being masked by another package I have loaded).</p>
  
  <pre><code>set.seed(1000)
  res&lt;-NULL
  for (i in 1:10000){res[[i]]&lt;-sample(seq1a)}
  res1 &lt;- lapply(res, function(x) sum(x[-length(x)]==x[-1]))
  sum(unlist(res1)==0) #228
  </code></pre>
  
  <p>This produces 228 options out of 10000 iterations.  But let's see how many unique ones:</p>
  
  <pre><code>res2 &lt;- res[which(unlist(res1)==0)]
  unique(unlist(lapply(res2, paste0, collapse="")))  #134
  </code></pre>
  
  <p>Out of 10000 attempts we only get 134 unique ones from this short example vector.</p>
  
  <p>Here are 3 of the 134 example sequences produced:</p>
  
  <pre><code># "bcbabcbabca" "cbabababcbc" "bcbcababacb"
  </code></pre>
  
  <p>In fact, if I try over 500,000 samples, I can only get 212 unique sequences that match my non-repeating criteria.  This is probably close to the upper limit of possible ones.</p>
  
  <p><strong>Option 2. - iteratively</strong></p>
  
  <p>A second idea I had is to be more iterative about the approach.</p>
  
  <pre><code>seq1a
  table(seq1a)
  #a b c 
  #3 5 3
  </code></pre>
  
  <p>We could sample one of these letters as our starting point.  Then sample another from the remaining ones, check if it is the same as the previously chosen one and if not, add it to the end.  And so on and so forth...</p>
  
  <pre><code>set.seed(10)
  newseq &lt;- sample(seq1a,1)  #b
  newseq #[1] "b"
  
  remaining &lt;-seq1a[!seq1a %in% newseq | duplicated(seq1a)]
  table(remaining)
  #a b c 
  #3 4 3 
  
  set.seed(10)
  newone &lt;- sample(remaining,1) #c
  
  #check if newone is same as previous one.
  newone==newseq[length(newseq)] #FALSE
  newseq &lt;- c(newseq, newone) #update newseq
  newseq #[1] "b" "c"
  
  remaining &lt;-seq1a[!seq1a %in% newseq | duplicated(seq1a)] #update remaining
  remaining
  table(remaining)
  
  #a b c 
  #3 4 2 
  </code></pre>
  
  <p>This might work, but I can also see it running into lots of issues - e.g. we could go:</p>
  
  <pre><code># "a" "c" "a" "c" "a" "b"  ...
  </code></pre>
  
  <p>and then be left with 3 more 'b's that cannot go at the end as they'd be duplicates.</p>
  
  <p>Of course, this would be a lot easier if I allowed sampling with replacement, but for now I'm trying to do this without replacement.</p>