# Input

A single positive integer $$\ 10 \geq n \geq 2\$$

# Output

A list of strings, each of length $$\2n\$$, satisfying the following properties.

• Each string will contain each of the first $$\n\$$ lowercase letters of the alphabet exactly twice.
• No letter can occur twice consecutively. That is abbcac is not allowed.
• No two strings that are equivalent can be in the list. Equivalence will be defined below.
• All non-equivalent strings satisfying the rules must be in the list.

# Equivalence

We say that two strings of the same length are equivalent if there is a bijection from the letters in the first string to the letters in the second string which makes them equal. For example, abcbca and bcacab are equivalent.

# Examples

• $$\n = 2\$$: abab
• $$\n = 3\$$: abacbc abcabc abcacb abcbac abcbca

The length of these lists is A278990.

• n=2: ab => n=2: abab
– l4m2
Commented Aug 13, 2023 at 5:15
• Isn't abacbc equivalent to acabcb? Commented Aug 13, 2023 at 5:35
• @CommandMaster Oops. That was a copy and paste error. Thx
– Simd
Commented Aug 13, 2023 at 5:39
• Is lowercase mandatory, or may the result also be uppercase (e.g. ABAB)? Commented Aug 14, 2023 at 11:46
• @KevinCruijssen Given the number of answers already, I would like to keep lowercase.
– Simd
Commented Aug 14, 2023 at 11:48

# Charcoal, 45 bytes

≔⪪…βＮ¹θ⊞υωＦ⁺θθ≔ΣＥυ⁺κΦθ∧⁻μΦ⮌κ¬π∧‹№κμ²⬤…βν№κξυυ


Attempt This Online! Link is to verbose version of code. Theoretically supports n up to 26. Explanation:

≔⪪…βＮ¹θ


Get the first n letters of the lowercase alphabet.

⊞υω


Ｆ⁺θθ


Loop 2n times.

≔ΣＥυ⁺κΦθ∧⁻μΦ⮌κ¬π∧‹№κμ²⬤…βν№κξυ


For each string so far, create strings with all of the first n lowercase letters appended to it, but exclude those that fail to satisfy the criteria.

υ


Output the final strings.

There are three criteria that are checked when considering candidate letters to append:

• The letter must not already be the last letter of the string
• The letter must not have already appeared twice
• All previous letters must already appear in the string
• Very nice simplification of the rules.
– Simd
Commented Aug 13, 2023 at 8:40

# JavaScript (ES6), 107 bytes

Returns a single space-separated string.

f=(n,s=' ',m=1,i=m,g=q=>i?f(n,"abcdefghij"[--i]+s,+q+m)+g:q)=>s[2*n]?/(.)(|.*\1.*)\1/.test(s)?'':s:g(m<n)


Try it online!

Or 106 bytes in Node.js.

### Method

We recursively build all non-equivalent strings of length $$\2n\$$ with $$\n\$$ distinct characters. The non-equivalence is enforced by using an upper bound $$\m\$$ which is initialized to $$\1\$$ and incremented as soon as the $$\m\$$-th character has been inserted and while we have $$\m.

The other criteria are tested at the end of the recursion with a regular expression which should not be matched by a valid string:

/(.)(|.*\1.*)\1/


### Commented

f = (                // f is a recursive function taking:
n,                 //   n = input
s = ' ',           //   s = current output string
m = 1,             //   m = upper character bound
i = m,             //   i = counter
g = q =>           //   g is a recursive function taking a flag q:
i ?              //     if i is not zero:
f(             //       1st recursive call to f:
n,           //         pass n unchanged
"abcdefghij" //         lookup string of letters
[--i]        //         decrement i and append the i-th letter
+ s,         //         followed by s
+q + m       //         increment m if q is set
)              //       end of recursive call
+ g          //       2nd recursive call to g with q zero'ish
:                //     else:
q              //       stop (at this point, we have q = [''])
) =>                 //
s[2 * n] ?         // if s has 2n + 1 characters:
/(.)(|.*\1.*)\1/ //   if there's any character in s immediately
.test(s) ?       //   followed by itself or appearing 3+ times:
''             //     s is invalid, so append nothing
:                //   else:
s              //     append s
:                  // else:
g(m < n)         //   initial call to g with q set if m < n


# Retina, 69 bytes

.+
*
Y\_l
^
<$'> />./+Lrv$(?(2)(\3.+))<(.+)?(\w)
$%$1$3<$2$%' <>  Try it online! Might work up to n=26. Explanation: .+ * Y\_l  Generate the first n lowercase letters. ^ <$'>


Make a duplicate set, and wrap the first set in < and >.

Lrv$(?(2)(\3.+))<(.+)?(\w)$%$1$3<$2$%'


For each string, make new strings by either a) moving the first character from the first set or b) moving a character from the second set that was moved from the first set but not in the immediately previous iteration.

/>./+


Repeat until the second set is empty for all strings.

<>



Remove the <> markers.

# Jelly,  18  15 bytes

Øaḣx2Œ!Q⁼Ɲ;QƊÐṂ


A monadic Link that accepts $$\n\$$ and yields a list of lists of characters.

Try it online!

### How?

Øaḣx2Œ!Q⁼Ɲ;QƊÐṂ - Link: n
Øa              - alphabet
ḣ             - head to index {n}
x2           - times two
Œ!         - all permutations
Q        - deduplicate
ÐṂ - keep those {P in those permutations} minimal under:
Ɲ      -   to neighbouring pairs {P}:
⁼       -     equal?
Q    -   deduplicate {P}
;     -   concatenate ...e.g. 'accbab' -> [0,1,0,0,0,'a','c','b']
(minimal entries would be [0,0,0,..,0,'a','b','c',...])


# JavaScript (Node.js), 127 bytes

f=(n,z=[],L)=>[...n?f(n-1,[c=(n+9).toString(36),...z],c+[L]):z+z?[]:[L],...z.flatMap(t=>t==L[0]?[]:f(n,z.filter(y=>y!=t),t+L))]


Try it online!

Its print version is 116 bytes

• Could you add an explanation? Base 36 is already confusing ;)
– Simd
Commented Aug 13, 2023 at 5:51
• @Simd To convert number into letter
– l4m2
Commented Aug 13, 2023 at 5:52

# Python3, 323 bytes:

def B(a,b):
d={}
for a,b in zip(a,b):
if b not in(T:=d.get(a,[])):d[a]={*T,b}
return d
def F(n):
r,q=[],[['abcdefghijklmnopqrstuvwxyz'[:n]*2,'']]
for s,k in q:
if''==s:
if all(any(len(K)>1for K in B(j,k).values())for j in r):r+=[k]
for i,a in enumerate(s):q+=[[s[:i]+s[i+1:],k+a]]*(k==''or a!=k[-1])
return r


Try it online!

• You can save 8 bytes by replacing ascii_lowercase and its import with the literal 'abcdefghijklmnopqrstuvwxyz' Commented Aug 13, 2023 at 23:43
• @yoniLavi Thank you, updated Commented Aug 13, 2023 at 23:48

# Nekomata, 18 bytes

r:,↕ũ∆Zç∫:ux=¿97+H


Attempt This Online!

r:,↕ũ∆Zç∫:ux=¿97+H
r:,↕ũ               Find a list of length 2n that contains each number from 0 to n exactly twice
r                       Range from 0 to input
:                      Duplicate
,                     Join
↕ũ                   Permutation
∆Zç∫           Check that no two adjacent values are equal
∆                  Delta
Z                 Check no values are 0
ç                Prepend 0
∫               Cumsum to get back to the original list
:ux=¿      Check that the list is in the standard order
:              Duplicate
u             Uniquify
x=           Check that the result is [0, 1, 2, ..., n]
¿          If so, get back to the original list
97+H  Convert to string
H      Convert from codepoints to string

• You might win the prize for the slowest code.
– Simd
Commented Aug 14, 2023 at 10:05

# Python 3.10, 204 bytes

from itertools import*
def f(n):z,F='abcdefghij'[:n],frozenset;q=F();return[x for x in permutations(z*2)if all(a!=b for a,b in pairwise(x))and q!=(q:=q|{F(F(I for I,c in enumerate(x)if c==d)for d in z)})]


Testable as f(n), outputs list of tuples. Each tuple contains "characters" (strings of length 1) and is thus equivalent to a string.

# Python 3.8 (pre-release), 205 bytes

itertools.pairwise was added in 3.10 and is not supported by TIO, so here's another version:

from itertools import*
def f(n):z,F='abcdefghij'[:n],frozenset;q=F();return[x for x in permutations(z*2)if all(a!=b for a,b in zip(x,x[1:]))and q!=(q:=q|{F(F(I for I,c in enumerate(x)if c==d)for d in z)})]


Try it online!

Works by simple bruteforce, will likely time out for $$\n \ge 6\$$.

• Welcome to Code Golf, and nice answer! Commented Aug 15, 2023 at 18:18

# 05AB1E, 17 (or 16†) bytes

L€DœÙʒDüÊ*ÙāQ}.bl


Output as a list of lists.

: Could be -1 byte removing the trailing l by outputting in uppercase.

Explanation:

L        # Push a list in the range [1, (implicit) input-integer]
€D      # Duplicate each value within the list
œ     # Get all permutations of this list
Ù    # Uniquify it
ʒ        # Filter this list of lists by:
D       #  Duplicate the current list
ü      #  For each overlapping pair:
Ê     #   Check that they are NOT equal
*    #  Multiply the values in the lists at the same positions
#  (removing the trailing item, but this doesn't matter)
Ù   #  Uniquify it
ā  #  Push a list in the range [1,length] (without popping)
Q #  Check whether the two lists are the same
}.b      # After the second filter: convert all integers to their 1-based alphabetic
# uppercase letters
l     # Convert those to lowercase
# (after which the result is output implicitly)

• You are not outputting strings.
– Simd
Commented Aug 14, 2023 at 12:01
• Strings are sequences of characters, so it's the same thing. Both are allowed by default: see this meta post and this 'default input/output methods' meta answer. Commented Aug 14, 2023 at 13:33
– Simd
Commented Aug 14, 2023 at 13:42

# Perl 5, 161 bytes

sub{$_=substr(abcdefghij,0,pop)x2;my%r;1while s/^(.*)(.)(.*)(.)(??{($t="$1$4$3$2$'")=~m,(.)(\1|.*(.).*\3(??{$1lt$3})),||$r{$t}++;$s{$t}++||''})/$1$4$3$2/;keys%r}  Try it online! $f=
sub{
$_=substr(abcdefghij,0,pop)x2; #set$_ to first n chars times 2
my%r;                                  #init %r where results are collected
1 while                                #repeat while untested perms exists
s/                                   #permute $_ by swap of two random chars ^(.*)(.)(.*)(.) (??{$t="$1$4$3$2$'"; #test new permutation in$t
$t=~ m,(.)(\1|.*(.).*\3(??{$1lt$3})), #two of same not neighbors and #no higher char before two equal lower || #if no error then tests passed and...$r{$t}++; #register current perm$t as a result
$s{$t}++||''                     #register current perm as seen/done
})
/$1$4$3$2/x;                         #if not seen change \$_ to new perm
keys%r                                 #return registered results
}
;


# Scala, 528 521 bytes

Port of @Ajax1234's Python answer in Scala.

521 bytes, it can be golfed much more.

Golfed version. Try it online!

def b(a:String,b:String)=(Map.empty[Char,Set[Char]]/:a.zip(b)){(d,p)=>d+(p._1->(d.getOrElse(p._1,Set.empty)+ p._2))}
def f(n:Int)={val q=scala.collection.mutable.Queue[(String,String)]((Array.fill(2)("abcdefghijklmnopqrstuvwxyz".substring(0,n)).mkString,""));var r=List[String]();while(q.nonEmpty){val(s:String,k:String)=q.dequeue;if(s.isEmpty){if(r.forall(S=>b(S,k).values.exists(_.size>1))){r=k::r}}else{for(i<-s.indices){if(k.isEmpty||s(i)!=k.last){q.enqueue((s.substring(0,i)+s.substring(i+1),k+s(i)))}}}};r.reverse;}


Ungolfded version. Try it online!

object Main {
def main(args: Array[String]): Unit = {
println(findSequences(2))
println(findSequences(3))
println(findSequences(4))
}

def buildDictionary(a: String, b: String): Map[Char, Set[Char]] = {
a.zip(b).foldLeft(Map.empty[Char, Set[Char]]) { (dict, pair) =>
dict + (pair._1 -> (dict.getOrElse(pair._1, Set.empty) + pair._2))
}
}

def findSequences(n: Int): List[String] = {
var initialString = Array.fill(2)("abcdefghijklmnopqrstuvwxyz".substring(0,n)).mkString
val queue = scala.collection.mutable.Queue[(String, String)]((initialString, ""))
var result = List[String]()

while(queue.nonEmpty) {
val (s: String, k: String) = queue.dequeue()

if(s.isEmpty) {
if(result.forall(sub => buildDictionary(sub, k).values.exists(_.size > 1))) {
result = k :: result
}
} else {
for(i <- s.indices) {
if(k.isEmpty || s(i) != k.last) {
queue.enqueue((s.substring(0, i) + s.substring(i+1), k + s(i)))
}
}
}
}

result.reverse
}
}
`