โปรแกรมค้นหาจำนวนองค์ประกอบในการเรียงสับเปลี่ยนทั้งหมดซึ่งเป็นไปตามเงื่อนไขที่กำหนดใน Python

สมมติว่าเรามีเซต A ซึ่งมีองค์ประกอบตั้งแต่ 1 ถึง n ทั้งหมด และ P(A) แสดงถึงการเรียงสับเปลี่ยนขององค์ประกอบทั้งหมดที่มีอยู่ใน A เราต้องหาจำนวนองค์ประกอบใน P(A) ที่ตรงตามเงื่อนไขที่กำหนด

สำหรับ i ทั้งหมดในช่วง [1, n], A[i] ไม่เหมือนกับ i
มีชุดของ k ดัชนี {i1, i2, ... ik} ซึ่ง A[ij] =ij+1 สำหรับ j

ดังนั้น หากอินพุตเป็น n =3 k =2 เอาต์พุตจะเป็น 0 เพราะ -

พิจารณา Array's เป็น 1 ที่จัดทำดัชนี เนื่องจาก N =3 และ K =2 เราสามารถหา A 2 ชุดที่ตรงตามคุณสมบัติแรก a[i] ≠ i นั่นคือ [3,1,2] และ [2,3,1] ตอนนี้เมื่อ K =2 เราก็มีองค์ประกอบดังกล่าวได้ 6 ตัว

[1,2], [1,3], [2,3], [2,1], [3,1], [3,2] ทีนี้ถ้าเราพิจารณาองค์ประกอบแรกของ

P(A) -> [3,1,2]

[1,2], A[1] ≠ 2
[1,3], A[1] =3 แต่ A[3] ≠ 1
[2,3], เอ[2] ≠ 3
[2,1], A[2] =1 แต่ A[1] ≠ 2
[3,1], A[3] =1 แต่ A[1] ≠ 3
[3,2], A[3] ≠ 2

P(A) -> [2,3,1]

[1,2], A[1] =2 แต่ A[2] ≠ 1
[1,3], A[1] ≠ 3
[2,3], A[2] =3 แต่ A[3] ≠ 3
[2,1], เอ[2] ≠ 1
[3,1], A[3] =แต่ A[1] ≠ 3
[3,2], A[3] ≠ 2

เนื่องจากไม่มีองค์ประกอบของ a ตรงตามคุณสมบัติข้างต้น จึงเป็น 0

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

ps :=การเรียงสับเปลี่ยนทั้งหมดของอาร์เรย์ที่มีองค์ประกอบอยู่ในช่วง [1, n]
ค :=0
สำหรับแต่ละ p ใน ps ทำ
- สำหรับแต่ละดัชนี i และค่า a ใน p ให้ทำ
  - ถ้า a เหมือนกับ i แล้ว
    - ออกมาจากวงจร
- มิฉะนั้น
  - สำหรับ j ในช่วง 0 ถึง n - 1 ทำ
    - ปัจจุบัน :=p[j]
    - cycle_length :=1
    - ในขณะที่กระแสไม่เหมือนกับ j ให้ทำ
      - ปัจจุบัน :=p[ปัจจุบัน]
      - cycle_length :=cycle_length + 1
    - ถ้า cycle_length เหมือนกับ k แล้ว
      - c :=c + 1
      - ออกมาจากวงจร
คืนค

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

import itertools

def solve(n, k):
   ps = itertools.permutations(range(n), n)
   c = 0
   for p in ps:
      for i, a in enumerate(p):
         if a == i:
            break
      else:
         for j in range(n):
            current = p[j]
            cycle_length = 1
            while current != j:
               current = p[current]
               cycle_length += 1
            if cycle_length == k:
               c += 1
               break
   return c

n = 3
k = 2
print(solve(n, k))

อินพุต

3, 2

โปรแกรมค้นหาจำนวนองค์ประกอบในการเรียงสับเปลี่ยนทั้งหมดซึ่งเป็นไปตามเงื่อนไขที่กำหนดใน Python

ตัวอย่าง

อินพุต

ผลลัพธ์