Fixed Content Necklace Generator

Question

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.

Some definitions:

• letter: a value that can appear in the necklace. Is a non-negative integer
• occurrence: this states how many of each letter must appear in the necklace. letter can be used to index occurrence.
• word: a complete configuration of letters that may be a necklace. Has a size of sum(occurrence).
• alphabet: (used for fast algorithm only) this contains a list of all unique letters. As occurrence for a letter drops to 0, that letter is removed from alphabet, and vice versa.
• k-1: the last letter in alphabet
• run: (used for fast algorithm only) this keeps track of the longest chain of k-1 starting 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:

1. If the only values left to assign are 0, then it's not a necklace, and skip.
2. If the only values left to assign are k-1, then it's a necklace if the occurrence of k-1 is > the current run (or = under certain conditions).

Some shortcuts can happen before the algorithm is started:

1. occurrence can have values = 0 (stating that a given letter will not occur in the necklace). In this case, it's useful to also remove these letters from alphabet and occurrence.
2. a necklace with fixed content must always start with the lowest letter that has occurrence greater 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 = [0]*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 = [0]*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[0]
        # 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[0] = 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 occurrence of k-1 is more than twice the size of all the others combined.

sample code:

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())

Answer 1

• Docstrings: You should include a docstring at the beginning of every method, class, and module you write. This will allow documentation to identify what your code is supposed to do. In the param section of some of your methods, I wrote ? so you can fill in what those are supposed to do.
• Simplify Returns: You have code like if expresssion1 return value1 else return value2. This code can be simplified to a one liner, return value1 if expression1 else value2.
• Too Many Comments: A quick look at your program and I see tons of gray. You don't need to explain every variable you create. Having a comment for self.k = len(n) is unnecessary, anyone can see that it's the length of variable n. Having a comment for the algorithms in _simple_fixed_content and _fast_fixed_content is helpful and allows people reading your code to know what that code is supposed to accomplish.
• Variable/Parameter Naming: Having parameter names like p, n, t, s can confuse other programmers reading your code, and even you! You should have meaningful and descriptive parameter and variable names, to remind you what their function is.
• Enumerate vs range(len()): I would use enumerate as it's more generic - eg it will work on iterables and sequences, and the overhead for just returning a reference to an object isn't that big a deal. If you just need an index, you can do for index, _ in enumerate(...), with the _ displaying that that variable is to be ignored.
• ClassNaming: While you got your variable and method naming correct, class names are a bit different. They should be CapCase.
• Variable & Operator Spacing: You should put spaces between your variables and operators (t+1 -> t + 1), as it's a little cleaner and allows you to space out your code, possibly improving readability.

Updated Code

"""
Module Docstring
A description of your program goes here
"""

class FixedContentNecklace:
    """
    A class that generates combinatorial necklaces with fixed content 
    """
    def __init__(self, number_list):
        """
        Class FixedContentNecklace Init Method

        :param number_list: A list of integers

        """
        # Force negative numbers to zero
        for index, _ in enumerate(number_list):
            if number_list[index] < 0:
                number_list[index] = 0

        self.n_init = number_list
        self.N = sum(number_list)
        self.k = len(number_list)

        self.initialize()

    def initialize(self, method='simple'):
        """
        Determines what method algorithm to use in the generation

        :param method: The name of the method/algorithm to use

        """
        self.occurrence = self.n_init.copy()
        self.word = [0] * self.N

        self.alphabet = [*range(self.k)]
        self.run = [0] * self.N 

        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[0], short-circuiting the search to the 
        letter to put there during the algorithm, and finds the last nonzero letter

        :param method: The name of the method/algorithm to use

        """
        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[0] = 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)
        self.last_letter = 0 if not self.alphabet else max(self.alphabet)

    def execute(self, method='simple'):
        """
        Runs the algorithm that's passed to `method`

        :param method: The method/algorithm to execute

        """
        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):
        """
        The simple algorithm

        :param t: ?
        :param 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):
        """
        The fast algorithm

        :param t: ?
        :param p: ?
        :param 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):
        """
        Removes the passed letter from self.alphabet

        :param letter: The letter to remove from self.alphabet

        """
        index = self.alphabet.index(letter)
        self.alphabet.remove(letter)
        return index

    def __add_letter(self, index, letter):
        """
        Adds the passed letter into self.alphabet at the specified index

        :param index: Index where letter is to be added
        :param letter: Letter to add to self.alphabet

        """
        self.alphabet.insert(index, letter)

    def __get_letter(self, index):
        """
        Gets a letter in self.alphabet at a specified index

        :param index: Index to get the letter

        """
        return -1 if index < 0 else self.alphabet[index]

Answer 2

Use a profiler

To try to find out what is slowing down the code, try using the Python profiler.

Data structures

The cited article uses a array/linked list data structure to store the alphabet, so that insertions and deletions are O(1). Your code uses a Python list. list.remove(item) does a linear search of the list to find the first occurance of item, removes the item, and then copies the remainder of the list up one position to fill in the removed item...so remove() is an O(n) operation. I believe list.insert() is O(n). These get called k times for each prenecklace. I don't know if that is enough to cause the slow down.

The article uses an array of elements that include the index of the next/previous element. It might help to also keep the index of the last element. Maybe something like this:

class Node:
    def __init__(self, letter, prev, next):
        self.letter = letter
        self.prev = prev
        self.next = next

self.alphabet = [Node(letter, letter - 1, letter + 1) for letter in range(self.k)]


def __remove_letter(self, letter):
    self.alphabet[letter].next.prev = self.prev
    self.alphabet[letter].prev.next = self.next
    return letter

def __add_letter(self, index, letter):
    self.alphabet[letter].next.prev = letter
    self.alphabet[letter].prev.next = letter


def __get_letter(self, index):
    return -1 if index < 0 else self.alphabet[index].letter

Other observations

letter = max(self.alphabet) isn't the max item always at the end? So this could be replaced by letter = self.alphabet[-1].

"Big-O" analysis generally looks at the how an algorithm performs as n gets large. For small problems an algorithm with worse Big-O may be faster because the problem isn't large enough to amortize the extra overhead of the more efficient algorithm. For example, bubble sort may be faster than quick sort for a list of a few items. Here, your sample necklaces may not be big enough to see the benefits of the fast algorithm.