Algo Visualizedდაიწყე სწავლა

ქვესიმრავლეებისა და გადანაცვლებების გენერაცია

რომელი ნივთები ეტევა ბიუჯეტში? გაჩერებების რომელი რიგია უმოკლესი? როცა შემავალი მონაცემები მცირეა, ყველაზე საიმედო პასუხი ყველა ვარიანტის გადარჩევაა, რეკურსია კი მათ ჩამოთვლას დაახლოებით ათ სტრიქონში გაძლევს.

საშუალო⏱ 12 წთ

←ეყრდნობა

0რეკურსია და გამოძახებათა სტეკიქვესიმრავლეების გენერაცია ორად განშტოებადი რეკურსიაა: ავიღოთ ელემენტი თუ გამოვტოვოთ.0სირთულე და ზრდის ტემპი2ⁿ ქვესიმრავლე და n! გადანაცვლება აჩვენებს, რა სწრაფად ფეთქდება ექსპონენციალური ზრდა.

გზას უხსნის→

4უკუსვლა და მოკვეთა: N ლაზიერიუკუსვლა იგივე გენერაციაა, რომელიც განშტოებას მაშინვე ტოვებს, როგორც კი წესი ირღვევა.5ხეები: ცნებები, თვისებები, შემოვლებისრული გადარჩევის გადაწყვეტილებების ხე უკვე ხე იყო; ახლა მის ნაწილებს სახელს ვარქმევთ.7ხარბი იდეა და როდის ცდებასრული გადარჩევა საზომია: ხარბი სწორია მხოლოდ მაშინ, თუ ყველაფრის ცდას ემთხვევა.9ბიტური ოპერაციებიn ელემენტის ქვესიმრავლე n-ბიტიანი რიცხვია; 0-დან 2ⁿ − 1-მდე დათვლა ყველას ჩამოთვლის.10დპ-ის საფუძვლები: მემოიზაცია და ცხრილიდპ არის სრული გადარჩევა პლუს მეხსიერება.100-1 ზურგჩანთის ამოცანაზურგჩანთის დპ 2ⁿ ქვესიმრავლის ცდას ცვლის ერთი „ავიღოთ თუ არა“ გადაწყვეტილებით თითო უჯრაში.10უდიდესი საერთო ქვემიმდევრობაქვემიმდევრობა პოზიციების ქვესიმრავლეა; უსქ მათ ყველას არ ცდის.
1ისწავლე2ითამაშე3შეამოწმე4ივარჯიშე
01

ისწავლე

იდეა, მექანიზმი და ფასი.

01ყოველი ქვესიმრავლე გადაწყვეტილებების გზაა

{1, 2, 3}-ის ქვესიმრავლის ასაგებად ყოველ ელემენტზე ერთი გადაწყვეტილება მივიღოთ: ავიღოთ თუ არ ავიღოთ. სამი „კი/არა“ გადაწყვეტილება იძლევა 2 · 2 · 2 = 8 ქვესიმრავლეს. დავხატოთ ისინი ორობით ხედ: ყოველი დონე ერთ ელემენტზე წყვეტს, ყოველი გზა სათავიდან ფოთლამდე ერთი ქვესიმრავლეა.

რეკურსია ამ ხეს პირდაპირ შემოივლის:

  • search(k): თუ k == n, დავბეჭდოთ მიმდინარე ქვესიმრავლე;
  • წინააღმდეგ შემთხვევაში გამოვიძახოთ search(k+1) a[k]-ის გარეშე;
  • შემდეგ push_back(a[k]), გამოვიძახოთ search(k+1) და pop_back().

pop_back() აუცილებელია: ის აუქმებს არჩევანს, რომ გამომძახებელმა ქვესიმრავლე ზუსტად ისეთი დაიბრუნოს, როგორიც იყო. ყოველი ფოთოლი ერთხელ ინახულება, ამიტომ ყოველი ქვესიმრავლე ზუსტად ერთხელ იბეჭდება.

−1+1−2+2−2+2−3+3−3+3−3+3−3+3∅{3}{2}{2,3}{1}{1,3}{1,2}{1,2,3}3 გადაწყვეტილება → 2³ = 8 ფოთოლიარ ავიღოთავიღოთ
წყვეტილი წიბო ელემენტს არ იღებს, უწყვეტი იღებს. ფოთლები 8 ქვესიმრავლეა.

02ქვესიმრავლეები ბიტური ნიღბებით

არსებობს უფრო მოკლე გზაც. დავწეროთ რიცხვი 0-დან 2ⁿ − 1-მდე ორობითად: ბიტი i გვეუბნება, ავიღეთ თუ არა a[i]. 0-დან 2ⁿ − 1-მდე თვლა ყოველ ქვესიმრავლეს ზუსტად ერთხელ ჩამოთვლის, რეკურსიის გარეშე:

  • for (int mask = 0; mask < (1 << n); mask++)
  • for (int i = 0; i < n; i++) if (mask >> i & 1) …

n = 3-ისთვის ნიღაბი 5 = 101₂ ნიშნავს {a, c}-ს, ნიღაბი 7 = 111₂ კი მთელი სიმრავლეა.

ბიტური ნიღბები მოსახერხებელია, როცა ქვესიმრავლის კომპაქტურად შენახვაც გინდა, მასივის ინდექსად გამოყენება ან ქვესიმრავლეების &-ითა და |-ით გაერთიანება. მოგვიანებით ბიტური დინამიური პროგრამირება სწორედ ამ იდეაზე აშენდება. რეკურსიული ვერსია ჯობია, როცა ადრე გაჩერება ან განშტოებების გამოტოვება გინდა, როგორც ამას უკუსვლა გააკეთებს.

რიცხვი 0…2ⁿ−1 = ქვესიმრავლე: ბიტი i = 1 ⇔ ავიღეთ a[i]0000∅1001{a}2010{b}3011{a,b}4100{c}5101{a,c}6110{b,c}7111{a,b,c}for (mask = 0; mask < (1<<n); mask++) if (mask >> i & 1) …

03გადანაცვლებები: რიგს მნიშვნელობა აქვს

გადანაცვლება ყოველ ელემენტს ერთხელ იყენებს, რაღაც რიგით. ახლა ხე სხვაგვარია: პირველ დონეზე n არჩევანია, შემდეგზე n − 1 (ყველა ჯერ გამოუყენებელი ელემენტი) და ა.შ., ამიტომ ფოთოლი n · (n−1) · … · 1 = n!-ია.

რეკურსიული შაბლონი იგივეა, „აირჩიე, ჩაუღრმავდი, გააუქმე“:

  • ვინახავთ used[] მასივს და მიმდინარე მიმდევრობას;
  • ყოველ დონეზე ყოველი x-ისთვის, რომლისთვისაც !used[x]: მოვნიშნავთ, ბოლოში მივუწერთ, ჩავუღრმავდებით, შემდეგ წავშლით და მონიშვნას მოვხსნით.

C++-ში შეგიძლია მასივი დაალაგო და გამოიყენო do { … } while (next_permutation(a.begin(), a.end()));, რომელიც ყველა გადანაცვლებას ლექსიკოგრაფიული რიგით გაივლის და განმეორებად მნიშვნელობებსაც სწორად ამუშავებს.

იგივე შაბლონი აგენერირებს წყობებს (k-ელემენტიან ქვესიმრავლეებს), ანბანზე აგებულ სტრიქონებს და ბევრ სხვა „ყველა შესაძლო“ ობიექტს.

გადანაცვლებები: 3 · 2 · 1 = 3! = 6 ფოთოლი231233213213213312311231221321123

04რამდენად დიდი შეიძლება იყოს n?

სრული გადარჩევა თავისი აგებულებით სწორია, ამიტომ ერთადერთი კითხვა დროა. ტიპური შემმოწმებელი წამში დაახლოებით 10⁸ მარტივ ოპერაციას ასრულებს. შევადაროთ:

  • 2²⁰ ≈ 10⁶: 20 ელემენტის ქვესიმრავლეები მყისიერია; 2³⁰ ≈ 10⁹ უკვე ნელია;
  • 10! ≈ 3.6 · 10⁶ კარგია; 12! ≈ 4.8 · 10⁸ ზღვარზეა; 15! უიმედოა.

ამიტომ შეზღუდვა n ≤ 20 ქვესიმრავლეებზე მიგვანიშნებს, n ≤ 10 კი გადანაცვლებებზე. რამის დაპროექტებამდე შეზღუდვები წაიკითხე.

თუ უხეში გადარჩევა ნელია, ორი გამოსავალია: მოკვეთო განშტოებები, რომლებიც პასუხამდე ვერ მიგიყვანს (შემდეგი გაკვეთილი), ან შენიშნო, რომ ბევრი განშტოება ერთსა და იმავე ქვეამოცანას ხსნის და შრომა გააზიარო (დინამიური პროგრამირება). მაშინაც კი, უხეში ამოხსნა იდეალური შემმოწმებელია შენი ჭკვიანი ამოხსნის მცირე შემავალ მონაცემებზე გამოსაცდელად.

ფასი ერთი შეხედვით

ყველა ქვესიმრავლეO(2ⁿ · n)
ყველა გადანაცვლებაO(n! · n)
რეკურსიის სიღრმეO(n)

დაიმახსოვრე

  1. ქვესიმრავლეების გენერაცია ორობითი გადაწყვეტილებების ხის შემოვლაა: ყოველი ელემენტი გამოტოვე ან აიღე, უკან დაბრუნებისას კი არჩევანი გააუქმე.
  2. რიცხვები 0 … 2ⁿ − 1 ზუსტად n ელემენტის ქვესიმრავლეებია, თითო ბიტი თითო ელემენტზე.
  3. ქვესიმრავლეები 2ⁿ ღირს, გადანაცვლებები n!, ამიტომ სრული გადარჩევა დაახლოებით n ≤ 20-სა და n ≤ 10-ს ერგება.
02

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: გაჰყევი მონიშნულ გზას: ყოველი მარცხნივ მოხვევა ელემენტს გამოტოვებს, ყოველი მარჯვნივ იღებს, ყოველი დაბრუნება კი ბოლო არჩევანს აუქმებს. სცადე 4 ელემენტი და ნახე, როგორ ორმაგდება ხე.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →
✎ შენი მონაცემები4-მდე განსხვავებული რიცხვი. n = 4 იძლევა 16 ფოთოლს: ყოველი ელემენტი ხეს აორმაგებს.

გადაწყვეტილებების ხე

1?2?3?
მიმდინარე ქვესიმრავლე
{}
გამოტანილი ქვესიმრავლეები (0/8)
არ ავიღოთავიღოთ
გამოვიტანოთ 3 ელემენტის ყველა ქვესიმრავლე. ყოველი ელემენტი ერთი „კი/არა“ გადაწყვეტილებაა, ამიტომ ქვესიმრავლეა 2^3 = 8: ეს გადაწყვეტილებების ხის ფოთლებია.

ფსევდოკოდი

 1 void search(int k): 2   if k == n: print(subset); return 3   search(k+1)              // without a[k] 4   subset.push_back(a[k]) 5   search(k+1)              // with a[k] 6   subset.pop_back()        // undo the choice 7 search(0)   // 2^n leaves → O(n·2^n)
1 / 1
03

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

რეკურსია ჯერ გამოტოვებს, მერე იღებს. {1, 2, 3}-ისთვის რომელი ქვესიმრავლე დაიბეჭდება მეორე?

№2

a = [a, b, c] და ბიტი i ნიშნავს a[i]-ს. რომელი ქვესიმრავლეა ნიღაბი 6 (110₂)?

№3

ამოცანაში n ≤ 18 ნივთია და საუკეთესო ქვესიმრავლე უნდა იპოვო. რეალისტურია ქვესიმრავლეების სრული გადარჩევა?

04

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeSubsets საშუალო↗LeetCodePermutations საშუალო↗CSESApple Division საშუალო↗CSESCreating Strings საშუალო↗LeetCodeCombination Sum საშუალო↗