14
\$\begingroup\$

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 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 , 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
\$\endgroup\$
4
  • \$\begingroup\$ Clarifications: 1) Do outputs have to simplify symbol/inverse-symbol sequences? 2) Since I'm not familiar with this branch of math, I'm confused by your use of the terms "free group," "subgroup of a free group," and "group generated by." The title asks for a "subgroup of a free group," but the question body asks for a "group generated by." My assumption was that a "group" and a "subgroup" were two different things, but maybe I'm wrong...? \$\endgroup\$
    – DLosc
    Commented Jun 12 at 16:30
  • \$\begingroup\$ @DLosc 1. Yes, as without simplifying them a lot of words can't be generated 2. A subgroup is a subset of another group that's also a group in itself, I'll change the phrasing though \$\endgroup\$
    – emanresu A
    Commented Jun 12 at 21:02
  • \$\begingroup\$ Another point of confusion for me was that your first paragraph talks about generating a group from symbols, but after that you talk about generating a (sub)group from words. Am I correct that a subgroup generated from words is a subset of the free group generated from the set of all symbols used in those words? (And that it's called a "free" group because there are no constraints on the order in which you combine the symbols, whereas a group generated from words does have constraints?) That would be helpful to clarify somewhere. \$\endgroup\$
    – DLosc
    Commented Jun 12 at 21:40
  • \$\begingroup\$ @DLosc A subgroup generated from words is the set of all (simplified) concatenations of those words, not necessarily containing all possible combinations of its symbols. The free group is generated from the words a, b, c, etc; and because of that contains all possible concatenations of symbols and is a (non-strict) superset of any subgroup generated from words of the same set of symbols. Another way of defining subgroups of the free group is placing restrictions on them by declaring certain words equal to the empty string, but I don't really want to get into that for this challenge. \$\endgroup\$
    – emanresu A
    Commented Jun 12 at 21:56

5 Answers 5

5
\$\begingroup\$

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

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

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.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nice idea to use base conversion (the real byte saver is the reduction I could not find which could be used in mine for 18 too EDIT: TIO). \$\endgroup\$ Commented Jun 13 at 19:28
3
\$\begingroup\$

Haskell + hgl, 79 bytes

f w=nn>~(m(rF(#)[]<fo)<mM(p$ap[id,rv<m(*(-1))]w)<ef 0)
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 (*(-1))
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
\$\endgroup\$
3
  • \$\begingroup\$ 79 \$\endgroup\$ Commented Jun 16 at 0:58
  • 1
    \$\begingroup\$ Smart, thank you! \$\endgroup\$
    – corvus_192
    Commented Jun 16 at 10:28
  • 1
    \$\begingroup\$ Sorry I missed this somehow. Couple of improvements I can see: 1) m(*(-1)) can be m Ng 2) ef 0 can be e0 3) m(rF(#)[]<fo)< can be rF(#)[]<<fo<<. \$\endgroup\$
    – Wheat Wizard
    Commented 20 hours ago
2
\$\begingroup\$

Charcoal, 54 bytes

⊞υωWS«⊞υι⊞υ⭆⮌ι⎇№ακ↧κ↥κ»≔⍘NυθWΦE⪫υω⁺κ⎇№ακ↧κ↥κ№θκ≔⁻θ⌊ιθθ

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.

WS«

Loop through the words.

⊞υι

Add the word to the list.

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

Add the inverse of the word to the list.

»≔⍘Nυθ

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

WΦE⪫υω⁺κ⎇№ακ↧κ↥κ№θκ≔

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.

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