หน้าเว็บ

วันอาทิตย์ที่ 24 พฤษภาคม พ.ศ. 2558

ฝึก recursive ด้วยโจทย์ความน่าจะเป็น


       โจทย์นี้เป็นโจทย์ที่ผมใช้ฝึกวิธีคิด  การแก้ปัญหา  ซึ่งอาจมีคนคิด  หรือสร้าง tools สำเร็จรูปเอาไว้แล้ว  บางคนมาเห็นโพสต์นี้ อาจจะคิดว่าทำไมไม่ใช้เครื่องมือที่คนอื่นทำไว้แล้วล่ะ  จะมามัวเสียเวลาสร้างเองทำไม  ของคนอื่นอาจจะดีกว่าด้วยซ้ำ

        ครับ!!! ผมเคยได้ยินประโยคแบบนี้มานักต่อนักล่ะ  บางคนบอกว่าผมไม่รู้จักใช้เครื่องมือให้เกิดประโยชน์
        คุณกำลังเข้าใจผิดกับคำว่า  "การเลือกใช้เครื่องมือ"  กับ  "การฝึกทักษะการแก้ปัญหา"
ที่ผมเขียนเอง เพราะผมต้องการฝึก skill เพื่อให้เกิดความคล่องตัว เมื่อเราเจอโจทย์ปัญหาลักษณะนี้  เราจะแก้มันได้รึเปล่า ลองใช้ความคิดของเราดูสิ
        skill มันส่งต่อผ่านประสบการณ์กันไม่ได้  ต่อให้มีคนพยายามเล่าประสบการณ์ทั้งชีวิตของเขาให้คุณฟัง  คุณก็ทำแบบเขาไม่ได้ คุณต้องฝึก ฝึก ฝึก ลงมือทำด้วยตัวคุณเองครับ

ปัญหา

        โดยทั่วไป การหาความน่าจะเป็นหรือความเป็นไปได้ของสมาชิกทั้งหมดภายในเซต S ซึ่งมีสมาชิกจำนวน n ตัว
คุณจะต้องวนลูปทั้งหมด n รอบ และลึก n ชั้น ถึงจะได้ค่าทั้งหมดออกมา  เช่น

S = {'A', 'B', 'C'}
n = 3 ตัว
จำนวนความเป็นไปได้ทั้งหมดคือ 3 x 3 x 3 = 27 ค่า

การเขียนโปรแกรมแบบง่ายๆ จะได้
for (var i = 0; i < S.lenght; i++){
    for (var j = 0; j < S.lenght; j++){
        for (var k = 0; k < S.lenght; k++){
               print(S[i] + ',' + S[j] + ',' + S[k]);
        }
    }
}

A,A,A
A,A,B
A,A,C
A,B,A
A,B,B
...
...
...
C,B,C
C,C,A
C,C,B
C,C,C
แล้วถ้าเขาต้องการให้คุณเขียน code ที่รองรับ S ที่มี size ขนาดใดก็ได้ คุณจะเขียนยังไง?
แน่นอน loop ใช้ไม่ได้ล่ะ เพราะมัน fixed ตายตัว
แล้วอะไรที่เราเอามาใช้แทน loop ได้ แถมยังเป็นแบบ dynamic อีก

คำตอบคือ Recursive ครับ

code
function probabilityWalking(topElement, elements, index, callback){
    if (index < 0) {
        callback(topElement);
        return;
    }     

    for (var i=0; i < elements.length; i++) {
        probabilityWalking(
            (topElement ? (topElement + ',') : topElement) + elements[i],
            elements,
            index - 1,
            callback 
        );
    }
}
using
probabilityWalking('', ['A', 'B'], 1, function(el){
     console.log(el);     
});

A,A
A,B
B,A
B,B
probabilityWalking('', ['A', 'B', 'C'], 2, function(el){
     console.log(el);     
});

A,A,A
A,A,B
A,A,C
A,B,A
A,B,B
...
...
...
C,B,C
C,C,A
C,C,B
C,C,C
ตอนนี้ code เราสามารถหาความเป็นไปได้ทั้งหมดของ S ขนาดเท่าใดก็ได้ แล้วครับ :)

การนำแนวคิดไปประยุกต์ใช้
maven dependencies
<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-lang3</artifactId>
    <version>3.1</version>
    <type>jar</type>
</dependency>

<dependency>
    <groupId>junit</groupId>
    <artifactId>junit</artifactId>
    <version>4.10</version>
    <scope>test</scope>
</dependency>
Probability.java
package com.blogspot.na5cent.learning;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import org.apache.commons.lang3.StringUtils;

/**
 * @author redcrow
 */
public class Probability {

    private static interface Callback {

        void call(String element);
    }

    private final List<String> elements;
    private boolean distinct = false;
    private boolean unique = false;
    private Integer size;
    private Set<String> signatures;

    private Probability(List<String> elements) {
        this.elements = elements;
    }

    public static Probability ofElements(String... elements) {
        return ofElements(Arrays.asList(elements));
    }

    public static Probability ofElements(List<String> elements) {
        return new Probability(elements);
    }

    public Probability size(int size) {
        this.size = size;
        return this;
    }

    public Probability distinct() {
        this.distinct = true;
        return this;
    }

    public Probability unique() {
        this.unique = true;
        return this;
    }

    private Set<String> getSignatures() {
        if (signatures == null) {
            signatures = new HashSet<>();
        }

        return signatures;
    }

    private boolean contains(String str, String target) {
        if (!str.isEmpty()) {
            String[] els = StringUtils.split(str, ":");
            for (String el : els) {
                if (el.equals(target)) {
                    return true;
                }
            }
        }

        return false;
    }

    private String findSignature(String str) {
        String[] els = StringUtils.split(str, ":");
        Arrays.sort(els);
        return StringUtils.join(els, ":");
    }

    private boolean has(String element) {
        String signature = findSignature(element);
        if (getSignatures().contains(signature)) {
            return true;
        }

        getSignatures().add(signature);
        return false;
    }

    private void walking(String topElement, List<String> elements, int index, Callback callback) {
        if (index < 0) {
            if (unique && has(topElement)) {
                return;
            }

            callback.call(topElement);
            return;
        }

        for (String element : elements) {
            if (distinct && contains(topElement, element)) {
                continue;
            }

            walking(
                    (topElement.isEmpty() ? topElement : topElement + ":") + element,
                    elements,
                    index - 1,
                    callback
            );
        }
    }

    public List<String> find() {
        if (size == null) {
            size = elements.size();
        }

        final List<String> results = new ArrayList<>();
        walking("", elements, size - 1, new Callback() {

            @Override
            public void call(String element) {
                results.add(element);
            }
        });

        return results;
    }
}

ลองดูวิธีการเรียกใช้และผลลัพธ์ที่ Test

ProbabilityTest.java
package com.blogspot.na5cent.learning;

import java.util.Arrays;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;

/**
 * @author redcrow
 */
public class ProbabilityTest {

    @Test
    public void allOf2ElementsSize2() {
        List<String> probs = Probability
                .ofElements("A", "B")
                .find();

        List<String> results = Arrays.asList(
                "A:A",
                "A:B",
                "B:A",
                "B:B"
        );

        assertEquals(probs, results);
    }

    @Test
    public void allOf3ElementsSize3() {
        List<String> probs = Probability
                .ofElements("A", "B", "C")
                .find();

        List<String> results = Arrays.asList(
                "A:A:A",
                "A:A:B",
                "A:A:C",
                "A:B:A",
                "A:B:B",
                "A:B:C",
                "A:C:A",
                "A:C:B",
                "A:C:C",
                "B:A:A",
                "B:A:B",
                "B:A:C",
                "B:B:A",
                "B:B:B",
                "B:B:C",
                "B:C:A",
                "B:C:B",
                "B:C:C",
                "C:A:A",
                "C:A:B",
                "C:A:C",
                "C:B:A",
                "C:B:B",
                "C:B:C",
                "C:C:A",
                "C:C:B",
                "C:C:C"
        );

        assertEquals(probs, results);
    }

    @Test
    public void distinctOf2ElementsSize2() {
        List<String> probs = Probability
                .ofElements("A", "B")
                .distinct() //ตัด A:A กับ B:B ออก เพราะ A กับ B ซ้ำกัน 2 ตัว
                .find();

        List<String> results = Arrays.asList(
                "A:B",
                "B:A"
        );

        assertEquals(probs, results);
    }

    @Test
    public void distinctOf3ElementsSize3() {
        List<String> probs = Probability
                .ofElements("A", "B", "C")
                .distinct()
                .find();

        List<String> results = Arrays.asList(
                "A:B:C",
                "A:C:B",
                "B:A:C",
                "B:C:A",
                "C:A:B",
                "C:B:A"
        );

        assertEquals(probs, results);
    }

    @Test
    public void distinctOf4ElementsSize2() {
        List<String> probs = Probability
                .ofElements("A", "B", "C", "D")
                .distinct()
                .size(2)
                .find();

        List<String> results = Arrays.asList(
                "A:B",
                "A:C",
                "A:D",
                "B:A",
                "B:C",
                "B:D",
                "C:A",
                "C:B",
                "C:D",
                "D:A",
                "D:B",
                "D:C"
        );

        assertEquals(probs, results);
    }

    @Test
    public void uniqueOf2ElementsSize2() {
        List<String> probs = Probability
                .ofElements("A", "B")
                .unique()
                .find();

        List<String> results = Arrays.asList(
                "A:A",
                "A:B",
                "B:B"
        );

        assertEquals(probs, results);
    }

    @Test
    public void uniqueOf3ElementsSize3() {
        List<String> probs = Probability
                .ofElements("A", "B", "C")
                .unique()
                .find();

        List<String> results = Arrays.asList(
                "A:A:A",
                "A:A:B",
                "A:A:C",
                "A:B:B",
                "A:B:C",
                "A:C:C",
                "B:B:B",
                "B:B:C",
                "B:C:C",
                "C:C:C"
        );

        assertEquals(probs, results);
    }

    @Test
    public void uniqueAndDistinctOf2ElementsSize2() {
        List<String> probs = Probability
                .ofElements("A", "B")
                .distinct() //ตัด A:A กับ B:B ออก เพราะ A กับ B ซ้ำกัน 2 ตัว
                .unique() //A:B กับ B:A ถือเป็นตัวเดียวกัน แค่สลับตำแหน่ง
                .find();

        List<String> results = Arrays.asList(
                "A:B"
        );

        assertEquals(probs, results);
    }

    @Test
    public void uniqueAndDistinctOf3ElementsSize3() {
        List<String> probs = Probability
                .ofElements("A", "B", "C")
                .distinct()
                .unique()
                .find();

        List<String> results = Arrays.asList(
                "A:B:C"
        );

        assertEquals(probs, results);
    }

    @Test
    public void uniqueAndDistinctOf3ElementsSize2() {
        List<String> probs = Probability
                .ofElements("A", "B", "C")
                .distinct()
                .unique()
                .size(2)
                .find();

        List<String> results = Arrays.asList(
                "A:B",
                "A:C",
                "B:C"
        );

        assertEquals(probs, results);
    }

    @Test
    public void uniqueAndDistinctOf4ElementsSize2() {
        List<String> probs = Probability
                .ofElements("A", "B", "C", "D")
                .distinct()
                .unique()
                .size(2)
                .find();

        List<String> results = Arrays.asList(
                "A:B",
                "A:C",
                "A:D",
                "B:C",
                "B:D",
                "C:D"
        );

        assertEquals(probs, results);
    }

    @Test
    public void uniqueAndDistinctOf4ElementsSize3() {
        List<String> probs = Probability
                .ofElements("A", "B", "C", "D")
                .distinct()
                .unique()
                .size(3)
                .find();

        List<String> results = Arrays.asList(
                "A:B:C",
                "A:B:D",
                "A:C:D",
                "B:C:D"
        );

        assertEquals(probs, results);
    }
}
code นี้เป็นส่วนนึงของโจทย์ที่ผมกำลังแก้อยู่ครับ โจทย์มีอยู่ว่า

ให้เขียนโปรแกรมเพื่อหาสมการทั้งหมดที่เป็นไปได้ โดยให้เรา
1. ใส่คำตอบที่อยากจะได้ลงไป
2. ใส่ตัวเลขอะไรก็ได้ กี่ตัวก็ได้ลงไป (ในที่นี้คือ S)
3. ใส่ operators + หรือ - หรือ * หรือ / ลงไปกี่ตัวก็ได้ ใน 4 ตัวนี้
แล้วให้โปรแกรมคืนค่าสมการที่เกิดจากการป้อน input ข้อ 1- 3 ทั้งหมดออกมาครับ

น่าสนุกน่ะ
ตอนนี้ผมเหลือเงื่อนไขวงเล็บทั้งหมดที่เป็นไปได้  ตามจำนวนสมาชิกใน S ครับ
ยังคิดไม่ออก ฮ่าๆๆๆ

1 ความคิดเห็น: