Lecture Notes: Lost Beast Algorithm

Overview

• Objective: Create a function to display all different combinations of n numbers ranging from 1 to 9 in ascending order.
• Prototype: This function does not return any value and takes the number of digits as input (n).

Function Behavior

1. Initialization:

   • Two arrays (v & v_max): Contain initial (0 to n-1) and final (10-n to 9) values respectively.
   • Integer flag and an integer base are declared.
   • Check if n is within the valid range (1 to 10), if not, prompt the user to input a valid integer.

2. Algorithm:

   • Initial Setup: Initialize arrays v and v_max for the first small values and max values respectively.
   • Print initial array values.
   • Use a while loop to generate all combinations while v[0] is not equal to v_max[0].
   • Flag: Start with the last position of the array (n-1) and check if it has reached its maximum value.
     • If a value equals its maximum, reduce the flag and move left.
   • Once the sentinel value (flag) is found, increase it by one and adjust all values to the right.
   • Print the new combination and repeat until the first element reaches its maximum.

3. Printing Function:

   • Helper function to print array values, determining if they are the last set.
   • Format output with commas and spaces appropriately.

Example Implementation

• Initial State: v = [0, 1, 2, 3]
  • Intermediate combinations: Increment values maintaining ascending order.
  • Final State: v_max = [6, 7, 8, 9]

Steps of the Algorithm

1. Finding the Sentinel:

   • Search from right to left for the first value not at its maximum.
   • Increment the sentinel and adjust subsequent values to maintain ascending order.

2. Print Function:

   • Check if the current combination is the last by comparing to v_max.
   • Print the combination with appropriate formatting.

Visualization and Understanding

• Initial State: Create arrays with initial and maximum values.
• Final State: Determine configurations between the initial and final states by incrementing values.
• Detailed Walkthrough: Print arrays for further understanding.

Example Outputs

• Given n=4, output: Initial [0, 1, 2, 3] -> Final [6, 7, 8, 9], with all intermediate states printed in ascending order.
• For n=10, output: single combination [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].