說明
三色旗的問題最早由E.W.Dijkstra所提出，他所使用的用語為Dutch Nation Flag(Dijkstra為荷蘭人)，而多數的作者則使用Three-Color Flag來稱之。假設有一條繩子，上面有紅、白、藍三種顏色的旗子，起初繩子上的旗子顏色並沒有順序，您希望將之分類，並排列為藍、白、紅的順序，要如何移動次數才會 最少，注意您只能在繩子上進行這個動作，而且一次只能調換兩個旗子。
解法
在一條繩子上移動，在程式中也就意味只能使用一個陣列，而不使用其它的陣列來作輔助，問題的解法很簡單，您可以自己想像一下在移動旗子，從繩子開頭進 行，遇到藍色往前移，遇到白色留在中間，遇到紅色往後移，如下所示：
- 如果圖中W所在的位置為白色，則W+1，表示未處理的部份移至至白色群組。
- 如果W部份為藍色，則B與W的元素對調，而B與W必須各+1，表示兩個群組都多了一個元素。
- 如果W所在的位置是紅色，則將W與R交換，但R要減1，表示未處理的部份減1。
注意B、W、R並不是三色旗的個數，它們只是一個移動的指標；什麼時候移動結束呢？一開始時未處理的R指標會是等於旗子的總數，當R的索引數減至少於 W的索引數時，表示接下來的旗子就都是紅色了，此時就可以結束移動，如下所示：
如果可以使用雙向鏈結的話，則B可以再省去，在W遞增時，若遇到藍色，則將藍色移至鏈結前端且W+1，若遇到白色則W+1，若遇到紅色，則將紅色移至 鏈結尾端且R-1。
演算法
Procedure MOVE(Flags[])
w = 0
b = 0
r = LENGTH(Flags) - 1
WHILE(Flags[w] == 'B' && w < LENGTH(Flags))
b = b + 1
w = w + 1
WHILE(Flags[r] == 'R' && r > 0)
r = r - 1
WHILE(w <= r)
IF(Flags[w] == 'W')
w = w + 1
ELSE IF(Flags[w] == 'B')
SWAP(Flags[], b, w)
b = b + 1
w = w + 1
ELSE
SWAP(Flags[], r, w)
r = r - 1
實作：Toy C Java
Python Scala
Ruby JavaScript
Haskell Prolog
def adjust(flags) {
b = 0
w = 0
r = flags.length() - 1
while flags.get(w) == 'B' and w < flags.length() {
w += 1
}
while flags.get(r) == 'R' and r > 0 {
r -= 1
}
while w <= r {
switch flags.get(w) {
case 'W'
w += 1
case 'B'
flags.swap(b, w)
w += 1
b += 1
default
flags.swap(r, w)
r -= 1
}
}
return flags
}
flags = 'RWBBWRWR'.split('')
println(adjust(flags))#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SWAP_FLAGS(x, y) { char temp; \
temp = flags[x]; \
flags[x] = flags[y]; \
flags[y] = temp; }
void printFlags(char* flags) {
int i;
for(i = 0; i < strlen(flags); i++) {
printf("%c ", flags[i]);
}
printf("\n");
}
void adjust(char* flags) {
int w = 0;
int b = 0;
int r = strlen(flags) - 1;
while(flags[w] == 'B' && w < strlen(flags)) { b++; w++; }
while(flags[r] == 'R' && r > 0) { r--; }
while(w <= r) switch(flags[w]) {
case 'W':
w++;
break;
case 'B':
SWAP_FLAGS(b, w);
b++; w++;
break;
case 'R':
SWAP_FLAGS(r, w);
r--;
}
}
int main() {
char flags[] = {'R', 'W', 'B', 'W', 'W',
'B', 'R', 'B', 'W', 'R', '\0'};
printFlags(flags);
adjust(flags);
printFlags(flags);
return 0;
}
import java.util.*;
public class Flags {
private static void swap(char[] arr, int x, int y) {
char tmp = arr[x]; arr[x] = arr[y]; arr[y] = tmp;
}
public static String adjust(String flags) {
char[] fs = flags.toCharArray();
int b = 0, w = 0, r = fs.length - 1;
while(fs[w] == 'B' && w < fs.length) { b++; w++; }
while(fs[r] == 'R' && r > 0) { r--; }
while(w <= r) switch(fs[w]) {
case 'W':
w++;
break;
case 'B':
swap(fs, b, w);
b++; w++;
break;
case 'R':
swap(fs, r, w);
r--;
}
return new String(fs);
}
public static void main(String[] args) {
System.out.println(adjust(args[0]));
}
}def adjust(flags):
w = 0
r = len(flags) - 1
while flags[w] == "B" and w < len(flags):
w += 1
while flags[r] == "R" and r > 0:
r -= 1
while w <= r:
if flags[w] == "W":
w += 1
elif flags[w] == "B":
flags.insert(0, flags.pop(w))
w += 1
elif flags[w] == "R":
flags.append(flags.pop(w))
r -= 1
return flags
flags = list(input("輸入三色旗順序（ex. RWBBWRWR）："))
flags = adjust(flags)
print("移動順序後：", str(flags))def adjust(flags: List[Char]) = {
def categorize(bw: List[Char], remain: List[Char],
r: List[Char]): List[Char] = remain match {
case Nil => bw ++ r
case x::xs => x match {
case 'W' => categorize(bw ++ List(x), xs, r)
case 'B' => categorize(x::bw, xs, r)
case 'R' => categorize(bw, xs, x::r)
}
}
categorize(Nil, flags, Nil)
}
print("輸入三色旗順序（ex. RWBBWRWR）：")
adjust(readLine.toList).foreach(print)
# encoding: big5
def adjust(flags)
w = 0
r = flags.length - 1
while flags[w] == "B" && w < r
w += 1
end
while flags[r] == "R" && r > 0
r -= 1
end
while w <= r
case flags[w]
when "W"
w += 1
when "B"
flags.insert(0, flags.slice!(w))
w += 1
when "R"
flags << flags.slice!(w)
r -= 1
end
end
flags
end
print "輸入三色旗順序（ex. RWBBWRWR）："
flags = gets.chomp!
flags = adjust(flags)
print "移動順序後：#{flags} \n"
function adjust(flags) {
var fs = flags.split("");
var w = 0;
var r = fs.length - 1;
while(fs[w] === 'B' && w < fs.length) { w++; }
while(fs[r] === 'R' && r > 0) { r--; }
while(w <= r) switch(fs[w]) {
case 'W':
w++;
break;
case 'B':
fs.unshift(fs.splice(w, 1));
w++;
break;
case 'R':
fs.push(fs.splice(w, 1));
r--;
}
return fs.join("");
}
print(adjust("RWBWRWBW").toString());
adjust flags = categorize [] flags []
where categorize bw [] r = bw ++ r
categorize bw (x:xs) r = case x of
'W' -> categorize (bw ++ [x]) xs r
'B' -> categorize (x:bw) xs r
'R' -> categorize bw xs (x:r)
main = print \$ adjust "WBRRWBWRBWW"
categorize(BW, [], R, BWRFlags) :- append(BW, R, BWRFlags).
categorize(BW, [w|T], R, BWRFlags) :- append(BW, [w], BWFlags),
categorize(BWFlags, T, R, BWRFlags).
categorize(BW, [b|T], R, BWRFlags) :-
categorize([b | BW], T, R, BWRFlags).
categorize(BW, [r|T], R, BWRFlags) :- append(R, [r], RFlags),
categorize(BW, T, RFlags, BWRFlags).
adjust(Flags, BWRFlags) :- categorize([], Flags, [], BWRFlags).
main(_) :-
adjust([w, b, r, r, w, b, w, r, b, w, w], BWRFlags),
writef("%p\n", [BWRFlags]).