Strings without twin letters

Question

Consider an arbitrary set of letters \$L\$. It may either be \$\{A, B, C\}\$, \$\{M, N, O, P\}\$, \$\{N, F, K, D\}\$, or even contain all the 26 letters. Given an instance of \$L\$ and a positive integer \$n\$, how many \$n\$-letter words can we build from \$L\$ such that no adjacent letters are the same (so for example ABBC is not allowed from \$\{A, B, C\}\$)?

This can be solved using combinatorics, but what those words are?

Input

A non-empty string \$L\$ and a positive integer \$n > 0\$.

You choose to accept only lowercase letters, only uppercase letters, or both, as input for \$L\$.

Also, note that a valid \$L\$ won't contain any duplicate letters, so ABCA is an invalid input and should not be handled.

Output

A list of all strings of length \$n\$ that can be formed from \$L\$ such that no adjacent letters are the same.

You can repeat letters, so a valid solution for \$L=\{A, B, C\}\$ and \$n=3\$ is ABA, ABC, ACB, ACA, BAC, BCA, BAB, BCB, CAB, CBA, CAC and CBC.

Also note that \$|L| < n\$ is possible, so a valid solution for \$L=\{A, B\}\$ and \$n=3\$ is only ABA and BAB.

And yes, \$|L| > n\$ is also possible, so a valid solution for \$L=\{A, B, C, D\}\$ and \$n=3\$ is ABA, ABC, ABD, ACA, ACB, ACD, ADA, ADB, ADC, BAB, BAC, BAD, BCA, BCB, BCD, BDA, BDB, BDC, CAB, CAC, CAD, CBA, CBC, CBD, CDA, CDB, CDC, DAB, DAC, DAD, DBA, DBC, DBD, DCA, DCB and DCD.

The output doesn't have to be in a particular order.

Test samples

ABC, 3 -> ABA, ABC, ACA, ACB, BAB, BAC, BCA, BCB, CAB, CAC, CBA, CBC
AB, 3 -> ABA, BAB
ABCD, 3 -> ABA, ABC, ABD, ACA, ACB, ACD, ADA, ADB, ADC, BAB, BAC, BAD, BCA, BCB, BCD, BDA, BDB, BDC, CAB, CAC, CAD, CBA, CBC, CBD, CDA, CDB, CDC, DAB, DAC, DAD, DBA, DBC, DBD, DCA, DCB, DCD
OKAY, 2 -> OK, OA, OY, KO, KA, KY, AO, AK, AY, YO, YK, YA
CODEGLF, 3 -> COC, COD, COE, COG, COL, COF, CDC, CDO, CDE, CDG, CDL, CDF, CEC, CEO, CED, CEG, CEL, CEF, CGC, CGO, CGD, CGE, CGL, CGF, CLC, CLO, CLD, CLE, CLG, CLF, CFC, CFO, CFD, CFE, CFG, CFL, OCO, OCD, OCE, OCG, OCL, OCF, ODC, ODO, ODE, ODG, ODL, ODF, OEC, OEO, OED, OEG, OEL, OEF, OGC, OGO, OGD, OGE, OGL, OGF, OLC, OLO, OLD, OLE, OLG, OLF, OFC, OFO, OFD, OFE, OFG, OFL, DCO, DCD, DCE, DCG, DCL, DCF, DOC, DOD, DOE, DOG, DOL, DOF, DEC, DEO, DED, DEG, DEL, DEF, DGC, DGO, DGD, DGE, DGL, DGF, DLC, DLO, DLD, DLE, DLG, DLF, DFC, DFO, DFD, DFE, DFG, DFL, ECO, ECD, ECE, ECG, ECL, ECF, EOC, EOD, EOE, EOG, EOL, EOF, EDC, EDO, EDE, EDG, EDL, EDF, EGC, EGO, EGD, EGE, EGL, EGF, ELC, ELO, ELD, ELE, ELG, ELF, EFC, EFO, EFD, EFE, EFG, EFL, GCO, GCD, GCE, GCG, GCL, GCF, GOC, GOD, GOE, GOG, GOL, GOF, GDC, GDO, GDE, GDG, GDL, GDF, GEC, GEO, GED, GEG, GEL, GEF, GLC, GLO, GLD, GLE, GLG, GLF, GFC, GFO, GFD, GFE, GFG, GFL, LCO, LCD, LCE, LCG, LCL, LCF, LOC, LOD, LOE, LOG, LOL, LOF, LDC, LDO, LDE, LDG, LDL, LDF, LEC, LEO, LED, LEG, LEL, LEF, LGC, LGO, LGD, LGE, LGL, LGF, LFC, LFO, LFD, LFE, LFG, LFL, FCO, FCD, FCE, FCG, FCL, FCF, FOC, FOD, FOE, FOG, FOL, FOF, FDC, FDO, FDE, FDG, FDL, FDF, FEC, FEO, FED, FEG, FEL, FEF, FGC, FGO, FGD, FGE, FGL, FGF, FLC, FLO, FLD, FLE, FLG, FLF
NFKD, 4 -> NFNF, NFNK, NFND, NFKN, NFKF, NFKD, NFDN, NFDF, NFDK, NKNF, NKNK, NKND, NKFN, NKFK, NKFD, NKDN, NKDF, NKDK, NDNF, NDNK, NDND, NDFN, NDFK, NDFD, NDKN, NDKF, NDKD, FNFN, FNFK, FNFD, FNKN, FNKF, FNKD, FNDN, FNDF, FNDK, FKNF, FKNK, FKND, FKFN, FKFK, FKFD, FKDN, FKDF, FKDK, FDNF, FDNK, FDND, FDFN, FDFK, FDFD, FDKN, FDKF, FDKD, KNFN, KNFK, KNFD, KNKN, KNKF, KNKD, KNDN, KNDF, KNDK, KFNF, KFNK, KFND, KFKN, KFKF, KFKD, KFDN, KFDF, KFDK, KDNF, KDNK, KDND, KDFN, KDFK, KDFD, KDKN, KDKF, KDKD, DNFN, DNFK, DNFD, DNKN, DNKF, DNKD, DNDN, DNDF, DNDK, DFNF, DFNK, DFND, DFKN, DFKF, DFKD, DFDN, DFDF, DFDK, DKNF, DKNK, DKND, DKFN, DKFK, DKFD, DKDN, DKDF, DKDK
JOHN, 5 -> JOJOJ, JOJOH, JOJON, JOJHJ, JOJHO, JOJHN, JOJNJ, JOJNO, JOJNH, JOHJO, JOHJH, JOHJN, JOHOJ, JOHOH, JOHON, JOHNJ, JOHNO, JOHNH, JONJO, JONJH, JONJN, JONOJ, JONOH, JONON, JONHJ, JONHO, JONHN, JHJOJ, JHJOH, JHJON, JHJHJ, JHJHO, JHJHN, JHJNJ, JHJNO, JHJNH, JHOJO, JHOJH, JHOJN, JHOHJ, JHOHO, JHOHN, JHONJ, JHONO, JHONH, JHNJO, JHNJH, JHNJN, JHNOJ, JHNOH, JHNON, JHNHJ, JHNHO, JHNHN, JNJOJ, JNJOH, JNJON, JNJHJ, JNJHO, JNJHN, JNJNJ, JNJNO, JNJNH, JNOJO, JNOJH, JNOJN, JNOHJ, JNOHO, JNOHN, JNONJ, JNONO, JNONH, JNHJO, JNHJH, JNHJN, JNHOJ, JNHOH, JNHON, JNHNJ, JNHNO, JNHNH, OJOJO, OJOJH, OJOJN, OJOHJ, OJOHO, OJOHN, OJONJ, OJONO, OJONH, OJHJO, OJHJH, OJHJN, OJHOJ, OJHOH, OJHON, OJHNJ, OJHNO, OJHNH, OJNJO, OJNJH, OJNJN, OJNOJ, OJNOH, OJNON, OJNHJ, OJNHO, OJNHN, OHJOJ, OHJOH, OHJON, OHJHJ, OHJHO, OHJHN, OHJNJ, OHJNO, OHJNH, OHOJO, OHOJH, OHOJN, OHOHJ, OHOHO, OHOHN, OHONJ, OHONO, OHONH, OHNJO, OHNJH, OHNJN, OHNOJ, OHNOH, OHNON, OHNHJ, OHNHO, OHNHN, ONJOJ, ONJOH, ONJON, ONJHJ, ONJHO, ONJHN, ONJNJ, ONJNO, ONJNH, ONOJO, ONOJH, ONOJN, ONOHJ, ONOHO, ONOHN, ONONJ, ONONO, ONONH, ONHJO, ONHJH, ONHJN, ONHOJ, ONHOH, ONHON, ONHNJ, ONHNO, ONHNH, HJOJO, HJOJH, HJOJN, HJOHJ, HJOHO, HJOHN, HJONJ, HJONO, HJONH, HJHJO, HJHJH, HJHJN, HJHOJ, HJHOH, HJHON, HJHNJ, HJHNO, HJHNH, HJNJO, HJNJH, HJNJN, HJNOJ, HJNOH, HJNON, HJNHJ, HJNHO, HJNHN, HOJOJ, HOJOH, HOJON, HOJHJ, HOJHO, HOJHN, HOJNJ, HOJNO, HOJNH, HOHJO, HOHJH, HOHJN, HOHOJ, HOHOH, HOHON, HOHNJ, HOHNO, HOHNH, HONJO, HONJH, HONJN, HONOJ, HONOH, HONON, HONHJ, HONHO, HONHN, HNJOJ, HNJOH, HNJON, HNJHJ, HNJHO, HNJHN, HNJNJ, HNJNO, HNJNH, HNOJO, HNOJH, HNOJN, HNOHJ, HNOHO, HNOHN, HNONJ, HNONO, HNONH, HNHJO, HNHJH, HNHJN, HNHOJ, HNHOH, HNHON, HNHNJ, HNHNO, HNHNH, NJOJO, NJOJH, NJOJN, NJOHJ, NJOHO, NJOHN, NJONJ, NJONO, NJONH, NJHJO, NJHJH, NJHJN, NJHOJ, NJHOH, NJHON, NJHNJ, NJHNO, NJHNH, NJNJO, NJNJH, NJNJN, NJNOJ, NJNOH, NJNON, NJNHJ, NJNHO, NJNHN, NOJOJ, NOJOH, NOJON, NOJHJ, NOJHO, NOJHN, NOJNJ, NOJNO, NOJNH, NOHJO, NOHJH, NOHJN, NOHOJ, NOHOH, NOHON, NOHNJ, NOHNO, NOHNH, NONJO, NONJH, NONJN, NONOJ, NONOH, NONON, NONHJ, NONHO, NONHN, NHJOJ, NHJOH, NHJON, NHJHJ, NHJHO, NHJHN, NHJNJ, NHJNO, NHJNH, NHOJO, NHOJH, NHOJN, NHOHJ, NHOHO, NHOHN, NHONJ, NHONO, NHONH, NHNJO, NHNJH, NHNJN, NHNOJ, NHNOH, NHNON, NHNHJ, NHNHO, NHNHN

Answer 1

Husk, 4 bytes

fΛ≠π

Try it online!

Short and straightforward solution, the MVP here is Λ, thanks to its overload that can take a binary function and use it to check pairs of adjacent elements.

Explanation

fΛ≠π
   π    Cartesian power of L and n (generates all possible words)
f       Filter those
 Λ        for which all adjacent letters
  ≠           are different

Answer 2

Google Sheets, 88 bytes

=let(L,torow(A:A,1),reduce(,sequence(B1),lambda(a,_,sort(tocol(if(left(a)=L,,L&a),1)))))

Put letters \$L\$ in column A:A, the target length \$n\$ in cell B1, and the formula in cell D1.

The formula generates all possible strings of length \$n\$ from the alphabet \$L\$ with repeats, and while building a string, refuses it if its first character is the same as the one currently being prepended.

Ungolfed:

=let( 
  letters, torow(A1:A, 1), 
  n, B1, 
  blank, iferror(ø), 
  reduce(blank, sequence(n), lambda(acc, curr, 
    sort( 
      tocol(if(left(acc) = letters, blank, letters & acc), 1) 
    ) 
  )) 
)

acc is a vertical array, and letters is a horizontal array. The sort() function is array enabled, which means that the inner comparison and concatenation produce acc × letters results each round. tocol() then flattens the result, weeding out blanks generated by the if().

Hat tip to JvdV for the left(acc) = letters pattern.

Answer 3

Ruby, 42 bytes

->l,n{(?A*n..?Z*n).grep_v /[^#{l}]|(.)\1/}

Attempt This Online!

Input in uppercase. Start with a list of all \$n\$-letter strings, then remove those containing letters not in \$L\$ or double letters.

Answer 4

Haskell, 49 47 bytes

l#1=pure<$>l
l#n=[c:a:r|a:r<-l#(n-1),c<-l,a/=c]

Try it online!

Edit: Thanks to @xnor for taking off two bytes! I didn't know you could remove the parentheses in that context

Answer 5

JavaScript (ES10), 54 bytes

Expects (a)(n), where a is an array of characters. Returns an array of strings.

a=>g=(n,o,p)=>n--?a.flatMap(c=>p!=c?g(n,[o]+c,c):[]):o

Try it online!

Commented

a =>             // outer function taking a[]
g = (            // inner recursive function taking:
  n,             //   n = expected length
  o,             //   o = output string, initially undefined
  p              //   p = previous character in the output,
) =>             //       initially undefined
n-- ?            // if we don't have enough characters:
  a.flatMap(c => //   for each character c in a[]:
    p != c ?     //     if the previous char. is not equal to c:
      g(         //       do a recursive call:
        n,       //         pass the updated value of n
        [o] + c, //         coerce o to a string and append c to o
        c        //         set p = c
      )          //       end of recursive call
    :            //     else:
      []         //       abort
  )              //   end of flatMap()
:                // else:
  o              //   return the output

Answer 6

Vyxal, 5 bytes

↔'ÞǓ⁼

Try it Online!

generates all combinations of length n using the characters in the input string, then filters by those which are equal to the string with all adjacent duplicates removed.

Answer 7

C (gcc), 168 160 119 114 bytes

-8 Thanks to @corvus_192 for pointing out newline separation between values was allowed, and a massive -41 thanks to @tsh, a further -5 thanks to @ceilingcat

char*l,*c;f(n,i){n?(c[n-1]=l[i])&&(l[i]-c[n]&&f(n-1,0),f(n,i+1)):puts(c);}g(e,n)char*e;{c=calloc(n,2);l=e;f(n,0);}

Try it online!

Prints the newline separated output to STDOUT.

Answer 8

K (ngn/k), 22 21 18 bytes:

-1 byte due to @ovs. -3 bytes thanks to @ngn.

{(|/'=':')_+!y#,x}

Try it online

Answer 9

MATL, 9 bytes

Z^t!dXAY)

Try it online!

Explanation

Z^    % Implicit inputs. Cartesian product. Gives a character matrix where 
      % each row is a Cartesian tuple (*)
t!    % Duplicate, transpose
d     % Consecutive differences, computed along vertical dimension
XA    % Vertical-all: gives true for columns that only contain nonzeros
Y)    % Use as logical index into the rows of (*). Implicit display

Answer 10

R, 70 bytes

\(L,n,x=combn(rep(L,n+1),n))unique(x[,apply(x,2,\(a)all(diff(a)))],,2)

Attempt This Online!

Uses a rather loose definition of string - a vector of character codes. Outputs a matrix with unique words in columns.

Answer 11

Python 3, 74 67 64 bytes

-7 thanks to @Albert.Lang, -3 thanks to @Mukundan314

f=lambda l,n:[""][n:]or[c+w for w in f(l,n-1)for c in{*l}-{*w[:1]}]

Try it online!

Answer 12

Perl 5 -nl, 30 bytes

map!/(.)\1/&&say,glob"{$_}"x<>

Try it online!

Answer 13

APL+WIN, 42 bytes

Prompts for string followed by n:

n←m←⎕⋄⍎∊(⎕-1)⍴⊂'n←n∘.,m⋄'⋄(0=+/¨2=/¨,n)/,n

Try it online! Thanks to Dyalog Classic

Answer 14

Uiua ^SBCS, 23 21 20 bytes

▽≡(/×≡/≠◫2).⊏☇1⇡▽:⧻,

Try it!

▽≡(/×≡/≠◫2).⊏☇1⇡▽:⧻,
                  ⧻,  # length of the set, call it L
               ⇡▽:    # permutations w/ repetition of [0..n) with length L
             ☇1       # change to rank 2
            ⊏         # index into set
           .          # duplicate
 ≡(       )           # map each row
        ◫2            # windows of length 2
     ≡/≠              # reduce each row by inequality
   /×                 # product
▽                     # keep

Answer 15

Jelly, 6 bytes

ṗnƝẠ$Ƈ

A dyadic Link that accepts the alphabet on the left and the word length on the right and yields a list of valid words.

Try it online!

How?

ṗnƝẠ$Ƈ - Link: Alphabet, WordLength
ṗ      - {Alphabet} Cartesian power {WordLength} -> all words
     Ƈ - keep those for which:
    $  -   last two links as a monad - f(Word):
  Ɲ    -     for neighbouring pairs:
 n     -       not equal?
   Ạ   -     all?

...if one didn't need to handle an alphabet of length one, then five bytes would do - ṗnƝÐṀ (keep those words which are maximal under neighbourwise not-equal).

Answer 16

Excel ms365, ⁸⁵ 84 bytes

• -1 thanks to doubleunary's tip to apply LEFT() instead of RIGHT().

Assuming:

• \$L\$ - Given input in the first row 1:1 starting from A1 onwards;
• \$n\$ - Given integer in A2.

Formula, thus output, in A4 spilled down:

=LET(L,TOROW(1:1,1),REDUCE("",TAKE(L,,A2),LAMBDA(x,n,TOCOL(IFS(LEFT(x)<>L,L&x),3))))

Answer 17

Charcoal, 20 bytes

⊞υωＦＮ≔ΣＥηＥΦυ⌕μκ⁺κμυυ

Attempt This Online! Link is to verbose version of code. Explanation:

⊞υω

Start with the empty string.

ＦＮ

Loop n times.

≔ΣＥηＥΦυ⌕μκ⁺κμυ

For each letter of L, prefix it to each string so far that does not begin with that letter, then concatenate all of the results together. (Prefixing each letter of L that the string does not begin with fails when there are no strings in the list.)

υ

Output the final list.

Answer 18

05AB1E, 5 bytes

ãʒüÊP

Inputs in the order \$n,L\$.

Try it online or verify all test cases.

Or alternatively:

ãʒDÔQ

Try it online or verify all test cases.

Explanation:

ã      # Cartesian product on both (implicit) inputs to get all n-sized strings using
       # characters from L
 ʒ     # Filter it by:
  ü    #  Map over each overlapping pair:
   Ê   #   Check that they're NOT equal
    P  #  Check that all of them are truthy
       # (after which the filtered list is output implicitly)

  D    #  Duplicate the current string
   Ô   #  Connected uniquify it, collapsing all equal adjacent characters
    Q  #  Check if the connected uniquified string is still the same

Answer 19

Retina, 41 bytes

"$&"+%Lw$`,.*(.)
$`$1$&$'
\d|,.+

A`(.)\1

Try it online! Link includes test cases. Takes comma-separated input. Explanation:

"$&"+`

Repeat n times...

%Lw$`,.*(.)
$`$1$&$'

Replicate each line for each letter of L but inserting a copy of the letter before the comma.

\d|,.+

Remove the copies of n and L.

A`(.)\1

Remove all lines with duplicate adjacent letters.

Answer 20

Perl 5 + -lF -M5.10.0, 40 bytes

!/[^@F]|(.)\1/&&say for A x($;=<>)..Z x$

Try it online!

Answer 21

Brachylog, 13 10 bytes

-3 bytes inspired by a suggestion from Fatalize

gʰj₎∋ᵐ.ẹ~ḅ

Generator solution. Takes input as a list containing a string and an integer. Returns solutions as lists of single-character strings. Try it online!

Explanation

This feels like it should be shorter. Part of the problem is that Brachylog starts getting verbose when you have to deal with anything past one input and one output.

gʰj₎∋ᵐ.ẹ~ḅ
             Input: list containing string and number
gʰ           Wrap the first element in a singleton list
  j₎         Concatenate that list with itself (second element) times
    ∋ᵐ       Select one character from each of those strings
      .      This will be the output
       ẹ     Convert each character to a list of its characters (i.e.
              wrap it in a singleton list)
        ~ḅ   Assert that this is the same as the result of partitioning
              some list into runs of identical elements
             ... and that that list is the output

To help clarify the ending bit: The predicate ẹ converts each string in its input into a list of its characters. The predicate ḅ finds all runs of consecutive identical values in its input. The .ẹ~ḅ structure applies ẹ to the list, then unapplies ḅ to that result, then requires that result to be the same list we started with. This is the same as saying that ẹ and ḅ must give the same result when applied to the list. So:

• Given the list ["a","b","b"], ẹ outputs [["a"],["b"],["b"]] and ḅ outputs [["a"],["b","b"]]. Those don't match, so the predicate fails.
• Given the list ["a","b","a"], ẹ outputs [["a"],["b"],["a"]] and ḅ outputs [["a"],["b"],["a"]]. Those do match, so the predicate succeeds.

Answer 22

Nekomata, 4 bytes

ŧĉᵐz

Attempt This Online!

ŧĉᵐz    Take input L and n
ŧ       Find an n-tuple of elements of L
 ĉ      Split into runs of equal elements
  ᵐ     For each run:
   z        Check that it contains exactly one element, and take that element

Answer 23

R, 65 64 bytes

\(L,n,A=expand.grid(rep(list(L),n)))A[!rowSums(A[,-n]==A[,-1]),]

Assuming L is a vector of characters.

-1 byte thanks to @pajonk!

Try it online here!

Answer 24

Scala 3, 128 bytes

A Port of @Arnold Palmer's Python answer in Scala.

---

Golfed version. Attempt This Online!

type Q=String;
def g(l:Q,n:Int,c:Q=""):Seq[Q]={if(n==0)Seq("");else{for{a<-l if a.toString!=c;b<-g(l,n-1,a.toString)}yield a+b}}

Ungolfed version. Attempt This Online!

def generateCombinations(l: String, n: Int, c: String = ""): Seq[String] = {
    if (n == 0) Seq("")
    else {
      for {
        a <- l
        if a.toString != c
        b <- generateCombinations(l, n - 1, a.toString)
      } yield a + b
    }
  }

Answer 25

jq, 67 bytes

def f($n):combinations($n)|join("")|select(test("(.)\\1";"x")|not);

Try it online!

Defines a function f which takes \$L\$ as input and \$n\$ as an argument.