I have three lists: word, occurrence, and alphabet :
occurrence = [2, 1, 3, 10] # but can be initialized differently
k = len(occurrence)
alphabet = [range(k)]
N = sum(occurrence)
word = [0]*N # initially
word is a list that will contain a certain combination of values pulled from alphabet, as decided by occurrence. In the example above, word must contain two 0, one 1, three 2, and ten 3 in some combination. alphabet can be used to index occurrence.
I have an algorithm (see List-Fixed-Content by Sawada) that recursively adds/removes "letters" in alphabet to/from word, decrementing the value in the corresponding index of occurrence when a letter is added, and incrementing that same value when a letter is removed.
The algorithm starts at the highest letter (3 when first initialized in this case) where the corresponding index in occurrence is still greater than zero, then as the algorithm proceeds, goes to the NEXT highest letter that is still greater than zero.
I am currently handling this by removing a letter when its occurrence reaches 0, via word.remove(letter), then adding it back in the correct position using word.insert(i,letter) when its occurrence increases again. This makes both finding the maximum value in the alphabet stepping down alphabet very easy.
The full code as requested:
occurrence = [2, 5, 3, 5] # example occurrence
k = len(occurrence)
alphabet = [range(k)]
N = sum(occurrence)
word = [0]*N
def algorithm(t, p):
if t > N:
if N % p == 0:
yield word.copy()
else:
letter = max(alphabet)
i = len(alphabet)-1
while letter >= word[t-p-1]:
word[t-1] = letter
occurrence[letter] -= 1
if not occurrence[letter]: # <<<<
i_removed = remove(letter)
if letter == word[t-p-1]:
yield from algorithm(t+1, p)
else:
yield from algorithm(t+1, t)
if not occurrence[letter]: # <<<<
add(i_removed, letter)
occurrence[letter] += 1
i -= 1
letter = get(i) # <<<<
def remove(letter):
i = alphabet.index(letter)
alphabet.remove(letter)
return i
def add(i, letter):
alphabet.insert(i,letter)
def get(i):
if i < 0:
return -1
else:
return alphabet[i]
def execute()
yield from algorithm(1, 1)
# Example usage of function
print(list(execute()))
I've found this to be VERY slow, and I suspect it's because of list.insert. What is a better way of finding the highest and next-highest letters of alphabet whose corresponding values in occurrence are non-zero, without adding and removing letters from alphabet?
Something like assigning the lists as numpy arrays and the following code?
...
letter = max(alphabet[occurrence > 0])
while letter >= limit: # some limit
...
while True: # <<<< replaces remove(), add(), and get()
letter -= 1
if letter < 0 or occurrence[letter] > 0:
break
