The
DNF (Dutch National Flag) problem was named by Edsger Dijkstra, who is Dutch, and is the basis for part of his famous quicksort sorting algorithm that is studied and learned in computer science courses and used in many sorting algorithms.
The
DNF has some other interesting applications, one of which is in evaluating multiple choice questions involving orderings and matchings. Details omitted and left for another time.
This approach was realized in the 1980's, used in the 1990's, and appears in of my publications from 2004 to 2008.
You are given:
A row of n buckets.
Each bucket contains one pebble.
Each pebble is either red, white, or blue.
You are to are to arrange the pebbles in red, white and blue groups with the following restrictions:
You can look and determine the color of a pebble in a bucket.
You can swap the contents of two buckets.
You must handle:
Degenerate cases (1 or 2 colors, no buckets).
No other arrays are allowed.
The cost of looking at a pebble is great. Each pebble can only be looked at once.
Given an array from 1 to n:
Pick a value (preferably one in the data range).
Execute the DNF algorithm to partition the array into groups less than, equal, and greater than the value.
Recursively execute the algorithm on the left and right parts.