در این مطلب، ویدئو پردازش رشته در پایتون: جایگشت را بررسی کنید با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,030 –> 00:00:01,920
بسیار خوب، بنابراین در این ویدیو می خواهیم
2
00:00:01,920 –> 00:00:03,179
مسئله زیر را حل
3
00:00:03,179 –> 00:00:05,100
کنیم، بنابراین دو رشته به ما داده می شود که می خواهیم
4
00:00:05,100 –> 00:00:07,259
روشی بنویسیم تا تصمیم بگیریم که آیا یکی
5
00:00:07,259 –> 00:00:09,929
جایگشت دیگری است، بنابراین در اینجا
6
00:00:09,929 –> 00:00:11,790
دو رشته داریم که به عنوان متغیر تعریف می کنیم.
7
00:00:11,790 –> 00:00:13,769
و dog و این دو
8
00:00:13,769 –> 00:00:15,570
جایگشت یکدیگر هستند زیرا می
9
00:00:15,570 –> 00:00:17,250
توانید حروف خدا را مجدداً مرتب کنید تا
10
00:00:17,250 –> 00:00:19,560
dog و بالعکس و سپس این دو
11
00:00:19,560 –> 00:00:21,570
رشته در اینجا نمونه هایی از غیر
12
00:00:21,570 –> 00:00:23,820
جایگشت هستند بنابراین راهی وجود ندارد که
13
00:00:23,820 –> 00:00:25,890
بتوان حروف این رشته را مجدداً تنظیم کرد.
14
00:00:25,890 –> 00:00:28,410
get top و بالعکس، بنابراین این
15
00:00:28,410 –> 00:00:30,060
دو رشته جایگشت نیستند و
16
00:00:30,060 –> 00:00:32,040
این دو چیزی است که ما در
17
00:00:32,040 –> 00:00:33,059
این ویدیو انجام می دهیم، ما به
18
00:00:33,059 –> 00:00:34,950
دو روش برای تعیین اینکه
19
00:00:34,950 –> 00:00:37,020
آیا یک جفت رشته معین
20
00:00:37,020 –> 00:00:38,879
جایگشت یکدیگر هستند یا خیر، نزدیک می شویم. ما
21
00:00:38,879 –> 00:00:40,079
22
00:00:40,079 –> 00:00:41,850
قصد داریم با رویکردی شروع کنیم که کمی کمتر
23
00:00:41,850 –> 00:00:44,190
بهینه تر از رویکرد زیر است.
24
00:00:44,190 –> 00:00:45,420
رویکرد دومی که نشان خواهیم داد و
25
00:00:45,420 –> 00:00:47,460
فقط هر یک از آنها را نشان می دهیم و
26
00:00:47,460 –> 00:00:49,559
سپس کمی بسیار مختصر انجام می دهیم. تجزیه
27
00:00:49,559 –> 00:00:51,570
و تحلیل به عنوان پیچیدگی زمان اجرا
28
00:00:51,570 –> 00:00:54,090
هر یک از رویکردها چه چیزی را به ما می دهد، بنابراین
29
00:00:54,090 –> 00:00:55,230
بیایید جلو برویم و تابعی را تعریف کنیم
30
00:00:55,230 –> 00:00:58,559
که آن را perm می نامیم و
31
00:00:58,559 –> 00:01:00,090
در واقع این را perm one می نامیم، بنابراین
32
00:01:00,090 –> 00:01:02,399
اگر بدانیم که دو طعم از این را تعریف می کنیم.
33
00:01:02,399 –> 00:01:04,349
تابع این
34
00:01:04,349 –> 00:01:06,030
دو رشته می گیرد، بنابراین ما آنها را رشته
35
00:01:06,030 –> 00:01:08,760
یک در رشته دو می نامیم و سپس کاری که می
36
00:01:08,760 –> 00:01:10,110
خواهیم انجام دهیم این است که
37
00:01:10,110 –> 00:01:12,180
کمی پیش پردازش روی این رشته ها انجام می دهیم، بنابراین
38
00:01:12,180 –> 00:01:14,070
فقط کمی وجود دارد یک نکته در اینجا
39
00:01:14,070 –> 00:01:17,280
نیز این است که ما رشته ها را به حروف کوچک عادی می کنیم،
40
00:01:17,280 –> 00:01:19,470
بنابراین در هر دو
41
00:01:19,470 –> 00:01:21,270
مثالی که نشان داده ایم حروف
42
00:01:21,270 –> 00:01:22,740
اینجا همه با حروف کوچک هستند، اما شما می
43
00:01:22,740 –> 00:01:25,369
توانستید چیزی شبیه به این داشته باشید و
44
00:01:25,369 –> 00:01:27,810
یا شاید مثال بهتری چیزی
45
00:01:27,810 –> 00:01:29,700
شبیه به این، بنابراین اگر چیزی شبیه به
46
00:01:29,700 –> 00:01:31,560
آن در آنجا داشته باشیم نشان می دهد که
47
00:01:31,560 –> 00:01:33,810
آن دو به عنوان جایگشت در نظر گرفته می شوند،
48
00:01:33,810 –> 00:01:37,380
حتی اگر این G
49
00:01:37,380 –> 00:01:39,689
بزرگ باشد، خوب این G کوچک است، بنابراین ما
50
00:01:39,689 –> 00:01:41,430
می خواهیم حروف را عادی کنیم
51
00:01:41,430 –> 00:01:43,500
تا مطمئن شویم که ما
52
00:01:43,500 –> 00:01:45,240
نیازی به نگرانی نیست زمانی که
53
00:01:45,240 –> 00:01:47,159
برای بررسی جایگشتها پردازش میشد
54
00:01:47,159 –> 00:01:48,840
، اشاره میکنم که ما
55
00:01:48,840 –> 00:01:50,610
چیزی شبیه به این داریم که در آن
56
00:01:50,610 –> 00:01:52,439
فضاهای اضافی داریم، میخواهیم
57
00:01:52,439 –> 00:01:54,840
فضاها را به عنوان کاراکترهای واقعی در نظر بگیریم، بنابراین در این
58
00:01:54,840 –> 00:01:56,880
مورد از آنجایی که من فضاهای اضافی را در اینجا اضافه کردهام
59
00:01:56,880 –> 00:01:58,920
که قرار نیست اکنون جایگشت
60
00:01:58,920 –> 00:02:01,680
سگ باشید زیرا سه
61
00:02:01,680 –> 00:02:03,509
فضای اضافی در این رشته وجود دارد که در آن هیچ
62
00:02:03,509 –> 00:02:06,060
فاصلهای در این رشته وجود ندارد، بنابراین ما
63
00:02:06,060 –> 00:02:08,128
اکنون میخواهیم هر فاصلهای را که
64
00:02:08,128 –> 00:02:11,038
ممکن است از سایر مشکلات انتظار داشته باشید که
65
00:02:11,038 –> 00:02:12,420
شامل رشتههایی است که قبلاً پردازش کردهایم حذف میکنیم.
66
00:02:12,420 –> 00:02:13,770
این
67
00:02:13,770 –> 00:02:15,630
واقعاً بستگی به روشی دارد که در آن
68
00:02:15,630 –> 00:02:18,480
مشکل را تعریف می کنید، گاهی اوقات فضاها ممکن
69
00:02:18,480 –> 00:02:20,310
است مهم باشند یا ممکن است مهم نباشند.
70
00:02:20,310 –> 00:02:21,390
71
00:02:21,390 –> 00:02:23,310
72
00:02:23,310 –> 00:02:24,960
73
00:02:24,960 –> 00:02:26,730
یک
74
00:02:26,730 –> 00:02:28,800
تکلیف یا هر چیز دیگری در این مورد
75
00:02:28,800 –> 00:02:30,810
فضاها مهم خواهند بود، اما
76
00:02:30,810 –> 00:02:32,400
case چیزی است که ما نادیده می گیریم،
77
00:02:32,400 –> 00:02:33,990
بنابراین من از شر آن فضاها خلاص می شوم.
78
00:02:33,990 –> 00:02:35,880
اینجا و من میروم،
79
00:02:35,880 –> 00:02:37,970
میتوانم همینطور آن را رها کنم،
80
00:02:37,970 –> 00:02:40,620
بنابراین در این تابع کاری که
81
00:02:40,620 –> 00:02:42,210
میخواهیم انجام دهیم این است که اولین
82
00:02:42,210 –> 00:02:44,430
رویکرد را در پیش بگیریم، اجازه دهید قبل از انجام این کار
83
00:02:44,430 –> 00:02:46,440
، رشتهها را از قبل پردازش کنیم. بنابراین
84
00:02:46,440 –> 00:02:48,900
همه آنها همانطور که میخواهیم عادی شدهاند، به
85
00:02:48,900 –> 00:02:50,610
عبارت دیگر میخواهیم آنها با
86
00:02:50,610 –> 00:02:53,220
حروف کوچک باشند، بنابراین میخواهیم بگوییم که رشته 1
87
00:02:53,220 –> 00:02:56,100
برابر است با رشته 1 نه کمتر و ما
88
00:02:56,100 –> 00:02:57,720
همان کار را برای رشته 2 انجام میدهیم.
89
00:02:57,720 –> 00:02:58,980
میخواهیم بگوییم که رشته 2 برابر است با
90
00:02:58,980 –> 00:03:01,470
رشته 2 به پایین، بنابراین اکنون هر دو رشته
91
00:03:01,470 –> 00:03:02,940
1 به
92
00:03:02,940 –> 00:03:04,920
حروف کوچک تبدیل میشوند و یک کاری که میتوانیم
93
00:03:04,920 –> 00:03:06,840
فوراً انجام دهیم تا بررسی کنیم که آیا
94
00:03:06,840 –> 00:03:08,730
رشته 1 یا رشته 2 یا جایگشتهای
95
00:03:08,730 –> 00:03:11,340
هر کدام انجام میشود یا خیر. دیگری یک بررسی بسیار سریع است که
96
00:03:11,340 –> 00:03:13,590
میتوانیم آن را با طول یکسان بررسی کنیم، بنابراین اگر
97
00:03:13,590 –> 00:03:15,060
طول آنها یکسان باشد، پتانسیل تغییر شکل دارند،
98
00:03:15,060 –> 00:03:17,430
اما اگر
99
00:03:17,430 –> 00:03:19,320
طول آنها یکسان نباشد، راهی وجود ندارد
100
00:03:19,320 –> 00:03:20,760
که بتوانیم شخصیتهای یکی از آنها را مرتب
101
00:03:20,760 –> 00:03:22,350
کنیم. رشته ها را به دیگری متصل می کند
102
00:03:22,350 –> 00:03:24,540
زیرا هیچ راهی وجود ندارد که بتوانیم آن را
103
00:03:24,540 –> 00:03:25,890
بازآرایی کنیم مستلزم
104
00:03:25,890 –> 00:03:28,080
حذف یا اضافه کردن یک کاراکتر به آن
105
00:03:28,080 –> 00:03:29,580
رشته نیست، بنابراین ما فقط یک
106
00:03:29,580 –> 00:03:32,520
بررسی سریع برای حذف
107
00:03:32,520 –> 00:03:34,530
رشتههایی که طول یکسانی ندارند انجام
108
00:03:34,530 –> 00:03:36,209
میدهیم، بنابراین میخواهیم بررسی کنیم که آیا طول
109
00:03:36,209 –> 00:03:38,700
رشته 1 است یا خیر. طول
110
00:03:38,700 –> 00:03:40,680
رشته 2 برابر نیست و اتفاقاً
111
00:03:40,680 –> 00:03:41,970
اینطور است، پس کاری که ما انجام خواهیم داد این است که فقط
112
00:03:41,970 –> 00:03:44,640
از خفاش خارج میشویم و فقط false را برمیگردانیم،
113
00:03:44,640 –> 00:03:46,320
در غیر این صورت پیش میرویم و ابتدا این کار را انجام میدهیم.
114
00:03:46,320 –> 00:03:49,709
115
00:03:49,709 –> 00:03:51,240
بنابراین اولین رویکرد این است که
116
00:03:51,240 –> 00:03:53,160
ما هر دو رشته 1
117
00:03:53,160 –> 00:03:55,050
و رشته 2 را به طور خاص در نظر می گیریم، کاری که می
118
00:03:55,050 –> 00:03:56,220
خواهیم انجام دهیم این است که آنها را
119
00:03:56,220 –> 00:03:59,670
بر اساس حروف الفبا مرتب می کنیم تا بر اساس حروف الفبا، حدس می
120
00:03:59,670 –> 00:04:01,560
زنم Deluxe یک ترتیب گرافیکی باشد.
121
00:04:01,560 –> 00:04:02,760
رشته ها همان چیزی است که ما دنبال آن خواهیم بود،
122
00:04:02,760 –> 00:04:04,890
بنابراین از روش مرتب سازی داخلی
123
00:04:04,890 –> 00:04:07,740
در پایتون برای مرتب سازی دو رشته استفاده می کنیم
124
00:04:07,740 –> 00:04:10,140
تا همانطور که می دانید الگوریتم مرتب سازی مبتنی بر مقایسه
125
00:04:10,140 –> 00:04:12,270
کران پایین برای آن
126
00:04:12,270 –> 00:04:13,500
بهترین کاری است که می توانیم امیدوار باشیم انجام دهیم. برای
127
00:04:13,500 –> 00:04:16,380
مقایسه، مرتب سازی مبتنی بر n log n است، بنابراین
128
00:04:16,380 –> 00:04:18,269
جایی که n اندازه رشته است g و در
129
00:04:18,269 –> 00:04:19,529
این مرحله پس از زدن
130
00:04:19,529 –> 00:04:21,418
عبارت if به این نتیجه رسیدیم
131
00:04:21,418 –> 00:04:22,860
که طول هر دو
132
00:04:22,860 –> 00:04:24,990
رشته یکسان خواهد بود، بنابراین
133
00:04:24,990 –> 00:04:27,240
به آن اندازه به عنوان n اشاره می کنیم.
134
00:04:27,240 –> 00:04:27,780
این کار را انجام
135
00:04:27,780 –> 00:04:30,120
می دهیم زیرا رشته ها را مرتب می کنیم و
136
00:04:30,120 –> 00:04:31,710
پس از مرتب شدن در آنجا
137
00:04:31,710 –> 00:04:33,450
، کاراکترهای
138
00:04:33,450 –> 00:04:34,889
رشته ها را حلقه می زنیم و سپس بررسی می کنیم که
139
00:04:34,889 –> 00:04:36,840
آیا کاراکترها مطابقت دارند
140
00:04:36,840 –> 00:04:38,669
یا خیر. به طور خاص که آیا
141
00:04:38,669 –> 00:04:39,960
کاراکترها با یکدیگر برابر هستند یا نه،
142
00:04:39,960 –> 00:04:42,240
زیرا اگر آنها مساوی باشند،
143
00:04:42,240 –> 00:04:44,760
اگر جایگشتی وجود داشته باشد مرتب می شوند،
144
00:04:44,760 –> 00:04:46,110
باید همان کاراکترها را
145
00:04:46,110 –> 00:04:47,580
در همان مکان در
146
00:04:47,580 –> 00:04:48,960
حلقه مشاهده کنیم، در غیر این صورت اگر جایگشت نباشند،
147
00:04:48,960 –> 00:04:51,450
این کار انجام نمی شود. بنابراین
148
00:04:51,450 –> 00:04:53,760
بیایید ابتدا رشتهها را مرتب کنیم
149
00:04:53,760 –> 00:04:54,990
تا روشی که میتوانیم انجام دهیم این است که میتوانیم بگوییم
150
00:04:54,990 –> 00:05:01,169
رشته ۱ برابر است با پیوستن به رشته مرتبشده
151
00:05:01,169 –> 00:05:03,240
۱، بنابراین اساساً کاری که ما در اینجا انجام میدهیم این است
152
00:05:03,240 –> 00:05:05,490
که تابع
153
00:05:05,490 –> 00:05:07,650
مرتبسازی شده تابع مرتبسازی داخلی پایتون است و پس اساساً کاری که
154
00:05:07,650 –> 00:05:09,300
ما در اینجا انجام می دهیم، زیرا رشته یک
155
00:05:09,300 –> 00:05:11,400
st است رشته حلقه ای که یک رشته است ما
156
00:05:11,400 –> 00:05:13,230
آن را به یک لیست تبدیل می کنیم زیرا
157
00:05:13,230 –> 00:05:15,450
در لیستی عمل می کند و ما آن را
158
00:05:15,450 –> 00:05:17,250
به رشته 1 اعمال می کنیم و سپس آن
159
00:05:17,250 –> 00:05:19,740
لیست مرتب شده را به یک رشته تبدیل می کنیم،
160
00:05:19,740 –> 00:05:21,180
بنابراین در اصل این چیزی است که این نقطه اتصال
161
00:05:21,180 –> 00:05:22,919
انجام می دهد. بنابراین فقط حذف می شود، ما
162
00:05:22,919 –> 00:05:24,540
تابع مرتب شده را در لیست اعمال می کنیم و
163
00:05:24,540 –> 00:05:26,430
آن را به یک رشته تبدیل می کنیم و
164
00:05:26,430 –> 00:05:29,310
سپس رشته مرتب شده در این متغیر رشته 1 ذخیره می شود،
165
00:05:29,310 –> 00:05:31,410
بنابراین ما
166
00:05:31,410 –> 00:05:33,060
همان کار را برای رشته 2 نیز انجام می دهیم، بنابراین ما می
167
00:05:33,060 –> 00:05:34,410
خواهیم ادامه دهید و آن را به رشته تغییر دهید
168
00:05:34,410 –> 00:05:37,050
تا رشته 2 را در اینجا مرتب کنید، بنابراین اکنون در این
169
00:05:37,050 –> 00:05:39,090
مرحله هر دو آنها مرتب شده اند، بنابراین
170
00:05:39,090 –> 00:05:40,740
کاری که می توانیم انجام دهیم این است که می توانیم بگوییم n
171
00:05:40,740 –> 00:05:42,690
برابر با طول رشته 1 است، بنابراین
172
00:05:42,690 –> 00:05:44,400
در این نقطه دوباره هر دو را به خاطر بسپارید.
173
00:05:44,400 –> 00:05:46,110
طول رشته یک رشته دو
174
00:05:46,110 –> 00:05:47,610
برابر با یکدیگر فرض می شود
175
00:05:47,610 –> 00:05:50,160
در غیر
176
00:05:50,160 –> 00:05:51,600
این صورت اگر دستور به این می رسیدند و
177
00:05:51,600 –> 00:05:53,160
سپس تابع false را بر نمی گرداند،
178
00:05:53,160 –> 00:05:55,050
بنابراین فرض می کنیم که n
179
00:05:55,050 –> 00:05:57,180
طول هر دو رشته است. 1 و رشته 2 و
180
00:05:57,180 –> 00:05:58,110
کاری که ما می خواهیم انجام دهیم این است ما می خواهیم
181
00:05:58,110 –> 00:05:59,400
از طریق حلقه حلقه بزنیم، بنابراین برای I
182
00:05:59,400 –> 00:06:02,669
در محدوده می گوییم و و می خواهیم بررسی کنیم که آیا
183
00:06:02,669 –> 00:06:07,169
رشته 1 از I برابر با رشته 2
184
00:06:07,169 –> 00:06:09,390
از I نیست، بنابراین اگر کاراکترهای این
185
00:06:09,390 –> 00:06:10,770
رشته ها در این نقطه در تکرار
186
00:06:10,770 –> 00:06:12,930
با یکدیگر برابر نیستند، سپس
187
00:06:12,930 –> 00:06:15,690
ما false را برمی گردانیم در غیر این صورت اگر
188
00:06:15,690 –> 00:06:17,550
بتوانیم به کل این حلقه
189
00:06:17,550 –> 00:06:19,200
برسیم بدون اینکه این اتفاق بیفتد، می دانیم که آنها
190
00:06:19,200 –> 00:06:20,610
جایگشت هستند، ما ادامه می دهیم و
191
00:06:20,610 –> 00:06:22,919
می گوییم بازگشت true پس بیایید ادامه دهید و
192
00:06:22,919 –> 00:06:25,169
فقط این را روی رشتههایی که
193
00:06:25,169 –> 00:06:26,910
در بالا تعریف کردهایم آزمایش کنید، بنابراین میخواهم
194
00:06:26,910 –> 00:06:30,810
بگویم چاپ perm 1 است و سپس این کار
195
00:06:30,810 –> 00:06:33,450
را انجام میدهیم در جایگشت 1 رشته اول
196
00:06:33,450 –> 00:06:34,979
و سپس رشته دوم است.
197
00:06:34,979 –> 00:06:37,500
جایگشت 2 و سپس ما
198
00:06:37,500 –> 00:06:39,630
این کار را روی مجموعه رشته های
199
00:06:39,630 –> 00:06:40,730
دیگر انجام خواهیم داد، بنابراین ما می
200
00:06:40,730 –> 00:06:43,970
خواهیم جایگشت یکی از جایگشت یک باشد و
201
00:06:43,970 –> 00:06:46,550
نه جایگشت دو، بنابراین من ادامه می دهم و
202
00:06:46,550 –> 00:06:50,000
آن را در اینجا جایگزین می کنم تا آن را ذخیره کنم که بروم
203
00:06:50,000 –> 00:06:50,900
پیش رو و اجرا کنید این
204
00:06:50,900 –> 00:06:54,200
پایتون جایگشت است نه pi است و بنابراین
205
00:06:54,200 –> 00:06:56,540
برای get a dog درست است و سپس
206
00:06:56,540 –> 00:06:59,810
برای گره های دیگر نادرست می بینیم. بالا، بنابراین
207
00:06:59,810 –> 00:07:02,960
رفتار مورد انتظار همان چیزی است که ما آن
208
00:07:02,960 –> 00:07:05,270
رفتار همان چیزی است که انتظارش را داشتیم، پس بیایید
209
00:07:05,270 –> 00:07:07,040
جلو برویم و رویکرد دیگری را در نظر بگیریم و
210
00:07:07,040 –> 00:07:08,150
فقط پیش برویم و
211
00:07:08,150 –> 00:07:10,640
پیچیدگی زمان اجرا را یادداشت کنیم، بنابراین
212
00:07:10,640 –> 00:07:15,470
پیچیدگی زمانی در این مورد o از
213
00:07:15,470 –> 00:07:18,280
n log باشد. n دوباره به این دلیل است که ما
214
0