[Question]
  [
Upon the rumor that Codegolf will have a *Rock-Paper-Scissors tournament* you look into the topic of **square-free words**. A word made of the letters `R`, `P`, `S` is *square-free* if it does not contain a sequence that repeats twice. That is to say, the word can not be written as
```
a x x b
```
where `a` and `b` are words of any length and `x` is a word of length at least one, all made of the letters `R`, `P`, `S`.
## Task
Write a program that generates the *square-free* words of the letters `R`, `P`, `S` of length `n` where the number `1 <= n <= 10` is taken as input. 
## Example
For example the *square-free* words of length 3 are
`RPR`, `RSR`, `RPS`, `RSP`, `SPS`, `SRS`, `SRP`, `SPR`, `PRP`, `PSP`, `PSR`, `PRS`
and those of length 4 are
`RPRS`, `RPSR`, `RPSP`, `RSRP`, `RSPR`, `RSPS`, `PRPS`, `PRSR`, `PRSP`, `PSRP`, `PSRS`, `PSPR`, `SRPR`, `SRPS`, `SRSP`, `SPRP`, `SPRS`, `SPSR`
and note that for example `SPSP` or `PRPR` are not square-free
## Rules
* This is codegolf, shortest program wins, standard loopholes are closed.
* You may print the words or create them in memory.
* Your program may be written as a function.
## References
[Wikipedia entry on square-free words](https://en.wikipedia.org/wiki/Square-free_word)
The number of square-free ternary words of given length are
in <https://oeis.org/A006156> 
Related: [Arbitrary-Length Ternary Squarefree Words](https://codegolf.stackexchange.com/questions/10601/arbitrary-length-ternary-squarefree-words)
  
[Answer]
# Ruby, 39 bytes
```
->n{(?P*n..?S*n).grep_v /[^RPS]|(.+)\1/}
```
This hilariously inefficient function generates all strings of length N that lie alphabetically between N Ps and N Ss, then filters out the vast majority that contain non-RPS characters. The actual squarefree check just uses a Regexp backreference: `(.+)\1`.
More idiomatic **65 bytes** that finish in a reasonable amount of time for N=10:
```
->n{%w[R P S].repeated_permutation(n).map(&:join).grep_v /(.+)\1/}
```
Edit: Saved a byte thanks to G B.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~15~~ 14 bytes
```
“RPS”ṗẆ;"f$$Ðḟ
```
[Try it online!](https://tio.run/##AUIAvf9qZWxsef//4oCcUlBT4oCd4bmX4bqGOyJmJCTDkOG4n/87IsOH4oKsWeKCrGrigb7CtsK2//9yYW5nZSgxLCAxMCk "Jelly – Try It Online")
### How it works
```
“RPS”ṗẆ;"f$$Ðḟ  Main link. Argument: n
“RPS”ṗ          Cartesian power; yield all strings of length n over this alphabet.
            Ðḟ  Filterfalse; keep only strings for which the quicklink to the left 
                returns a falsy result.
           $      Monadic chain. Argument: s (string)
      Ẇ             Window; yield the array A of all substrings of s.
          $         Monadic chain. Argument: A
       ;"             Concatenate all strings in A with themselves.
         f            Filter; yield all results that belong to A as well.
```
[Answer]
## [Retina](https://github.com/m-ender/retina), 28 bytes
```
+%1`1
R$'¶$`P$'¶$`S
A`(.+)\1
```
[Try it online!](https://tio.run/##K0otycxL/P9fW9UwwZArSEX90DaVhAAIFczlmKChp60ZY/j/vyEQAAA "Retina – Try It Online")
Takes input [in unary](http://meta.codegolf.stackexchange.com/questions/5343/can-numeric-input-output-be-in-unary).
### Explanation
```
+%1`1
R$'¶$`P$'¶$`S
```
This generates *all* strings made up of `RPS` of length `n`. The way we do this is that we repeatedly replace the first `1` in each line. Let's think about the line as `<1>`, where `<` is everything in front of the match and `>` is everything after the match (they're `$`` and `$'` respectively in regex substitution syntax, but those look less intuitive). We replace the `1` with `R>¶<P>¶<S`, where `¶` are linefeeds. So the full result of this substitution is actually `<R>¶<P>¶<S>`, which is three copies of the line, with the `1` replace with `R`, `P`, `S`, respectively, in each of the three copies. This process stops once all `1`s have substituted.
```
A`(.+)\1
```
Finally, we simply discard all lines that contain a repetition.
[Answer]
# Mathematica, 61 bytes
```
""<>#&/@{"R","P","S"}~Tuples~#~DeleteCases~{___,x__,x__,___}&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n6Zgq/BfScnGTllN36FaKUhJRykAiIOVautCSgtyUovrlOtcUnNSS1KdE4uBvOr4@HidCigGsmvV/gcUZeaVKOg7pOk7BCXmpac6GBr8BwA "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# [Husk](https://github.com/barbuz/Husk), ~~15~~ 14 bytes
*-1 byte thanks to Zgarb!*
```
fȯεfoE½QΠR"RPS
```
[Try it online!](https://tio.run/##yygtzv7/P@3E@nNb0/JdD@0NPLcgSCkoIPj///8mAA "Husk – Try It Online")
Builds all possible sequences of the correct length and keeps only the ones whose all substrings (except the empty one) are composed by two different halves.
Damn, I really wanted to beat Jelly here.
[Answer]
# Java 8, ~~285~~ 277 bytes
```
import java.util.*;Set r=new HashSet();n->p("",((1<<3*n)+"").replaceAll(".","PRS"),n)void p(String p,String s,int n){int l=s.length(),i=0;if(l<1&&(s=p.substring(0,n)).equals(s.replaceAll("(.*)\\1","")))r.add(s);for(;i<l;p(p+s.charAt(i),s.substring(0,i)+s.substring(++i,l),n));}
```
Although Java is almost always verbose, in this case it's definitely not the right language for a challenge like this. Generating permutations with substrings is bad for performance and inefficient.
Can definitely be golfed some more, though.
-8 bytes thanks to *@Jakob*.
**Explanation:**
[Try it here.](https://tio.run/##bVGxbsIwEN3zFScP6I4EA2IMqcTWpQiVsXQwiQFTx3Fthwohvp06kKFIXXx@T7p3794dxUmMGivNsfq6qdo2LsAxcrwNSvNhDgDjMaxEpJsdhIOE7TnIUdm0JiSlFt7Dm1DmkgAoE6TbiVLCsoMAp0ZVUGLkwVAeqWsSnyUYKOBmRi8WGcsQp/P5bGgoZYy4k1ZHhYXWyDjL2Op9zSgzlPRGlk0A@7@Z@zSL6@CU2YPN@o/PHvMvXdGF51qafTggZaqY5GqHej4dDNAXlvt26@9NOIkjicvvVmiP/skV8iFtNtPojRGR46Kq0FO@axzmaq5zizb1vDwItwioKPNPsorSv0Saqkx3@1F@TdYygCuM/IFX4Q8RIeU3ANtutSrBBxFiuW9Zx8T7RT8@QdAj7u4OUMdsO4kO4D10gJobXuKsR@uzD7LmTRu4jQpBG6y56@9zvf0C) (Performance is too bad for test cases above 3, but it does work locally..)
```
import java.util.*;   // Required import for Set and HashSet
Set r=new HashSet();  // Result-Set on class-level
n->                   // Method with integer parameter and no return-type
  p("",((1<<3*n)+"").replaceAll(".","PRS"),n)
                      //  Get all permutations and save them in the Set
                      // End of method (implicit / single-line return-statement)
void p(String p,String s,int n){
                      // Separated method with 2 String & int parameters and no return-type
  int l=s.length(),   //  The length of the second input-String
      i=0;            //  Index-integer, starting at 0
  if(l<1              //  If the length is 0,
     &&(s=p.substring(0,n)).equals(s.replaceAll("(.*)\\1","")))
                      //  and it doesn't contain a repeated part:
    r.add(s);         //   Add it to the result-Set
  for(;i<l;           //  Loop (2) from 0 to `l`
    p(                //   Recursive-call with:
      p+s.charAt(i),  //    Prefix-input + the character of the second input at index `i`
      s.substring(0,i)+s.substring(++i,l),
                      //    and the second input except for this character
      n)              //    and `n`
  );                  //  End of loop (2)
}                     // End of separated method
```
[Answer]
# [Python 3](https://docs.python.org/3/), ~~97~~ 96 bytes
```
f=lambda n:{c+s for c in'RPS'*n for s in f(n-1)or{''}if all(k-s.find(c+s[:k])for k in range(n))}
```
Returns a set of strings.
[Try it online!](https://tio.run/##RYuxDoIwFEVn/Yq3tcViQhxMSPgHo6M6VNpqA9ySlsUQvr1SHdzuOTl3fE8vj0NKtunV8NCKUM/tLpL1gVpyYOfThRX4clyZLEdZCR9mxhZnSfU978q4tw6ar8dr3d1FjrscB4Wn4RBiSdnh7ypJR1FvN2NwmDgkFdGHyWhucy4pmpEaYjcwSQb6t1cS6QM "Python 3 – Try It Online")
[Answer]
# [Julia 0.6](http://julialang.org/), 65 bytes
```
!n=n>0?["$c"s for s=!~-n,c="RPS"if~ismatch(r"(.+)\1","$c"s)]:[""]
```
[Try it online!](https://tio.run/##VYuxDoIwGAZneIq/XxzaWA1dHEiKr2B0BAZSJZbAj2lxM7x6jU46Xu5ueI6@O6Qk2HJVHGtsHCL1c6Boxbpj7SzOpwt8v/o4dYu7ywC536rGQH9j1ZY10KbPw@SZTGmKPGN6VfQInpeR82yYPUvBmtAw1J8CfvHG1/QG "Julia 0.6 – Try It Online")
[Answer]
# [Perl 5](https://www.perl.org/), 37 bytes
```
sub r{grep!/(.+)\1/,glob"{R,S,P}"x<>}
```
[Try it online!](https://tio.run/##K0gtyjH9/7@4NEmhqDq9KLVAUV9DT1szxlBfJz0nP0mpOkgnWCegVqnCxq72f3FipUJafpFC0X@Tf/kFJZn5ecX/dX1N9QwMDQA "Perl 5 – Try It Online")
Function returns an array of the square free strings.
**Explained:**
The `glob` generates all combinations of R, S, & P with length equal to the input. The `grep` statement filters out the ones that are not square free.
[Answer]
# [R](https://www.r-project.org/), 97 bytes
```
cat((x=unique(combn(rep(c('p','r','s'),n),n<-scan(),paste,collapse='')))[!grepl("(.+)\\1",x,,T)])
```
[Try it online!](https://tio.run/##DcsxCoQwEEbhs6zN/IOjYGGnt7BbLbJDWBZijImB3D4beF/5Yq1qHqCs2f/ubKHX@fGINkBBgYRik4jFt5YhqfFgCSY9VvRyzoRkVyJmfr@@bXPoMPa871MnRWTjg@tc/w "R – Try It Online")
`combn(rep(c('p','r','s'),n),n,paste,collapse='')` computes all `n`-character strings with `p`, `r`, `s`, but it unfortunately duplicates many(\*), so we uniquify it, and take those that match the regex `(.+)\1`, using perl-style matching, then we print out the resultant list.
(\*) technically, it generates all combinations of the `3n` letters in `p,r,s` repeated 3 times taken `n` at a time, then applies `paste(..., collapse='')` to each combination rather than computing the `3^n` strings directly, but this is golfier than an `expand.grid` (the true Cartesian product).
[Answer]
## JavaScript (Firefox 30-57), 69 bytes
```
f=n=>n?[for(x of f(n-1))for(y of'RPS')if(!/(.+)\1/.test(y+=x))y]:['']
```
Since all substrings of square-free words are also square-free the check can be done recursively.
[Answer]
# [Haskell](https://www.haskell.org/), ~~101~~ 98 bytes
```
f n=[x:r|x:r<-mapM(\_->"RPS")[1..n],[x]#r]
h#t@(x:r)=h/=take(length h)t&&(h++[x])#r&&[x]#r
h#t=1<3
```
[Try it online!](https://tio.run/##y0gszk7Nyfn/P00hzza6wqqoBohtdHMTC3w1YuJ17ZSCAoKVNKMN9fTyYnWiK2KVi2K5MpRLHDSAyjRtM/RtSxKzUzVyUvPSSzIUMjRL1NQ0MrS1gQo1lYvU1MAaQOptDW2M/@cmZuYp2CoUFGXmlSioKKQpmPwHAA "Haskell – Try It Online")
[Answer]
# Julia, 88
```
f(n)=[filter(A->!ismatch.(r"(.+)\1",join(A)),Iterators.product(repeated("RPS",n)...))...]
```
Nothing fancy.
[Answer]
## JavaScript (ES7), 93 bytes
```
n=>[...Array(3**n)].map(g=(d=n,i)=>d?'RPS'[i%3]+g(d-1,i/3|0):'').filter(s=>!/(.+)\1/.test(s))
```
Converts all the integers from 0 to 3ⁿ to (reversed padded) base 3 using `RPS` as digits and filters them for square-free words.
[Answer]
## C# / LINQ, 169
```
Enumerable.Range(0,(int)Math.Pow(3,n)).Select(i=>string.Concat(Enumerable.Range(1,n).Select(p=>"PRS"[(i/(int)Math.Pow(3,n-p))%3]))).Where(s=>!Regex.IsMatch(s,@"(.+)\1"))
```
There has to be a better way to do this :)
[Answer]
## F#, 143
```
let f n=[1..n]|>List.fold(fun l _->List.collect(fun s->["R";"P";"S";]|>List.map((+)s))l)[""]|>Seq.filter(fun x->not(Regex.IsMatch(x,"(.+)\1")))
```
[Answer]
# k, 56 bytes
```
f:{$[x;(,/"RPS",/:\:f x-1){x@&~~/'(2,y)#/:x}/1_!x;,""]}
```
The lack of native regex puts k well behind the curve for once. I went with a recursive solution, since the characters to implement it were saved by a simpler squarefree check.
```
$[ test ; if-true ; if-false ]
```
is k's ternary operator, here we do interesting stuff for non-zero length, and return a single empty string if asked for zero-length words.
```
(,/"RPS",/:\:f x-1)
```
takes the cartesian product of "RPS" and all n-1 length squarefree words. ,/:\: joins each element of the right to the left, giving a length 3 array of length n arrays. ,/ flattens this into a length 3n array.
```
{x@&~~/'(2,y)#/:x}
```
takes the first n letters of each string and compares it to the second n, then reduces the array to only where they do not match. Because we know the previous result is square-free, only the substrings starting at the first character need matching - simplifying the check here was worth the characters spent implementing recursion. Finally,
```
/1_!x
```
applies the lambda to the initial result set to its left, iterating over each substring length from 1 to (word length)-1. !x generates a list from 0 to x-1, then 1\_ removes the first element (since 0-length substrings will always match)
Sacrificing a few characters we can use .z.s to self-reference rather than rely on the function name, and instead of checking substrings up to length n-1 only check floor(n/2) for performance. It finds all length 49 words (of which there are 5207706) in about 120 seconds on a 7700k, above that I run into the 4GB limit of free 32-bit k.
```
{$[x;(,/"RPS",/:\:.z.s x-1){x@&~~/'(2,y)#/:x}/1+!_x%2;,""]}
```
[Answer]
# [Python 2](https://docs.python.org/2/), 99 bytes
```
import re
f=lambda n:n and[c+s for c in'RPS'for s in f(n-1)if not re.search(r'(.+)(\1)',c+s)]or['']
```
[Try it online!](https://tio.run/##FcsxDoMwDADAnVd4cywoElWnSvwB0ZEypIGISMWOnCx9fRrGGy7@8iF8LyWcUTSD7o0fv/b8bBb4yWB5W1ybwIuCg8A4Ty@8kCrAG74NFDywXLVPu1V3GEXTt2TeA2FXM62iC@JaogbONT2o/AE "Python 2 – Try It Online")
]