ISourceCode

Make the frequent cases fast and the rare case correct

Dutch National Flag Problem – Python

The Dutch national flag problem is a famous computer science related programming problem proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors : Red, White and Blue. Given balls of these three colors arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of same color are together and their collective color groups are in the correct order – Wikipedia

The Problem can be reconstructed for a given list consisting 0s, 1s and 2s write a function thats displays 0s first, then 1s and rest of the 2s in last.

0 – Red
1 – White
2 – Blue

def DNF(input,length):
        high = length - 1
        p = 0
        i = 0
        while i <= high:
                if input[i] == 0:
                        input[i],input[p]=input[p],input[i]
                        p = p+1
                        i = i+1
                elif input[i] == 2:
                        input[i],input[high]=input[high],input[i]
                        high = high-1
                else:
                        i = i+1
input = [0,1,2,2,1,0]
print "input: ", input
DNF(input,len(input))
print "output: ", input

OUTPUT:

~/DNF$ python dnf.py
input: [0, 1, 2, 2, 1, 0]
output: [0, 0, 1, 1, 2, 2]

Further reading : Article from Monash

DNF algorithm can be used in Quicksort to partition the elements. DNF algorithm makes O(n) moves and examinations.

3 responses to “Dutch National Flag Problem – Python

  1. ethan November 30, 2012 at 5:45 am

    test [1,2,0], then u see the bug

    change to while i <= high:

    good luck

  2. Using less Swaps December 26, 2015 at 11:32 am

    def DNF(input, length, Swaps=0):
    high = length – 1
    p = 0
    i = 0
    while i <= high:
    if input[i] == 0:
    if input[i]==input[p]:
    p+=1
    i+=1
    else:
    input[i],input[p]=input[p],input[i]
    p = p+1
    i = i+1
    Swaps+=1
    elif input[i] == 2:
    if input[i]==input[high]:
    high-=1
    else:
    input[i],input[high]=input[high],input[i]
    high = high-1
    Swaps+=1
    else:
    i = i+1
    print "Swaps",Swaps

    input = [1,1,0,2,2]
    DNF(input,len(input))
    print input

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: