Generate a subgroup of a free group

Question

In group theory, the free group with \$n\$ generators can be obtained by taking \$n\$ distinct symbols (let's call them \$a, b, c ...\$ etc), along with their inverses \$ a^{-1},b^{-1},c^{-1} ...\$ . Then the free group is the set of all finite words formed by concatenating these, subject to \$aa^{-1}, bb^{-1}, cc^{-1} \$etc being compressible to an empty string - for example, \$acbb^{-1}ca^{-1} = acca^{-1}\$, and some members of this group are \$ab^{-1}, cacb^{-1}a^{-1},b\$ etc.

The subgroup of the free group generated by a word \$w\$, denoted as \$\langle w \rangle\$, is the set of all words that can be formed by concatenating \$w\$ and \$w^{-1}\$, where \$w^{-1}\$ is \$w\$ reversed and with each element inverted - for example, \$(cb^{-1}c^{-1}a)^{-1} = a^{-1}cbc^{-1}\$. For example, \$\langle ab^{-1} \rangle\ = \{e, ab^{-1}, ba^{-1}, ab^{-1}ab^{-1}, ba^{-1}ba^{-1}...\}\$ and so on, where \$e\$ is the empty string and is included in the set.

Then, the subgroup generated by a set of words \$\{w_1,w_2,w_3...\}\$ (denoted \$\langle w_1,w_2,w_3...\rangle\$ is the set of all concatenations of \$w_1,w_1^{-1},w_2,w_2^{-1},w_3,w_3^{-1}\$ etc. For example, \$\langle aa,ba\rangle\$ is the set of all concatenations of \$aa, a^{-1}a^{-1}, ba, a^{-1}b^{-1}\$, which is \$\{e, aa, a^{-1}a^{-1}, ba, a^{-1}b^{-1}, baa^{-1}a^{-1} = ba^{-1}, ab^{-1} ...\}\$ etc.

Your challenge is to, given a set of words \$\{w_1,w_2,w_3...\}\$, output the subgroup of the relevant free group generated by them. You may use any set of distinct values to represent the symbols and their inverses, as long as there are at least 5 distinct symbols that can be represented this way. For example, having \$a = 1, a^{-1} = -1, b = 2, b^{-1} = -2 ... e^{-1} = -5\$ and representing words as arrays of these would be fine, and so would taking \$a = \text{"a"}, a^{-1} = \text{"A"} ... e^{-1} = \text{"E"}\$ and using string I/O. You may additionally take a list of all symbols used in the input, with or without their inverses.

Standard sequence output rules apply - you may output all generated elements infinitely, or take an 0/1-indexed n and output the nth / first n terms. The output can be in any order and may include duplicates, but every word that can be built from the input words should eventually appear at some finite index in the output. The one exception to this is the empty string (which occurs in the output for any input), which you may omit.

This is code-golf, shortest wins!

Testcases

These use the aAbBcCdDeE... format from before. Each of these is a potential first 10 terms of the generated sequence, and includes the empty string (see before the ,)

a -> , a, A, aa, AA, aaa, AAA, aaaa, AAAA, aaaaa
a, b -> , a, b, A, B, aa, ab, ba, bb, Ab
aa, ba -> , aa, ba, AA, AB, aB, bA, aaba, AAba, baaa
acc, CC ->, a, A, aa, AA, cc, CC, acc, CCA, aaa
abcbac, dCBA, CAB -> , d, D, dd, DD, ddd, DDD, bac, dbac, CAB

Answer 1

Jelly,  24  23 bytes

FµŻSƝaSƝTị
UN;ƊṗⱮẎÇÐL€ḣ

A dyadic Link that accepts the list of words on the left, and a non-negative integer, \$n\$, on the right and yields a list of the first \$n\$ elements.

The words use an alphabet of positive integers and their negation to represent an inverse.

The sequence includes many repeats as well as the empty word (also repeatedly).

Don't Try it online! as it's crazy slow.

For the sequence using up to \$n\$ words try this instead.

How?

FµŻSƝaSƝTị - Link 1, "Simplify Once": list of Words OR Word
F          - flatten the list of Words (no-op when passed Word)
 µ         - start a new monadic Link - f(S=that):
  Ż        -   prefix with a zero
   SƝ      -   sum of each neighbouring pair of that
      SƝ   -   sum of each neighbouring pair of S
     a     -   logical AND these together
                 (vectorises and takes the left when the right expires)
        T  -   truthy indices
         ị -   index into S -> S with offsetting neighbours removed

UN;ƊṗⱮẎÇÐL€ḣ - Main Link: StartingWords, Index
   Ɗ         - last three links as a monad - f(StartingWords):
U            -   reverse each {StartingWords}
 N           -   negate -> InverseWords
  ;          -   concatenate {StartingWords}
     Ɱ       - map across {C in [1..Index]} with:
    ṗ        -   Cartian power -> all wordlists of length C
      Ẏ      - tighten -> list of the wordlists
          €  - for each:
        ÐL   -   apply until no change:
       Ç     -     call Link 1 as a monad
           ḣ - head to {Index}

Answer 2

Jelly, 18 17 bytes

UN;ƊL⁹ḃịƲF;Ṗ+Ṫ¥?/

Try it online!

-1 thanks to Jonathan Allan

Takes the words as positive and negative integers on the left, and a 1-index on the right, outputting with a fair number of duplicates. Not shortest-first--it takes up to index 210 to generate the single d on the last test case.

UN                   Reverse and negate the words
  ;Ɗ                 and concatenate the list of inverses to the original words.
     ⁹ḃ              Convert the index to bijective base
    L                [# of words and inverse words],
       ịƲ            index the digits into the list of words and inverse words,
         F           and flatten the words together.
                /    Reduce left to right by:
               ?     If
            +Ṫ¥      the new symbol's sum with the last symbol of the accumulator
          ;    ?     is nonzero, then concatenate it to the end,
           Ṗ   ?     else remove the last symbol.

Answer 3

Pyth, 25 bytes

#jmu?s>2K+GHKPGsdYy=+m__M

Try it online!

Words are lists of non-zero integers where inversing is done by negation.

Generates output infinitely with many repeated terms, including the empty list.

Explanation

#jmu?s>2K+GHKPGsdYy=+m__MdQQ    # implicitly add dQQ
                                # implicitly assign Q = eval(input())
                   =      Q     # assign to Q
                     m    Q     #   map lambda d over Q
                       _Md      #     negate each element of d
                      _         #     and reverse
                    +      Q    #   concatenated with Q
  m               y             # map powerset of Q over lambda d
   u           sdY              #   reduce sum(d) over lambda G,H with [] as starting value
        K+GH                    #     assign K to the concatenation of G and H
    ?                           #     ternary operator, return the following
     s>2K                       #     if sum(K[-2:]) != 0:
            K                   #       K
                                #     else:
             PG                 #       G[:-1]
 j                              # print, sperated by newlines
#                               # repeat infinitely

Answer 4

Haskell + hgl, 79 70 bytes

-9 bytes thanks to Wheat Wizard

f w=nn>~rF(#)[]<<fo<<mM(p$ap[id,rv<m Ng]w)<e0
a#(h:t)| -h==a=t
a#b=a:b

Attempt This Online!

Takes positive and negative numbers as input.

Semi-Ungolfed:

invertWord = reverse . map negate
mkInvertedWords w = w ++ map invertWord w
cartesianPower l n = mapM (\_ -> mkInvertedWords l) [0..n]

reduceWords :: [[Int]] -> [Int]
reduceWords = foldr (#) [] 

-- This function implements the cancellation of inverses
a#(h:t)| -h==a=t
a#b=a:b

f w = do
 n <- [0..]
 return map reduceWords $ cartesianPower w n

Answer 5

Charcoal, 54 bytes

⊞υωＷＳ«⊞υι⊞υ⭆⮌ι⎇№ακ↧κ↥κ»≔⍘ＮυθＷΦＥ⪫υω⁺κ⎇№ακ↧κ↥κ№θκ≔⁻θ⌊ιθθ

Try it online! Link is to verbose version of code. Takes a newline-terminated list of newline-terminated words followed by n as input and outputs the nth term (1-indexed excluding the empty term, but if you run this on ATO instead then it will be 0-indexed including the empty term) including many, many duplicates. Explanation:

⊞υω

Start with just an empty string.

ＷＳ«

Loop through the words.

⊞υι

Add the word to the list.

⊞υ⭆⮌ι⎇№ακ↧κ↥κ

Add the inverse of the word to the list.

»≔⍘Ｎυθ

Input n and convert it to base 2m+1, where m is the number of words.

ＷΦＥ⪫υω⁺κ⎇№ακ↧κ↥κ№θκ≔

For each symbol in the words and their inverses, concatenate the symbol with its inverse. While at least one of those pairs exists in the result...

⁻θ⌊ιθ

... remove one of them from the result.

θ

Output the final result.

Bonus 58-byte version that outputs the first n terms: Attempt This Online! Link is to verbose version of code.