CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.

| Download

Edited Code for Stirling Paper

Views: 30
Visibility: Unlisted (only visible to those who know the link)
Image: ubuntu2204
Tweet
Share
Share
Kernel: SageMath 9.8

A word is flat if the sequence of leading letters is weakly increasing. The function is_flat, returns True if a word is flat and False otherwise.

The number of runs in a word ww is the number number of maximal contiguous weakly increasing subwords of ww. The function run_counter, returns the number of runs in a word.

def is_flat(word):
    # changed from array to single variable -> worst case memory usage before is O(n), now it's O(1) since we use constant space
    last_leading_letter = word[0]

    for index in range(1, len(word)):
        if word[index - 1] > word[index]:
            if last_leading_letter > word[index]:
                return False
            last_leading_letter = word[index]
    return True

def run_counter(word):
    run_count = 1
    
    for index in range(1, len(word)):
        if word[index - 1] > word[index]:
            run_count += 1
    return run_count

To generate Stirling Permutations of order n+1n + 1, we can take the list of Stirling Permutations of order nn and insert (n+1)(n+1)(n + 1)(n + 1) at any place in the word.

While not obvious, we can generate flattened Stirling Permutations of order n+1n + 1 by attempting to insert (n+1)(n+1)(n + 1)(n + 1) at every position in the word, and reject those words which are not flat.

# added n as a parameter so we don't have to calculate it
def gen_flatStirPerms(previousPerms, n):
    if previousPerms == []:
        return [[1,1]]

    newPerms = []
    
    for perm in previousPerms:
        for j in range(len(perm)+1):
            candidate = perm[:j] + [n+1, n+1] + perm[j:]

            if is_flat(candidate):
                newPerms.append(candidate)
            
    return newPerms

dStarting with an empty list, we construct the flattened Stirling Permutations of each order, counting the total number of flattened Stirling Permutations as well as the number of flattened Stirling Permutations with a given number of runs.

list_of_perms = []

for n in range(1,9):
    list_of_perms = gen_flatStirPerms(list_of_perms, n)
	# change this and line updating it below so we don't have the leading 0
    count_by_runs = n*[0]
    
    for perm in list_of_perms:
        count_by_runs[run_counter(perm)-1] += 1
        
    print(n, len(list_of_perms), count_by_runs)
1 1 [1] 2 2 [1, 1] 3 6 [1, 5, 0] 4 24 [1, 15, 8, 0] 5 116 [1, 37, 70, 8, 0] 6 648 [1, 83, 374, 190, 0, 0] 7 4088 [1, 177, 1596, 2034, 280, 0, 0] 8 28640 [1, 367, 6012, 15260, 6720, 280, 0, 0]