Piano World Home Page Forums Our Most Popular Forums Adult Beginners Forum A mathematical question

# Minum unit in quarter note subdivisions. 8 means 8th, 16 means 16th...
NOTE_MINIMUM_UNIT = 32
# Naturals + sharps
NOTE_NUMBER = 12

# This is simple but SLOW, it will run forever with the parameters above
def enumBars(previousNoteIsSilence, remainingTimeInUnit):
    # Ends the recursion
    if remainingTimeInUnit == 0:
        return 1

    tot = 0
    
    # Here we iterate over all possibile note duration.
    #
    # if NOTE_MINIMUM_UNIT is 32
    # from 1 (one 32th), 2 (one 16th), 3 (dotted 16th) ... to 32 (one quarter note)
    for noteDuration in range(1, remainingTimeInUnit + 1):
        if noteDuration <= remainingTimeInUnit:
            # We chose a note (12 possibilities)
            # then we recalculate the function recursively with the remaining time.
            tot = tot + NOTE_NUMBER * enumBars(False, remainingTimeInUnit - noteDuration)
            
            # Pause special case 
            # We can count "pause combination" only if the previus "note" is not a pause.
            if previousNoteIsSilence is False:
                tot = tot + enumBars(True, remainingTimeInUnit - noteDuration)
    
    return tot


# This is the same but it cache subproblems so it's FAST.
def enumBarsOptimized(previousNoteIsSilence, remainingTimeInUnit, state):
    # Ends the recursion
    if remainingTimeInUnit == 0:
        return 1
        
    # We use emainingTimeInUnit - 1 as the correct index in the array
    table = state[0 if previousNoteIsSilence is True else 1]
    if table[remainingTimeInUnit - 1] != False:
        return table[remainingTimeInUnit - 1]
    
    tot = 0
    
    # Here we iterate over all possibile note duration.
    #
    # if NOTE_MINIMUM_UNIT is 16
    # from 1 (one 16th), 2 (one 8th), 3 (dotted 8th) ... to 16 (one quarter note)
    for noteDuration in range(1, remainingTimeInUnit + 1):
        if noteDuration <= remainingTimeInUnit:
            # We chose a note (12 possibilities)
            # then we recalculate the function recursively with the remaining time.
            tot = tot + NOTE_NUMBER * enumBarsOptimized(False, remainingTimeInUnit - noteDuration, state)
            
            # Pause special case 
            # We can count "pause combination" only if the previus "note" is not a pause.
            if previousNoteIsSilence is False:
                tot = tot + enumBarsOptimized(True, remainingTimeInUnit - noteDuration, state)

    table[remainingTimeInUnit - 1] = tot
    return tot


# (NOTE_MINIMUM_UNIT * 4) is one 4/4 bar, (NOTE_MIN.. * 3) is one 3/4 bar ...
DURATION = NOTE_MINIMUM_UNIT * 4

print enumBarsOptimized(False, DURATION,  [[False] * DURATION for i in range (2)])