สร้างการเรียงสับเปลี่ยนด้วย Javascript

ไปเจอคำถามน่าสนใจใน Blognone forum ว่าจะเขียนโปรแกรมแก้ปัญหา Zebra Puzzle (ปัญหาที่มันบอกว่ามีคนหลายชาติ เลี้ยงสัตว์หลายแบบ บ้านหลายสี บ้านคนนั้นติดคนนี้ น่ะ) ยังไง? ตอนสมัยเรียนรู้สึกเหมือนเคยแก้ปัญหาอะไรทำนองนี้แต่ใช้ Prolog ทำ ถ้าจะเอาภาษา Imperative บ้านๆแบบ Python หรือ C# ทำจะได้มั้ย?

ผมเข้าใจว่า Prolog เองมันก็มีการทำ search หา solution ที่เป็นไปได้ แล้วมีการทำพวก branch & bound หรือ track back เวลา solution มันผิดอะไรแบบนี้เหมือน (ไม่รู้ใช้ศัพท์ถูกป่าว มันนานมาแล้ว – -‘a) ครั้งนี้กะว่าจะลองใช้ Javascript เขียน

วิธีที่อยากทำคือจะวนไปตามรูปแบบ solution ทั้งหมดที่เป็นไปได้แล้ว check กับ constraints ของโจทย์ทีละตัวเลย ปัญหาแรกที่เจอคือจะ generate solution ที่เป็นไปได้ออกมายังไง?? อันนี้ต้องใช้ Permutation

Permutation ทั้งหมดของ [1,2,3] มี 3! แบบ = 6 แบบ ได้แก่ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

ถ้ามี list มาให้อันนึง จะวนหา Permutation ทั้งหมด Wikipedia แบบให้ทำแบบนี้

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

  1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
  2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
  3. Swap a[k] with a[l].
  4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

เขียนออกมาเป็น Javascript .. ผมทำไว้เป็น Module

/////////////////////////////////////////////
// Permutation Generator
// - generate all permutation of given string
// array
// - Natthawut Kulnirundorn <m3rlinez at email by google>
// http://www.solidskill.net 10 July 2011
/////////////////////////////////////////////

var PermutationGenerator = (function () {
var self = {};

// Get start sequence of given array
self.getStartSequence = function (list) {
return list.slice(0).sort();
};

// Get next sequence from given array
// Ref: http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations
self.getNextSequence = function (list) {
// Make clone
var a = list.slice(0);

//The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
// 1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
var k = -1;
for (var i = 0; i < a.length - 1; ++i) {
if (a[i] < a[i + 1]) { k = i; }
}
if (k == -1) return null; // means this is the last one

// 2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
var l = -1;
for (var i = 0; i < a.length; ++i) {
if (a[k] < a[i]) { l = i };
}
if (l == -1) return null; // impossible

// 3. Swap a[k] with a[l].
var tmp = a[k]; a[k] = a[l]; a[l] = tmp;

// 4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
var next = a.slice(0, k + 1).concat(a.slice(k + 1).reverse());

return next;
};

return self;
} ());

แถม test cases ให้เป็นวิธีใช้
/////////////////////////////////////////////
// Test Cases
/////////////////////////////////////////////

var PermutationGeneratorTest = (function () {
var self = {};

function getStartSequence_Test1() {
var a = ['red', 'white', 'green', 'yellow', 'blue'];
var res = PermutationGenerator.getStartSequence(a);
log('input = ' + a);
log('output = ' + res);
}

function generateSequence(list) {
var current = PermutationGenerator.getStartSequence(list);
var count = 1;
log('start = ' + current);
while (true) {
current = PermutationGenerator.getNextSequence(current);
if (current == null) { break; }
log('next' + (++count) + ' = ' + current);
}
}

function getNextSequence_TestNormal() {
generateSequence(['English', 'Spanish', 'Japanese']);
}

function getNextSequence_TestEmpty() {
generateSequence([]);
}

function getNextSequence_TestRepeat() {
generateSequence(['gant', 'gant', 'korkore', 'jan']);
}

self.runTests = function () {
log("=== getStartSequence 1 ===");
getStartSequence_Test1();
log("=== getNextSequence Normal ===");
getNextSequence_TestNormal();
log("=== getNextSequence Empty ===");
getNextSequence_TestEmpty();
log("=== getNextSequence Repeat ===");
getNextSequence_TestRepeat();
};

return self;
} ());

ตัวอย่างเต็มๆผมทิ้งไว้ที่ http://www.solidskill.net/ZebraPuzzle.htm

ส่วนอันนี้เป็นคำตอบที่ตอบใน forum .. เผื่อว่า Blognone ทำกระมุ้หายคงเสียดาย พิมพ์ตั้งนาน 😛

อาจารย์ให้โจทย์ได้น่าสนใจมากครับ ผมเห็นแล้วอยากทำไปด้วยเลย ลองทำดูเล่นๆเป็น Javascript ใช้เวลาไปมากพอสมควร

เวลาทำโจทย์แนวนี้โดยใช้ดินสอกระดาษ เราก็จะพยายามสร้างคำตอบที่เป็นไปได้โดยดูจาก constraints ที่โจทย์บอก ทำผิดก็ลบใหม่แล้วสลับโน่นเปลี่ยนนั่นเปลี่ยนนี่ไปเรื่อยๆให้สอดคล้องกับ constraints จนได้คำตอบ .. แต่สิ่งที่ยากคือจะเอาวิธีที่กล่าวมานี้เปลี่ยนมาเป็น code ได้ยังไง??

สิ่งแรกที่ต้องทำคือ กำหนดรูปแบบของคำตอบที่เราต้องการ ตัวอย่างอันนี้กำหนดให้อยู่ในรูป list ของ list เช่น

[[1,2,3,4,5], [yellow,blue,red,white,green], [Norwegian,Italian,English,Spanish,Japanese], [fox,horse,snails,dog,zebra], [water,tea,milk,orange juice,coffe], [diplomat,physician,photographer,violinist,painter]]

list ย่อยตัวแรกจะบอกตำแหน่งของบ้าน ตัวต่อมาบอกสีบ้าน ตัวต่อมาบอกสัญชาติ และอื่นๆ ตามลำดับ จากตัวอย่างจะบอกว่าบ้านหลังแรกสีเหลือง มีชาว Norwegian บ้านหลังที่ 3 มีชาว Italian เลี้ยงหอยทาก เป็นต้น จากรูปแบบคำตอบแบบนี้และข้อมูลที่โจทย์ให้มา เราจะต้องหาคำตอบที่ถูกต้องจากคำตอบที่เป็นไปได้ทั้งหมด (5!)^5 = 24,883,200,000 แบบ (ไม่ต้องยกกำลัง 6 เพราะจริงๆแล้ว list ย่อยตัวแรกคือตำแหน่งนั้น เรา fixed ไว้เลย)

ทำแบบตรงไปตรงมา .. เราก็ generate คำตอบที่เป็นไปได้ทั้งหมดออกมา แล้วเอามาตรวจสอบกับ constraints ว่าผ่านทุก constraints หรือไม่ หลังจากตรวจสอบแล้วก็จะเหลือแค่คำตอบที่สอดคล้องกับ constraints ทั้งหมด ถ้าลองทำกับโจทย์ข้อนี้จะพบว่ามันเหลือแค่คำตอบเดียว (จากทั้งหมด 25,000 ล้านแบบ) ถ้าลองเอา constraint ออกซักตัวจะเห็นได้ว่ามีตำตอบออกมาเพิ่มหลายคำตอบ

วิธี generate คำตอบทำได้ด้วยการหา permutation ทั้งหมดที่เป็นไปได้ ยกตัวอย่างเช่น [1,2,3] มี permutation 3! =6 แบบ คือ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] .. อัลกอริทึมสำหรับการทำดูได้ใน http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations

แต่ถ้าเราจะ generate คำตอบที่เป็นได้ไปได้ออกมาทั้ง 25,000 ล้านแบบแล้ว ตรวจสอบทุกแบบอาจจะใช้เวลามาก จริงๆแล้วเราสามารถตัดคำตอบที่เป็นไปไม่ได้ออกได้ตั้งแต่ตอน generate เลย เช่นมี constraint ตัวนึงบอกว่าบ้านหลังสีเขียวอยู่ถัดจากบ้านหลังสีขาว ดังนั้นระหว่างเรา generate สีบ้าน เราก็ตัดเคสอื่นๆที่ไม่สอดคล้องกับ constraint ตัวนี้ออกไปซะ ก็จะลดเวลาที่ใช้ลงไปได้มาก (pruning)

ที่ผม implement เป็น Javascript ลองเข้าไปดู (view source) ได้ที่ http://www.solidskill.net/ZebraPuzzle.htm ถ้าเข้าใจหลักการแล้วจะ implement เป็น Python หรือภาษาอื่นก็ไม่น่าจะลำบาก

ผมเข้าใจว่าถ้าเป็นวิชา Discrete Mathematics อาจารย์คงอยากให้หัดทำ permutation แหละ คงไม่ได้ต้องการให้ใช้เทคนิคยากๆจาก AI หรืออย่างอื่น

Leave a Reply

Your email address will not be published. Required fields are marked *