I wrote a class that generates combinatorial necklaces with fixed content as per Sawada: A fast algorithm to generate necklaces with fixed content. The class is instantiated with an input list that states the occurrence of each value that is to appear in the necklace. The execute method is called to run either Sawada's simple algorithm, or fast algorithm.
letter: a value that can appear in the necklace. Is a non-negative integer
occurrence: this states how many of each
lettermust appear in the necklace.
lettercan be used to index
word: a complete configuration of
lettersthat may be a necklace. Has a size of
alphabet: (used for fast algorithm only) this contains a list of all unique
letterdrops to 0, that
letteris removed from
alphabet, and vice versa.
k-1: the last
run: (used for fast algorithm only) this keeps track of the longest chain of
k-1starting from each index.
The simple algorithm goes through each index in
word, and recurs through
letters that are left in
occurrence until it can find a
word that satisfies the necklace condition.
The fast algorithm shortcuts some of this by checking if certain conditions allow it to return before assigning a
letter explicitly to every single index in
word. It initializes
word to the last value in
alphabet and tracks downward. Shortcuts:
- If the only values left to assign are
0, then it's not a necklace, and skip.
- If the only values left to assign are
k-1, then it's a necklace if the
k-1is > the current run (or = under certain conditions).
Some shortcuts can happen before the algorithm is started:
occurrencecan have values = 0 (stating that a given
letterwill not occur in the necklace). In this case, it's useful to also remove these letters from
- a necklace with fixed content must always start with the lowest
occurrencegreater than 0.
class Fixed_content_necklace: def __init__(self, n): # n is a list of integers # force negative numbers to zero for i in range(len(n)): if n[i] < 0: n[i] = 0 # initialized as number and type of letters to be found in necklace # ('(n0, n1, n2, ... nk-1)' in paper) self.n_init = n # number of letters in word ('n' in paper) self.N = sum(n) # number of different letters to be used self.k = len(n) self.initialize() def initialize(self, method='simple'): # used as the number and type of letters STILL TO BE ADDED to word self.occurrence = self.n_init.copy() # current word of letters ('a' in paper) self.word = *self.N # only used in 'fast' algorithm self.alphabet = [*range(self.k)] # number of the largest letter from each index to the end self.run = *self.N # assume that the first letter in the word will be 0, # and last letter will be k-1, # unless they get changed by set_letter_bounds self.first_letter = 0 self.last_letter = self.k-1 self.__set_letter_bounds(method) if method != 'simple': self.word[1:] = [self.last_letter]*(self.N-1) def __set_letter_bounds(self, method): # assign the first letter with nonzero occurrence to word # short-circuiting the search to the letter to put there during the algorithm # find the last nonzero letter found_first_nonzero = False for letter in range(self.k): if not found_first_nonzero and self.occurrence[letter] > 0: found_first_nonzero = True self.occurrence[letter] -= 1 self.word = letter self.first_letter = letter # remove any letters with zero occurrence from the alphabet so that # we automatically skip them if method != 'simple': if self.occurrence[letter] == 0: self.__remove_letter(letter) if not self.alphabet: self.last_letter = 0 else: self.last_letter = max(self.alphabet) # the algorithm starts at 2 (the second letter in 'word') because we've # already assigned the first letter during initialize def execute(self, method='simple'): self.initialize(method) if method == 'simple': yield from self._simple_fixed_content(2, 1) elif method == 'fast': yield from self._fast_fixed_content(2, 1, 2) def _simple_fixed_content(self, t, p): if t > self.N: # if the prenecklace is complete if self.N % p == 0: # if the prenecklace word is a necklace yield self.word.copy() else: for letter in range(self.word[t-p-1], self.k): if self.occurrence[letter] > 0: self.word[t-1] = letter self.occurrence[letter] -= 1 if letter == self.word[t-p-1]: yield from self._simple_fixed_content(t+1, p) else: yield from self._simple_fixed_content(t+1, t) self.occurrence[letter] += 1 def _fast_fixed_content(self, t, p, s): # discard any prenecklace that ends in 0 (except for 0^N) # and any prenecklace that ends in (k-1)^n < (k-1)^m that occurs earlier if self.occurrence[self.last_letter] == self.N - t + 1: if self.occurrence[self.last_letter] == self.run[t-p-1]: if self.N % p == 0: yield self.word.copy() elif self.occurrence[self.last_letter] > self.run[t-p-1]: yield self.word.copy() # If the only values left to assign are `0`, then it's not a necklace elif self.occurrence[self.first_letter] != self.N - t + 1: letter = max(self.alphabet) # get largest letter from letter list i = len(self.alphabet)-1 # reset position in letter list s_current = s while letter >= self.word[t-p-1]: self.run[s-1] = t - s self.word[t-1] = letter self.occurrence[letter] -= 1 if not self.occurrence[letter]: i_removed = self.__remove_letter(letter) if letter != self.last_letter: s_current = t+1 if letter == self.word[t-p-1]: yield from self._fast_fixed_content(t+1, p, s_current) else: yield from self._fast_fixed_content(t+1, t, s_current) if not self.occurrence[letter]: self.__add_letter(i_removed, letter) self.occurrence[letter] += 1 i -= 1 letter = self.__get_letter(i) # reset to initial state self.word[t-1] = self.last_letter def __remove_letter(self, letter): i = self.alphabet.index(letter) self.alphabet.remove(letter) return i def __add_letter(self, index, letter): self.alphabet.insert(index,letter) def __get_letter(self, i): if i < 0: return -1 else: return self.alphabet[i]
Each method gives what I expect (although in opposite order). However, the "fast" method using the fast algorithm described by Sawada almost always takes longer, even though it's set up to skip a number of branches during recursion. The only time I've found the 'fast' algorithm to be faster is when the
k-1 is more than twice the size of all the others combined.
import numpy as np n = [2, 1, 3, 10] # or n = [0, 1, 2, 1, 3, 14] mynecklace = Fixed_content_necklace(n) print('Simple Fixed Content:') sfc = np.array(list(mynecklace.execute())) print(sfc) print('---------------------') print('Fast Fixed Content:') ffc = np.array(list(mynecklace.execute('fast'))) print(ffc) print('---------------------') print('Are the arrays equivalent?: ', (ffc == np.flipud(sfc)).all())