16
\$\begingroup\$

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.

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

11 Answers 11

5
\$\begingroup\$

Charcoal, 45 bytes

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

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

≔⪪…βN¹θ

Get the first n letters of the lowercase alphabet.

⊞υω

Start with an empty string.

F⁺θθ

Loop 2n times.

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

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
\$\endgroup\$
1
  • \$\begingroup\$ Very nice simplification of the rules. \$\endgroup\$
    – Simd
    Commented Aug 13, 2023 at 8:40
5
\$\begingroup\$

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<n\$.

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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',...])
\$\endgroup\$
3
\$\begingroup\$

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

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

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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can save 8 bytes by replacing ascii_lowercase and its import with the literal 'abcdefghijklmnopqrstuvwxyz' \$\endgroup\$
    – yoniLavi
    Commented Aug 13, 2023 at 23:43
  • 1
    \$\begingroup\$ @yoniLavi Thank you, updated \$\endgroup\$
    – Ajax1234
    Commented Aug 13, 2023 at 23:48
3
\$\begingroup\$

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
              97+       Add 97
                 H      Convert from codepoints to string
\$\endgroup\$
1
  • \$\begingroup\$ You might win the prize for the slowest code. \$\endgroup\$
    – Simd
    Commented Aug 14, 2023 at 10:05
3
\$\begingroup\$

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\$.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Commented Aug 15, 2023 at 18:18
2
\$\begingroup\$

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.

Try it online or verify both test cases.

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)
\$\endgroup\$
3
  • \$\begingroup\$ You are not outputting strings. \$\endgroup\$
    – Simd
    Commented Aug 14, 2023 at 12:01
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 14, 2023 at 13:33
  • 1
    \$\begingroup\$ Thanks for the links. \$\endgroup\$
    – Simd
    Commented Aug 14, 2023 at 13:42
2
\$\begingroup\$

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
}
;
\$\endgroup\$
1
\$\begingroup\$

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
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.