Iterate over all non-equivalent strings

Question

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.

Answer 1

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.

⊞υω

Start with an empty string.

Ｆ⁺θθ

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

Answer 2

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

Answer 3

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.

Answer 4

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',...])

Answer 5

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

Answer 6

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!

Answer 7

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

Answer 8

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

Answer 9

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)

Answer 10

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
}
;

Answer 11

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
  }
}