18/09/26 01:01:21.81 QBwnT99Q.net
>>651
自分もPCで>>597を数えたら、k=6 で 3501、k=7 で 36820 だった。
def three_letter_nonadjacent_words(counter, word, letters="abc"):
if sum(counter) == 0:
yield word
return
for i,x in enumerate(letters):
if counter[i] > 0:
if len(word) < 2 or {x,word[-1],word[-2]} != set(letters):
c = list(counter)
c[i] -= 1
yield from three_letter_nonadjacent_words(tuple(c), word + x)
def circularly_legal(word, letters=set("abc")):
return {word[0],word[-1],word[-2]} != letters \
and {word[1],word[0],word[-1]} != letters
def circular_three_letter_nonajacent_words(k):
for word in three_letter_nonadjacent_words((k,)*3,""):
if not circularly_legal(word):
continue
yield word
def num_fixed_perms(word):
n = len(word)
r = 1
for i in range(1,n):
if word[i:] == word[:-i] and word[:i] == word[-i:]:
r += 1
rev = word[::-1]
if word == rev:
r += 1
for i in range(1,n):
if word[i:] == rev[:-i] and word[:i] == rev[-i:]:
r += 1
return r
def num_circular_three_letter_nonajacent_words(k):
#used Burnside's lemma
return sum(num_fixed_perms(word) for word in \
circular_three_letter_nonajacent_words(k)) // (6*k)
for k in range(1,7):
print(k, num_circular_three_letter_nonajacent_words(k))