ลำดับที่เท่าไหร่

[gnopy]

ให้ A={0,1,2,3,4,5,...,n-1}และ B เป็นเซตที่เป็นสับเซตของ A โดยที่สมาชิกใน B มีค่าเริ่มจาก 0 และห่างกัน 1 เรียงกันจากน้อยไปหามาก เช่น B={0,1,2,3,4},B={0,1,2,3}
คำถามคือ ถ้าเรา ต้องการทราบว่าตัวเลขที่เกิดจากสมาชิกใน B 4 ตัวไม่ซ้ำกัน เป็น ลำดับที่เท่าไหร่ ของการสร้างตัวเลขเหล่านั้นโดยเลขจะเรียงจากน้อยไปมาก จะหาได้อย่างไร เช่น
B={0,1,2,3}
สร้าง ตัวเลขได้ตามเงื่อนไขคือ 0123,0132,0312,0321,...,3210 (มี 24 ตัว =n(B)!)
ถามว่า 2130 เป็นลำดับที่เท่าไหร่
ถ้า B={0,1,2,3,4,5,...,8} n(B)=9
ถามว่า 812354670 เป็นลำดับที่เท่าไหร่

มีสูตรในการหามั้ยครับ

[teamman]

สำหรับข้อ นี้นะครับ ผมไม่มีแนวคิดที่ดีเท่าไหร่นะครับ
ที่ผมคิดก็ประมาณว่า ใช้การไล่เอานะครับ
เริ่มจากอันแรก 2130 อยู่ตำแหน่งไหน
ผมก็คิดตำแหน่งก่อน ดึง 2130 ครับ
ตำแหน่งก่อนถึงก็จะมี
0_ _ _ = 6
1_ _ _ = 6
20_ _ = 2
210_ = 1
2130
ดังนั้นจะได้ว่า อยู่ตำแหน่งที่ 6+6+2+1+1 = 16
ครับ
ส่วนข้อ2 ผมก็คิดแบบนั่งไล่เหมือนกันครับ แต่ผมว่าน่าจะมีวิธีง่ายกว่านี้นะ
5555

[nooonuii]

ข้อความเดิมเขียนโดยคุณ gnopy

ให้ A={0,1,2,3,4,5,...,n-1}และ B เป็นเซตที่เป็นสับเซตของ A โดยที่สมาชิกใน B มีค่าเริ่มจาก 0 และห่างกัน 1 เรียงกันจากน้อยไปหามาก เช่น B={0,1,2,3,4},B={0,1,2,3}
คำถามคือ ถ้าเรา ต้องการทราบว่าตัวเลขที่เกิดจากสมาชิกใน B 4 ตัวไม่ซ้ำกัน เป็น ลำดับที่เท่าไหร่ ของการสร้างตัวเลขเหล่านั้นโดยเลขจะเรียงจากน้อยไปมาก จะหาได้อย่างไร เช่น
B={0,1,2,3}
สร้าง ตัวเลขได้ตามเงื่อนไขคือ 0123,0132,0312,0321,...,3210 (มี 24 ตัว =n(B)!)
ถามว่า 2130 เป็นลำดับที่เท่าไหร่
ถ้า B={1,2,3,4,5,...,9}
ถามว่า 812354670 เป็นลำดับที่เท่าไหร่

มีสูตรในการหามั้ยครับ

คำตอบจะอยู่ในรูป

$a_{n-1}(n-1)!+a_{n-2}(n-2)!+\cdots + a_11!+a_0 0!$

ลองหาดูว่า $a_{n-1},...,a_1,a_0$ สัมพันธ์กับตัวเลขที่เราจะหาอันดับอย่างไร

[teamman]

สำครับข้อ 2 นะครับผมได้คำตอบ เป็น 8(8!)+7!+(6!)+(5!)+2(4!)+(3!)+(2!)+1+1 ครับ
ไม่แน่ใจว่าถูกป่าวนะอิอิ

[gnopy]

ข้อความเดิมเขียนโดยคุณ nooonuii

คำตอบจะอยู่ในรูป

$a_{n-1}(n-1)!+a_{n-2}(n-2)!+\cdots + a_11!+a_0 0!$

ลองหาดูว่า $a_{n-1},...,a_1,a_0$ สัมพันธ์กับตัวเลขที่เราจะหาอันดับอย่างไร

พี่nooonuii เฉลยหน่อยครับ ยังหาความสัมพันธ์ไม่ได้เลย เช่นถ้า
n=4 จะได้เซตคือ {0,1,2,3}

แล้ว 0123 เนี่ย จะทำยังไงให้ได้เท่ากับ 1 เพราะมันเป็นลำดับที่ 1

[nooonuii]

เข้าใจว่ากำลังจะเขียนโปรแกรมอยู่ใช่มั้ยครับ

เพราะว่าวิธีนี้ถ้าเขียนเป็น algorithm น่าจะง่ายกว่า

สมมติว่า $B=\{0,1,2,3\}$

อยากทราบว่า $2130$ เป็นอันดับที่เท่าไหร่

เริ่มแรกให้ดูที่เลข $2$

เลขตัวนี้เป็นตัวเลขลำดับที่สามใน $B$

ดังนั้นตำแหน่งตัวเลขที่ขึ้นต้นด้วย $2$ แล้วต่อท้ายด้วยอีก 3 ตัวที่เหลือ จะเริ่มต้นที่ลำดับ

$(3-1) \cdot (4-1)!$ (ลองหาเหตุผลดูนะครับว่าทำไม)

ต่อไปขยับไปดูเลข $1$ ตอนนี้เราต้องโยนเลข $2$ ทิ้งไปเพราะเราใช้ตัวเลขได้ครั้งเดียวในวิธีเรียงสับเปลี่ยน

เลขที่เหลือที่เราต้องนำมาคิดคือ $0,1,3$

เลข $1$ เป็นตัวเลขลำดับที่สองในบรรดาเลขที่เหลืออยู่

ดังนั้นตำแหน่งตัวเลขที่ขึ้นต้นด้วย $1$ แล้วต่อท้ายด้วยอีก 2 ตัวที่เหลือ จะเริ่มต้นที่ลำดับ

$(2-1)\cdot (3-1)!$

ต่อไปก็โยน $1$ ทิ้งไป จะเหลือแค่ $0,3$

$3$ เป็นตัวเลขลำดับที่สองจากบรรดาเลขที่่เหลืออยู่

ดังนั้นตำแหน่งตัวเลขที่ขึ้นต้นด้วย $3$ แล้วต่อท้ายด้วยอีก 1 ตัวที่เหลือ จะเริ่มต้นที่ลำดับ

$(2-1)\cdot (2-1)!$

เหลือตัวเลขสุดท้ายคือ $0$

ไม่รู้จะจัดอันดับยังไงเพราะเหลืออยู่ตัวเดียว ก็ใส่อันดับหนึ่งให้มันไป

สรุปว่า $2130$ จะเป็นเลขลำดับที่ $2\cdot 3!+1\cdot 2!+1\cdot 1!+1\cdot 0!=16$

ถ้าหากเข้าใจวิธีคิดแล้วคิดว่าเขียน algorithm ได้ไม่ยากครับ

ลองเช็คดูกับตัวอื่นก็ได้ผลตรงกัน

$3210$ จะเป็นเลขลำดับที่ $3\cdot 3!+2\cdot 2!+1\cdot 1!+1\cdot 0!=24$

$0321$ จะเป็นเลขลำดับที่ $0\cdot 3!+2\cdot 2!+1\cdot 1!+1\cdot 0!=6$

$1302$ จะเป็นเลขลำดับที่ $1\cdot 3!+2\cdot 2!+0\cdot 1!+1\cdot 0!=11$

[gnopy]

ขอบคุณพี่ nooonuii นะครับ สุดท้ายผมก็ทำเหมือนอัลกอริธึมนี้แหละครับ ไม่ได้หาสูตรโดยตรง และก็ผ่านแล้วครับ

[TitanTS]

ข้อความเดิมเขียนโดยคุณ gnopy

B={0,1,2,3}
สร้าง ตัวเลขได้ตามเงื่อนไขคือ 0123,0132,0312,0321,...,3210 (มี 24 ตัว =n(B)!)
ถามว่า 2130 เป็นลำดับที่เท่าไหร่
ถ้า B={0,1,2,3,4,5,...,8} n(B)=9
ถามว่า 812354670 เป็นลำดับที่เท่าไหร่

ไปงงอยู่ตรงนี้อะครับ ตกลงมันผิดใช่ไหม