{menu}

Permutation Odometers
The Base-N-Odometer by Phillip P. Fuchs

Are we there yet?

Travelers clearly depend upon an odometer to answer this question. By definition, odometers measure a distance traveled and can accurately predict a scheduled event or repair. In contrast, the average speed at which a distance is crossed determines an arrival time. Consider a destination 120 miles away from your current location; an automobile traveling at 30 m.p.h. will arrive at this destination in approximately 4 hours, whereas an automobile traveling at 60 m.p.h. will arrive at the same destination in approximately 2 hours. Although the automobile's speed clearly influenced the arrival time, the odometer in both scenarios registers an increase of only 120 miles.

What if the same principles are applied to a permutation? One could effortlessly answer the concerns presented above. In this case, the odometer is utilized to count generations of N elements within a complete permutation set. Arriving at a solution depends upon the initial list(s) given, the speed of the computer(s), threading, and distribution (by degree). The initial list given directly corresponds to the direction of travel AND the proximity to a solution within a prioritized list simply increases the chance to succeed early...

Often permutation odometer-style models only display a current combination order as index wheels and fail to record vital information such as a simple generation count (or distance) and the next swappable target (pair) at a glance. If a common automobile mileage odometer can accomplish this small feat, then permutation odometers are not exempt from this principle. The rules still apply here as well.

As a Computer Science student, one must ask questions such as: If a standalone permutation odometer only registers the current combination order, then is it really an odometer? Can a single odometer reading (as a linear array) exist by itself and be read by other algorithms? Are programmers allowed to create practical odometer functions such as a current generation count, set(n), reset(), rewind(n), and fast-forward(n) - solely based upon an odometer reading?

As stated before, the "Base-N-Odometer" that is promoted on this website easily addresses concerns described above and is highly predictable, whereas other odometer models are more complex, certainly have more code to support the odometer model, and are difficult to grasp by many novice computer science students (in my opinion as a Computer Science teacher).

The QuickPerm algorithm presented earlier can utilize a countdown process or it can utilize a counting process. The significant difference between a countdown QuickPerm algorithm and a counting QuickPerm algorithm is the initialization of the Base-N-Odometer (coded as the primary controller array p[N]). A countdown process will initialize the controller array to corresponding index values (a maximum digit), whereas a counting process will initialize all values in the controller array to zero. Whether a countdown process or a counting process is utilized is rather debatable. Both counting processes offer similar advantages and only a few minor disadvantages if any.

In any case scenario, the primary controller array p[N] within the QuickPerm algorithm(s) is analogous to an incremental Base-N-Odometer, where the least significant digit p[0] is zero, digit p[1] counts in base 2 (binary), digit p[2] counts in base 3, ..., and digit p[N-1] counts in base N. Considering a counting QuickPerm algorithm, initially the default upper index variable i is set to one as a reference to the binary odometer digit which later advances by one each time a corresponding digit flips or rolls over. Since the upper index variable is clearly odd, the default lower index variable j is assigned to the odometer digit referenced by the upper index which coincides to the value stored in p[i] or zero. The first SWAP is executed on the target data structure(s) and the odometer digit/wheel referenced by the upper index advances...

Before another swap can take place, upper and lower index values must be recalculated based upon values stored in the base N odometer p[N]. Again the upper index begins at binary digit p[1] and attempts to flip each consecutive digit by adding one. The upper index will settle upon the first digit that will not flip. If the upper index is even, the lower index is assigned to the least significant odometer digit which coincides to the value stored in p[0] (or simply the lower index will remain at zero). Otherwise the lower index will be assigned to the actual odometer digit now referenced by the upper index. A second SWAP is executed on the target data structure(s) and the odometer digit/wheel referenced by the upper index advances.

This process continues until the upper index attempts to reference an odometer digit beyond the length of the linear permutable target in question.

Presented below is a table that compares common odometer characteristics with various computerized odometer models such as my "Base-N-Odometer", a standard automobile trip odometer, and an odometer-style generator commonly referenced by modern lexicographical (alpha-permutation) algorithms. Each odometer characteristic can have a "Yes" or "No" answer or ??? for an unknown. The third and fourth columns are open for your interpretation. Please provide a sound explanation and corresponding code to support your answer(s). I'll collect the data and compile the results within the table below:

Common Odometer Characteristics:
Standalone Odometer Models
Base N ~ Mileage ~ Lexicog
Represents Current Combination Yes Yes Yes
Counts All Generations ("Distance") Yes Yes No
Sequentially Linked Digits or Wheels Yes Yes No
Expected Duplicate Digits Yes Yes No
Standalone and Shareable Readings Yes Yes ???
Defines Upper and Lower Indices at a Glance Yes ??? ???
Able to Set(n) & Distribute Readings Yes ??? ???
Able to Reset() Yes Yes ???
Able to Quickly Rewind(n) Yes ??? ???
Able to Fast-Forward(n) Yes ??? ???
Calculate the Nth Combination Yes ??? ???
Miscellaneous / Other ??? ??? ???

For more information on the Base-N-Odometer research the countdown QuickPerm algorithm followed by the counting QuickPerm algorithm.

Glossary:   {Compare and contrast the following vocabulary terms as presented below.}


Base-N-Odometer noun
  1. a core algorithm primarily used to count all generations within a permutation set containing N elements or used as a Big Integer Calculator.
  2. an algorithm for recording numerous events over time by counting in a sequentially based numbering system.
  3. an algorithm for counting events within a fixed time period that can be initialized, reset, rewound, or advanced.
  4. an algorithm for sequentially counting events exceptionally characterized by occurrences of duplicate digits and digit roll-overs.
  5. an algorithm used to identify valid target elements within a parallel linear list(s) or used to determine a pending event.

Odometer noun
  1. an instrument used to measure distance traveled.
  2. an instrument for recording an overall distance traveled counting in a universal base 10 numbering system.
  3. an instrument for measuring a distance traveled between two geographic coordinates. Often referenced as a trip-odometer.
  4. an instrument for measuring distance traveled by a sequential count characterized by occurrences of duplicate digits and digit roll-overs.
  5. an instrument used to determine a scheduled event or repair.

Permutation Odometer noun
  1. an algorithm used to count all generations within a permutation set containing N elements. Also called the "Base-N-Odometer".
  2. an algorithm for recording unique generations processed by counting in a sequentially based numbering system.
  3. an algorithm for counting generations over a fixed time period within a permutation set that can be initialized, reset, rewound, or advanced.
  4. an algorithm for sequentially counting generations exceptionally characterized by occurrences of duplicate digits and digit roll-overs.
  5. an algorithm used to identify valid target elements to swap within a linear list(s) or used to predict an imminent generation order.



[New Book: Practical Permutations]

[QuickPerm] | [EXAMPLE 02] | [EXAMPLE 03] | [EXAMPLE 04] | [MetaPerm]
[Download the Five C++ Examples] | [Permutation Exercises]
[Contact the Author] | [Make a Donation] | [Links]
[HOME]

Help keep public education alive! We need your donations, click here to help now...

{top}

Copyright © 2008 by Phillip Paul Fuchs, all rights reserved.
Abstracting with credit is permitted...