
The Dutch national flag is composed of three coloured bands in the order:

   red     (top)
   then white,   and
   lastly blue   (at the bottom). 


The problem posed by Edsger Dijkstra is:

Given a number of red, blue and white balls in random order, arrange them in the order of the colours in the Dutch national flag.
When the problem was first posed, Dijkstra then went on to successively refine a solution, minimising the number of swaps and the number of times the colour of a ball needed to determined and restricting the balls to end in an array, ...



Task
 Generate a randomized order of balls ensuring that they are not in the order of the Dutch national flag.
 Sort the balls in a way idiomatic to your language.
 Check the sorted balls are in the order of the Dutch national flag.


C.f.

 Dutch national flag problem
 Probabilistic analysis of algorithms for the Dutch national flag problem by Wei-Mei Chen. (pdf)


/*REXX program reorders a set of random colored balls into a correct order, which is the*/
/*────────────────────────────────── order of colors on the Dutch flag:  red white blue.*/
parse arg N colors                               /*obtain optional arguments from the CL*/
if N='' |  N=","  then N=15                      /*Not specified?  Then use the default.*/
if colors=''  then colors= 'red white blue'      /* "      "         "   "   "      "   */
#=words(colors)                                  /*count the number of colors specified.*/
@=word(colors, #)    word(colors, 1)             /*ensure balls aren't already in order.*/
 
    do g=3  to N                                 /*generate a random # of colored balls.*/
    @=@  word( colors, random(1, #) )            /*append a random color to the  @ list.*/
    end   /*g*/
 
say 'number of colored balls generated = '   N       ;  say
say center(' original ball order ', length(@), "─")
say @                                                ;  say
$=;                          do j=1  for #;
                             _=word(colors, j);      $=$  copies(_' ',   countWords(_, @))
                             end   /*j*/
say
say center(' sorted  ball order ', length(@), "─")
say space($)
say
    do k=2  to  N                                /*verify the balls are in correct order*/
    if wordpos(word($,k), colors) >= wordpos(word($,k-1), colors)  then iterate
    say "The list of sorted balls isn't in proper order!";         exit 13
    end   /*k*/
say
say 'The sorted colored ball list has been confirmed as being sorted correctly.'
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
countWords:  procedure;   parse arg ?,hay;  s=1
                  do r=0  until _==0;  _=wordpos(?, hay, s);  s=_+1;  end /*r*/;  return r