查找使用简单几何级数创建的树的祖先节点(Finding the ancestral nodes of a tree created with a simple geometric progression)

 我正在寻找一种算法，它可以为任何树中的任何节点提供祖先线，这些节点是使用几何系列创建的，其中a = 1 ， r等于任何整数。 例如，下图中的树， r = 2 ，而26的祖先线是[26, 13, 6, 3, 1] 。 
 
 
 我自己也有过这个问题，并且得出了一个答案，似乎给了我正确的答案，我已经尝试过r的值。 但在我创建一个使用此算法提供文件系统资源的应用程序之前，我想确保我不会错过某些边缘案例。 感觉就像那种问题必须有一个既定的解决方案，几乎肯定比我的更优雅。 有谁知道什么？ 
 
# My python implementation.

import math

def findLevelOfFolder(folder):
    """ Find the 'level' on which a given folder sits.  """
    if folder == 1:
        return 1
    else:
        level = 2
        while True:
            lower, upper= boundsOfLevel(level)
            if folder >= lower and folder <= upper:
                return level
            level += 1


def sumOfProgression(r, upToAndIncludingTerm):
    """
    Sums a simple geometric series.

    If r = 2, and upToAndIncludingTerm = 6, we'refinding the value of...
    pow(2, 0) + pow(2, 1) + pow(2, 3) + ... + pow(2, 5)
    """
    rRepeated = [r] * upToAndIncludingTerm
    powers = range(0, upToAndIncludingTerm)

    return sum(map(pow, rRepeated, powers))


def boundsOfLevel(level):
    """
    A levels 'bounds' refers to the number of the first folder and the last folder
    on that level. For example, when r == 2, and the level == 3, the
    bounds is (4, 7). The smallest possible level is 1, which, for any
    value of r always returns (1, 1).
    """
    assert(level > 0, "Smallest possible level is 1.")
    if level == 1:
        return 1, 1
    else:
        lower = sumOfProgression(foldersPerFolder, level-1) + 1
        upper = lower + pow(foldersPerFolder, level-1) - 1
        return lower, upper


def ancestorsOfFolder(folder, ancestors):
    """ Find the shortest route from folder '1' for the specified folder value.

    On completion, ancestors will contain a list of numbers each of which
    represents a folder in the ancestral line of 'folder'. The first number in
    the list will always be 'folder' and the last number will always be 1."""
    # First get the level...
    level = findLevelOfFolder(folder)
    lowerBoundOfPreviousLevel, _ = boundsOfLevel(level-1)

    relativePosition = folder - sumOfProgression(foldersPerFolder, level-1)
    parent = (lowerBoundOfPreviousLevel - 1) + math.ceil(relativePosition/foldersPerFolder)
    ancestors.append(parent)
    if parent != 1:
        ancestorsOfFolder(parent, ancestors)

# 'r' value
foldersPerFolder = 2

# looking for ancestral line of...
folder = 23

print(ancestorsOfFolder(folder, [folder])) # -> [23, 11, 5, 2, 1]

I'm looking for an algorithm that will give me the ancestral line for any node in any tree that has been created using a geometric series where a = 1, and r equals any whole number. For example the tree in the image below, r = 2, and the ancestral line for 26 is [26, 13, 6, 3, 1].
 
 
I've had a go at this myself and have come up with an answer that appears to give me the correct answer for the values of r that I've tried. But before I create an app that uses this algorithm to provide file-system resources I want to be sure that I'm not missing some edge-case somewhere. It feels like the kind of problem that must have an established solution that is almost certainly more elegant that mine. Does anyone know of anything?
 
# My python implementation.

import math

def findLevelOfFolder(folder):
    """ Find the 'level' on which a given folder sits.  """
    if folder == 1:
        return 1
    else:
        level = 2
        while True:
            lower, upper= boundsOfLevel(level)
            if folder >= lower and folder <= upper:
                return level
            level += 1


def sumOfProgression(r, upToAndIncludingTerm):
    """
    Sums a simple geometric series.

    If r = 2, and upToAndIncludingTerm = 6, we'refinding the value of...
    pow(2, 0) + pow(2, 1) + pow(2, 3) + ... + pow(2, 5)
    """
    rRepeated = [r] * upToAndIncludingTerm
    powers = range(0, upToAndIncludingTerm)

    return sum(map(pow, rRepeated, powers))


def boundsOfLevel(level):
    """
    A levels 'bounds' refers to the number of the first folder and the last folder
    on that level. For example, when r == 2, and the level == 3, the
    bounds is (4, 7). The smallest possible level is 1, which, for any
    value of r always returns (1, 1).
    """
    assert(level > 0, "Smallest possible level is 1.")
    if level == 1:
        return 1, 1
    else:
        lower = sumOfProgression(foldersPerFolder, level-1) + 1
        upper = lower + pow(foldersPerFolder, level-1) - 1
        return lower, upper


def ancestorsOfFolder(folder, ancestors):
    """ Find the shortest route from folder '1' for the specified folder value.

    On completion, ancestors will contain a list of numbers each of which
    represents a folder in the ancestral line of 'folder'. The first number in
    the list will always be 'folder' and the last number will always be 1."""
    # First get the level...
    level = findLevelOfFolder(folder)
    lowerBoundOfPreviousLevel, _ = boundsOfLevel(level-1)

    relativePosition = folder - sumOfProgression(foldersPerFolder, level-1)
    parent = (lowerBoundOfPreviousLevel - 1) + math.ceil(relativePosition/foldersPerFolder)
    ancestors.append(parent)
    if parent != 1:
        ancestorsOfFolder(parent, ancestors)

# 'r' value
foldersPerFolder = 2

# looking for ancestral line of...
folder = 23

print(ancestorsOfFolder(folder, [folder])) # -> [23, 11, 5, 2, 1]

原文：https://stackoverflow.com/questions/30514352