Tarkibga o'tish

Permutatsiyalar

Takrorlanmaydigan butun sonlar massivi berilgan. Uning barcha permutatsiyalarini toping.

Permutatsiya — elementlarning barcha mumkin bo'lgan tartiblashlari. n ta element uchun n! ta permutatsiya mavjud.

Kirish: [1, 2, 3]
Chiqish:
  [1, 2, 3]
  [1, 3, 2]
  [2, 1, 3]
  [2, 3, 1]
  [3, 1, 2]
  [3, 2, 1]

Kirish: [0, 1]
Chiqish:
  [0, 1]
  [1, 0]

Kirish: [1]
Chiqish: [[1]]

Asosiy g'oya: backtracking

Har permutatsiyani qurishda "keyingi pozitsiyaga qaysi element qo'yiladi?" degan qaror qabul qilinadi. Barcha mumkin bo'lgan tanlovlar tekshiriladi — bu backtracking.

Qaror daraxti [1, 2, 3] uchun:

                     []
          /           |          \
        [1]          [2]          [3]
       /   \        /   \        /   \
    [1,2] [1,3]  [2,1] [2,3]  [3,1] [3,2]
      |     |      |     |      |     |
  [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

Har bosqichda "hali ishlatilmagan" elementlardan biri tanlanadi, joriy permutatsiyaga qo'shiladi, rekursiya chaqiriladi, keyin bekor qilinadi.

Yondashuv 1: used massivi bilan

FUNCTION PERMUTE(nums)
    result  = bo'sh list
    current = bo'sh list
    used    = LENGTH(nums) ta FALSE qiymatdan iborat array
    BACKTRACK(nums, used, current, result)
    RETURN result

FUNCTION BACKTRACK(nums, used, current, result)
    IF LENGTH(current) = LENGTH(nums)
        result ga current ning nusxasini qo'sh
        RETURN

    FOR i = 0 DAN LENGTH(nums) - 1 GACHA
        IF used[i] = TRUE
            CONTINUE

        current ga nums[i] ni qo'sh     // tanlash
        used[i] = TRUE
        BACKTRACK(nums, used, current, result)
        current dan oxirgi elementni olib tashlash  // bekor qilish
        used[i] = FALSE

used[i] — i-element joriy permutatsiyada ishlatilganmi. Har rekursiv chaqiruvda ishlatilmagan elementlardan biri tanlanadi.

Bosqichma-bosqich dry run: [1, 2, 3]

BACKTRACK(current=[], used=[F,F,F])

  i=0 (nums[0]=1):
    current=[1], used=[T,F,F]
    BACKTRACK(current=[1], used=[T,F,F])

      i=0: used[0]=T, o'tkaziladi
      i=1 (nums[1]=2):
        current=[1,2], used=[T,T,F]
        BACKTRACK(current=[1,2])

          i=0: used, i=1: used
          i=2 (nums[2]=3):
            current=[1,2,3], used=[T,T,T]
            BACKTRACK → LENGTH=3=3: result ga [1,2,3]
            bekor: current=[1,2], used=[T,T,F]

        bekor: current=[1], used=[T,F,F]

      i=2 (nums[2]=3):
        current=[1,3], used=[T,F,T]
        BACKTRACK(current=[1,3])

          i=1 (nums[1]=2):
            current=[1,3,2] → result ga [1,3,2]
            bekor

        bekor: current=[1], used=[T,F,F]

    bekor: current=[], used=[F,F,F]

  i=1 (nums[1]=2):
    current=[2] → ... → [2,1,3], [2,3,1]

  i=2 (nums[2]=3):
    current=[3] → ... → [3,1,2], [3,2,1]

Yondashuv 2: almashtirish (swap) bilan

Har bosqichda start indeksidan boshlab elementlar navbati bilan start bilan almashtiriladi:

FUNCTION PERMUTE_SWAP(nums)
    result = bo'sh list
    BACKTRACK_SWAP(nums, 0, result)
    RETURN result

FUNCTION BACKTRACK_SWAP(nums, start, result)
    IF start = LENGTH(nums)
        result ga nums ning nusxasini qo'sh
        RETURN

    FOR i = start DAN LENGTH(nums) - 1 GACHA
        SWAP(nums[start], nums[i])           // tanlash
        BACKTRACK_SWAP(nums, start + 1, result)
        SWAP(nums[start], nums[i])           // bekor qilish

start pozitsiyasiga nums[i] qo'yiladi (almashtirish orqali). Keyin start+1 uchun rekursiya. Qaytganda almashtirish bekor qilinadi.

Bu used massivisiz xotirani tejaydi — O(1) qo'shimcha xotira (rekursiya stackidan tashqari).

Dry run [1, 2, 3], start=0:

i=0: SWAP(1,1)=[1,2,3], start=1
  i=1: SWAP(2,2)=[1,2,3], start=2
    i=2: SWAP(3,3)=[1,2,3] → [1,2,3] result ga
    SWAP qaytarish
  SWAP qaytarish: [1,2,3]
  i=2: SWAP(2,3)=[1,3,2], start=2
    → [1,3,2] result ga
    SWAP qaytarish: [1,2,3]
SWAP(1,1) qaytarish: [1,2,3]

i=1: SWAP(1,2)=[2,1,3], start=1
  → [2,1,3], [2,3,1] result ga
SWAP qaytarish: [1,2,3]

i=2: SWAP(1,3)=[3,2,1], start=1
  → [3,2,1], [3,1,2] result ga
SWAP qaytarish: [1,2,3]

Natija: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,2,1], [3,1,2] — tartib birinchi yondashuvdan farq qilishi mumkin, lekin barchasi to'g'ri.

Vaqt va xotira murakkabligi

Xususiyat Qiymat Izoh
Vaqt O(n × n!) n! permutatsiya, har biri O(n) nusxalash
Xotira O(n) Rekursiya chuqurligi + current/used

n! = 1×2×3×...×n. n=10 da 3 628 800 permutatsiya — amaliy chegaraga yaqin.

Edge case'lar

Bitta element. [1] → [[1]]. Rekursiya start=0 dan boshlanadi, darhol tugaydi.

Bo'sh massiv. [] → [[]] yoki [] (masala ta'rifiga qarab). Ko'pincha bo'sh permutatsiyalar to'plami [[]].

Ikkita element. [1, 2] → [[1,2], [2,1]].

Nol qiymatlar. Masalada takrorlanmaydigan elementlar deb kafolat berilgan. Takrorlanuvchi elementlar uchun alohida yondashuv kerak.

Note

Takrorlanuvchi elementlar bilan permutatsiyalar (Permutations II) uchun: used massivi bilan birgalikda IF i > 0 VA nums[i] = nums[i-1] VA used[i-1] = FALSE: CONTINUE sharti qo'shiladi. Bu duplikatlarni kesib tashlaydi.

Kengaytirilgan variant: tartibdagi keyingi permutatsiya

Berilgan permutatsiyaning leksikografik tartibdagi keyingi permutatsiyasini topish:

  1. Oxiridan nums[i] < nums[i+1] bo'lgan eng katta i topiladi.
  2. Oxiridan nums[i] < nums[j] bo'lgan eng katta j topiladi.
  3. nums[i] va nums[j] almashtiriladi.
  4. i+1dan keyin massiv teskari qilinadi.

Bu har qadamda faqat O(n) vaqt oladi.

Xulosa

Permutatsiyalar — backtracking ning klassik qo'llanishi. Har bosqichda ishlatilmagan element tanlanadi, rekursiya chaqiriladi, keyin bekor qilinadi.

Ikki yondashuv: used massivi (intuitiv, ko'proq xotira) va almashtirish (xotirani tejaydi). Ikkalasi ham O(n × n!) vaqt oladi — bu optimal, chunki n! ta natija chiqariladi va har biri O(n) yoziladi.