Dutch national flag problem: Difference between revisions

{{task}}

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, ...

 

# 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.

 

* [[wp:Dutch national flag problem|Dutch national flag problem]]

* [https://www.google.co.uk/search?rlz=1C1DSGK_enGB472GB472&sugexp=chrome,mod=8&sourceid=chrome&ie=UTF-8&q=Dutch+national+flag+problem#hl=en&rlz=1C1DSGK_enGB472GB472&sclient=psy-ab&q=Probabilistic+analysis+of+algorithms+for+the+Dutch+national+flag+problem&oq=Probabilistic+analysis+of+algorithms+for+the+Dutch+national+flag+problem&gs_l=serp.3...60754.61818.1.62736.1.1.0.0.0.0.72.72.1.1.0...0.0.Pw3RGungndU&psj=1&bav=on.2,or.r_gc.r_pw.r_cp.r_qf.,cf.osb&fp=c33d18147f5082cc&biw=1395&bih=951 Probabilistic analysis of algorithms for the Dutch national flag problem] by Wei-Mei Chen. (pdf)

 

=={{header|Ada}}==

 

 

procedure Dutch_National_Flag is

 

Print("After Sorting: ", A);

 

{{out}}

Original Order: WHITE, WHITE, BLUE, WHITE, BLUE, BLUE, WHITE

After Sorting: WHITE, WHITE, WHITE, WHITE, BLUE, BLUE, BLUE</pre>

 

=={{header|AutoIt}}==

Given each color a value in descending order ( Red = 1, White = 2 And Blue = 3)

#include <Array.au3>

Dutch_Flag(50)

_ArrayDisplay($avArray)

EndFunc ;==>Dutch_Flag

 

{{works with|BBC BASIC for Windows}}

Sort% = FN_sortinit(0,0)

prev% = weight%

NEXT

<pre>

Random list: Red White Red Blue White Red White Blue Red Red Blue Red

 

=={{header|C}}==

#include <stdlib.h> //srand(), rand(), RAND_MAX, qsort()

#include <stdbool.h> //true, false

#define NUMBALLS 5 //NUMBALLS>1

 

return c1-c2;

}

}

return 0;

{{out}}

<pre>Accidentally still sorted:rrrww

 

=={{header|C++}}==

#include <iostream>

 

dnf_partition(balls, balls + 9, WHITE, BLUE);

print(balls, 9);

{{out}}

<pre>

Balls: red red red white white white blue blue blue

Sorted: true

</pre>

 

=={{header|D}}==

 

enum DutchColors { red, white, blue }

 

int lo, mid, hi = items.length - 1;

 

DutchColors[12] balls;

foreach (ref ball; balls)

 

writeln("Original Ball order:\n", balls);

writeln("\nSorted Ball Order:\n", balls);

{{out}}

<pre>Original Ball order:

 

===Bidirectional Range Version===

std.array, std.traits;

 

assert(balls[0 .. n].isSorted());

}

The output is the same.

 

=={{header|Erlang}}==

-export([random_balls/1, is_dutch/1, dutch/1]).

 

dutch(R, W, B, [red | L]) -> dutch([red|R], W, B, L);

dutch(R, W, B, [white | L]) -> dutch(R, [white|W], B, L);

 

Sample usage:

L = random_balls(10),

case is_dutch(L) of

true -> io:format("The random sequence ~p is already in the order of the Dutch flag!~n", [L]);

false -> io:format("The starting random sequence is ~p;~nThe ordered sequence is ~p.~n", [L, dutch(L)])

 

<pre>The starting random sequence is [white,white,blue,blue,white,red,white,blue,

blue,white];

The ordered sequence is [red,white,white,white,white,white,blue,blue,blue,

blue].</pre>

=={{header|Go}}==

 

import (

f.sort3()

fmt.Println(f)

{{out}}

<pre>

The function "sort" works with anything that belongs to the Eq and Ord classes.

The function "randomRIO" takes a range of two integers to give a random value within the range. We make Color an instance of Enum so that we can give Red, White and Blue as integers to randomRIO and convert the random number back to Red, White or Blue.

import System.Random (randomRIO)

import System.IO.Unsafe (unsafePerformIO)

False -> do

putStrLn $ "The starting random sequence is " ++ show a ++ "\n"

<pre>

The starting random sequence is [White,Blue,Blue,Blue,Blue,Blue,Blue,Red,Red,

 

To understand ''why'' Dijsktra was interested in the problem, here's an example showing difficiency of using generic sort:

 

mk012 :: Int -> Int -> [Int] -- definitely unordered

mk012 n = (++[0]).(2:).map (`mod` 3).take n.frr where

-- frr = Fast Rubbish Randoms

 

dutch1 n = (filter (==0) n)++(filter (==1) n)++(filter (==2) n)

 

 

main = do -- 3 methods, comment/uncomment each for speed comparisons

-- print $ inorder $ dutch1 s -- O(n)

print $ inorder $ dutch2 s -- O(n)

 

=={{header|J}}==

We shall define a routine to convert the values 0 1 2 to ball names:

and its inverse

Next, we need a random assortment of balls:

BALLS

┌────┬───┬────┬───┬───┬─────┬─────┬─────┬────┬────┬─────┬────┬────┬───┬────┬───┬─────┬───┬────┬───┐

│blue│red│blue│red│red│white│white│white│blue│blue│white│blue│blue│red│blue│red│white│red│blue│red│

And we want to sort them in their canonical order:

┌───┬───┬───┬───┬───┬───┬───┬─────┬─────┬─────┬─────┬─────┬────┬────┬────┬────┬────┬────┬────┬────┐

│red│red│red│red│red│red│red│white│white│white│white│white│blue│blue│blue│blue│blue│blue│blue│blue│

Note that if we were not using J's built in sort, we would probably want to use [[Counting_sort|bin sort]] here.

 

Anyways, we can test that they are indeed sorted properly:

 

=={{header|Logo}}==

make "colors {red white blue}

 

setitem :a :array item :b :array

setitem :b :array :temp

 

Test code:

make "list random_balls 10

] [dutch? :list]

print (sentence [Start list:] arraytolist :list)

print (sentence [Sorted:] arraytolist dutch :list)

 

<pre>Start list: white blue red red red white blue red red white

Sorted: red red red red red white white white blue blue</pre>

 

{{out}}

<pre>flagSort[{WHITE, RED, RED, WHITE, WHITE, BLUE, WHITE, BLUE, BLUE, WHITE, WHITE, BLUE}]

 

{RED, RED, WHITE, WHITE, WHITE, WHITE, WHITE, WHITE, BLUE, BLUE, BLUE, BLUE}</pre>

 

=={{header|PARI/GP}}==

A [[counting sort]] might be more appropriate here, but that would conceal the details of the sort.

if (a==b,

0

while(inorder(v), v=r(10));

v=vecsort(v,compare);

 

<pre>1</pre>

 

 

}

 

}

 

 

 

 

 

{{out}}

 

 

 

 

 

=={{header|PicoLisp}}==

(list

(def 'RED 1)

(prin "Sorted balls ")

(print S)

<pre>Original balls (RED BLUE WHITE BLUE BLUE RED WHITE WHITE WHITE) not sorted

Sorted balls (RED RED WHITE WHITE WHITE WHITE BLUE BLUE BLUE) are sorted</pre>

 

=={{header|Prolog}}==

Works with SWI-Prolog 6.1.11

===Prolog spirit===

length(L, N),

repeat,

 

is_dutch_flag_blue([]).

<pre> ?- dutch_flag(20).

[blue,white,white,blue,blue,blue,red,blue,red,blue,blue,blue,white,red,red,blue,blue,red,blue,red]

===Functional spirit===

Use of filters.

length(L, N),

 

 

is_dutch_flag_blue([]).

 

=={{header|Python}}==

===Python: Sorted===

The heart of the idiomatic Dutch sort in python is the call to function <code>sorted</code> in function <code>dutch_flag_sort</code>.

 

colours_in_order = 'Red White Blue'.split()

 

if __name__ == '__main__':

{{out|Sample output}}

<pre>Original Ball order: ['Red', 'Red', 'Blue', 'Blue', 'Blue', 'Red', 'Red', 'Red', 'White', 'Blue']

 

===Python: sum of filters===

 

Replace the function/function call dutch_flag_sort above, with dutch_flag_sort2 defined as:

def dutch_flag_sort2(items, order=colours_in_order):

'return summed filter of items using the given order'

return list(chain.from_iterable(filter(lambda c: c==colour, items)

 

Or equivalently using a list comprehension (though perhaps less clear):

'return summed filter of items using the given order'

Output follows that of the sorting solution above.

 

===Python: Construct from ball counts===

 

Replace the function/function call dutch_flag_sort above, with dutch_flag_sort3 defined as:

'counts each colour to construct flag'

Output follows that of the sorting solution above.

 

===Python: Explicit in-place sort===

 

colours_in_order = 'Red White Blue'.split()

 

if __name__ == '__main__':

Output follows that of the sorting solution above.

 

=={{header|REXX}}==

This version uses a version of a bin sort with counts, and has been generalized to allow any number of colors.

 

 

 

 

end /*k*/

countWords: procedure; parse arg ?,hay; s=1

number of colored balls generated = 15

 

 

 

 

 

 

 

 

end /*k*/

number of colored balls generated = 15

 

 

 

</pre>

 

=={{header|Ruby}}==

 

 

 

end

 

 

 

 

 

 

 

 

=={{header|Tcl}}==

This isn't very efficient in terms of the sorting itself (and it happens to use <code>lsearch</code> twice in the comparator!) but it is very simple to write like this.

proc dutchflagcompare {a b} {

set colors {red white blue}

} else {

puts "sort failed\n$sorted"

{{out}}

<pre>

red red red red red red red white white white white white white white white white blue blue blue blue

</pre>

 

=={{header|UNIX Shell}}==

{{works with|Bash}}

 

for (( i=0; i<${#COLORS[@]}; ++i )); do

eval ${COLORS[i]}=$i

done

echo "${a[@]}"

 

Test code:

balls=()

while (( ${#balls[@]} < len )) || dutch? "${balls[@]}"; do

echo "Initial list: ${balls[@]}"

balls=($(dutch "${balls[@]}"))

 

<pre>Initial list: blue blue red blue red blue blue white blue red

Sorted: red red red white blue blue blue blue blue blue</pre>