Qanday qilib berilgan massivning barcha qism massivlarini chiqarish mumkin?
Tushuntirish
Massivning barcha qism massivlari deganda massivdan hosil qilib bo‘ladigan barcha massivlarga aytiladi. Keling sizlar bilan ushbu qism massivlarni hosil qilish haqida gaplashsak. Bizda [4, 1, 7] massivi mavjud va biz quyidagicha javob chiqarishimiz kerak:
[{}, {1}, {4}, {7}, {1, 4}, {1, 7}, {4, 7}, {1, 4, 7}] – buni ingliz tilida power set ham deyishadi. {1, 4} va {4, 1} qism massivlar bir xil hisoblanadi.
Massiv uzunligi 3 ga va qism massivlar soni esa 8 ga teng. Agar massiv uzunligi 2 ga teng bo‘lsa qism massivlar soni 4 ga tenglashadi (buni qo‘lda tekshirishingiz mumkin). Xulosa qilganda massiv uzunligini n deb belgilab olsak qism massivlar soni 2^n (bu 2 ning n-darasi) ga teng. Ya’ni qism massivlar yaratayotganda i indeksni qo‘shamiz yoki qo‘shmaymiz deymiz va bunda 2 xil holat bo‘ladi shuning uchun n ni 2 ning darajasiga yozamiz (oddiy kombinatorika).
Kodda yozish
Endi buni kodda qanday qilib yozishga kelganda qo‘shamiz yoki qo‘shmaymiz g‘oyasidan foydalansak. Tepadagi massiv uzunligi 3 ga teng va biz hamma holatlarni birma-bir yozib chiqamiz – [000, 001, 010, 011, 100, 101, 110, 111]. Qaysi indeksda nol turgan bo‘lsa shu indeksni o‘sha qism massivga qo‘shmaymiz, agar bir turgan bo‘lsa o‘sha qism massivga qo‘shamiz, tepadagi holatni [4, 1, 7] massivi orqali qaytadan yozib chiqsak.
000 = {} – hamma indeksda nol ko‘rsatilgan, demak qism massivda hech qanday element bo ‘lmaydi.
001 = {7} – faqatgina uchinchi indeksda 1 soni bor, demak faqat 7 raqamidan tashkil topgan qism massiv bo‘ladi.
010 = {1} – faqatgina ikkinchi indeksda 1 soni bor, demak faqat 1 raqamidan tashkil topgan qism massiv bo‘ladi.
011 = {1, 7} – 2 va 3 - indekslarda 1 soni bor, demak 1 va 7 raqamidan tashkil topgan qism massiv bo‘ladi.
100 = {4} – faqatgina birinchi indeksda 1 soni bor, demak faqat 4 raqamidan tashkil topgan qism massiv bo‘ladi.
101 = {4, 7} – 1 va 3 - indekslarda 1 soni bor, demak 4 va 7 raqamidan tashkil topgan qism massiv bo‘ladi.
110 = {1, 4} – 1 va 2 - indekslarda 1 soni bor, demak 1 va 4 raqamidan tashkil topgan qism massiv bo‘ladi.
111 = {1, 4, 7} – 1, 2 va 3 - indekslarda 1 soni bor, demak 1, 4 va 7 raqamidan tashkil topgan qism massiv bo‘ladi.
Xulosa qilganda birinchi biz [000, 001, 010, 011, 100, 101, 110, 111] ushbu massivni yaratamiz, keyin shu massiv orqali qism massivlarimizni yasab olamiz. Bu qism massiv [0, 1, 2, 3, 4, 5, 6, 7] sonlarining binar ko‘rinishidir, biz qiladigan ish 0 dan 2^n-1 gacha bo’lgan sonlarning binar ko‘rinishini bir massivda saqlash. Bundan keyin qiladigan ish – binar ko‘rinishda saqlagan massivimizga qarab qism massivlarni yaratish. Quyidagi kodda shu usulda yechilganini ko‘rishingiz mumkin:
string decimal_to_binary(int n){
if(n<2) return to_string(n);
string s="";
while(n>1){
if(n%2==0) s+='0';
else s+='1';
n/=2;
}
s+=to_string(n);
reverse(s.begin(), s.end());
return s;
}
vector<vector<int>> subsets(vector<int> &nums){
vector<vector<int>> subs;
vector<string> binar;
int n=nums.size();
for(int i=0; i<(1<<n); i++){
string s=decimal_to_binary(i); // bu funksiya o'nlikdan ikkilikka o'tkazadi
s=string(n-s.size(), '0')+s; // barcha sonlar uzunligi bir xil
// bo'lishi uchun oldinini nollar bilan to'ldiramiz
binar.push_back(s);
}
for(int i=0; i<binar.size(); i++){
vector<int> subset; // qism massiv uchun massiv yaratamiz
for(int j=0; j<n; j++){
if(binar[i][j]=='1') subset.push_back(nums[j]); // agar 1 bo'lsa qo'shamiz
}
subs.push_back(subset); // hosil bo'lgan qism massivni javobga qo'shib qo'yamiz
}
return subs; // barcha qism massivlardan hosil bo'lgan massivni natija sifatida qaytaramiz
}
void solution()
{
int n; cin >> n;
vector<int> nums(n);
for(int i=0; i<n; i++) cin >> nums[i]; // massivni o'qib olamiz
vector<vector<int>> subs=subsets(nums); // natijani funksiyadan subs o'zgaruvchisiga olamiz
// pastda qism massivlar chiqarilgan
for(int i=0; i<subs.size(); i++){
for(int j=0; j<subs[i].size(); j++){
cout << subs[i][j] << ' ';
}
cout << '\n';
}
}
1-optimizatsiya
Keling endi kodni qisqaroq qilamiz, aslida bizga binar massivi kerakmi? Sonlarning binar ko‘rinishini alohida massivga saqlagandan ko‘ra qism massivlarni o‘sha paytda topib ketsak ham bo‘ladi aslida. Pastdagi kodda buni to‘g‘irlaymiz.
string decimal_to_binary(int n){
if(n<2) return to_string(n);
string s="";
while(n>1){
if(n%2==0) s+='0';
else s+='1';
n/=2;
}
s+=to_string(n);
reverse(s.begin(), s.end());
return s;
}
vector<vector<int>> subsets(vector<int> &nums){
vector<vector<int>> subs;
int n=nums.size();
for(int i=0; i<(1<<n); i++){
string s=decimal_to_binary(i); // bu funksiya o'nlikdan ikkilikka o'tkazadi
s=string(n-s.size(), '0')+s; // barcha sonlar uzunligi bir xil bo'lishi uchun oldinini nollar bilan to'ldiramiz
vector<int> subset; // qism massiv uchun massiv yaratamiz
for(int j=0; j<n; j++){
if(s[j]=='1') subset.push_back(nums[j]); // agar 1 bo'lsa qo'shamiz
}
subs.push_back(subset); // hosil bo'lgan qism massivni javobga qo'shib qo'yamiz
}
return subs; // barcha qism massivlardan hosil bo'lgan massivni natija sifatida qaytaramiz
}
void solution()
{
int n; cin >> n;
vector<int> nums(n);
for(int i=0; i<n; i++) cin >> nums[i]; // massivni o'qib olamiz
vector<vector<int>> subs=subsets(nums); // natijani funksiyadan subs o'zgaruvchisiga olamiz
// pastda qism massivlar chiqarilgan
for(int i=0; i<subs.size(); i++){
for(int j=0; j<subs[i].size(); j++){
cout << subs[i][j] << ' ';
}
cout << '\n';
}
}
2-optimizatsiya
Bu yerda yana bir qismni o‘zgartirish orqali kodimizni yanada tezlashtirishimiz mumkin. Kompyuter boshqa amallarga qaraganda bitwise amallarni tezroq bajaradi. Masalan bitwise AND & operatorini hozirgi masalada ishlatsak.
Agar biz kodimizda 3 & 2 qilsak bizga natija sifatida 2 ni qaytaradi, keling shuni qanday chiqarishini chuqurroq o‘rgansak. Kompyuter birinchi 3 va 2 sonlarini ikkilikka o‘tkazadi, keyin ularni orqali bitlaridan boshlab bitwise AND & operatorini bajaradi. Bitwise AND operatori jadvalini quyida ko‘rishingiz mumkin:
| A | B | A & B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Endi esa jadvaldan foydalanib 3 & 2 amalini oxirgi bitidan boshlab bajaramiz. 3 bu yerda A ning o‘rniga, 2 esa B ning o‘rnida kelgan.
3 raqamining ikkilikda ko‘rinishi 11
2 raqamining ikkilikda ko‘rinishi 10
| 1-bit | 0-bit | |
|---|---|---|
| A | 1 | 1 |
| B | 1 | 0 |
| Javob | 1 | 0 |
Javob 10 lekin kompyuter buni o‘nlikka o‘tkazib keyin chiqaradi. 10 sonini o‘nlik sanoq sistemasiga o‘tkazsak 2 ga teng. Yaxshiroq tushunish uchun yana bir boshqa misolga qarasak 91 & 12.
Jadvalda yozsak:
91 raqamining ikkilikda ko‘rinishi 1011011
12 raqamining ikkilikda ko‘rinishi 1100
| 6-bit | 5-bit | 4-bit | 3-bit | 2-bit | 1-bit | 0-bit | |
|---|---|---|---|---|---|---|---|
| A | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| B | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| Javob | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
1100 uzunligi kam bo‘lganligi uchun uning oldinini nollar bilan to‘ldirish kerak shunda javob to‘g‘ri chiqadi. Javob 1000, buni o‘nlikka o‘tkazsak 8 bo‘ladi.
Mavzudan tashqari c++ dasturlash tilida 1<<n ko‘rinishda yozsa bizga 2 ning n-darajasini chiqarib beradi.
Bitwise AND operatori bilan ishlashni o‘rgandik endi esa masalada buni qo‘llaymiz. 14 sonining n-biti bir agarda 14 & (1<<n) >= 1 ushbu shart qanotlansa aks holda nol. Masalan n o‘rniga 2 sonini qo‘yib tekshirib ko‘rsak. 14 & (1<<2) teng bo‘ladi 14 & 4 ga. Endi esa jadval orqali bitwise AND operatorini bajaramiz.
| 3-bit | 2-bit | 1-bit | 0-bit | |
|---|---|---|---|---|
| A | 1 | 1 | 1 | 0 |
| B | 0 | 1 | 0 | 0 |
| Javob | 0 | 1 | 0 | 0 |
2 ning barcha darajalarida (noldan tashqari) faqatgina bitta bir soni bo‘ladi. 2 ning darajalarini quyida ko‘rsak.
0 – 2^0
10 – 2^1
100 – 2^2
1000 – 2^3
10000 – 2^4
100000 – 2^5
... hokazo
Bundan xulosa qilsak x sonining n-biti bir ekanligini aniqlash uchun x & (1<<n) >=1 danligini tekshirish yetarli. Pastdagi kodda esa 0 dan 2^n-1 gacha bo‘lgan sonlarni ikkilik sanoq sistemasiga o‘tkazib tekshirgandan ko‘ra endi bizda shunchaki o‘sha sonni o‘zini bemalol bitwise AND & operatori orqali osongina yozib qo‘yishimiz mumkin.
vector<vector<int>> subsets(vector<int> &nums){
vector<vector<int>> subs;
int n=nums.size();
for(int i=0; i<(1<<n); i++){
vector<int> subset; // qism massiv uchun massiv yaratamiz
for(int j=0; j<n; j++){
if(i&(1<<j)) subset.push_back(nums[j]);
}
subs.push_back(subset); // hosil bo'lgan qism massivni javobga qo'shib qo'yamiz
}
return subs; // barcha qism massivlardan hosil bo'lgan massivni natija sifatida qaytaramiz
}
void solution()
{
int n; cin >> n;
vector<int> nums(n);
for(int i=0; i<n; i++) cin >> nums[i]; // massivni o'qib olamiz
vector<vector<int>> subs=subsets(nums); // natijani funksiyadan subs o'zgaruvchisiga olamiz
// pastda qism massivlar chiqarilgan
for(int i=0; i<subs.size(); i++){
for(int j=0; j<subs[i].size(); j++){
cout << subs[i][j] << ' ';
}
cout << '\n';
}
}
Leetcode saytida xuddi shu masala mavjud quyidagi link orqali yechib ko‘rishingiz mumkin. https://leetcode.com/problems/subsets/description/
Leetcodeda qanday yechim yuborishni bilmasangiz quyida tepadagi kodni qanday yuborilganini ko‘rishingiz mumkin.
class Solution {
public:
vector<vector<int>> subsets(vector<int> &nums){
vector<vector<int>> subs;
int n=nums.size();
for(int i=0; i<(1<<n); i++){
vector<int> subset; // qism massiv uchun massiv yaratamiz
for(int j=0; j<n; j++){
if(i&(1<<j)) subset.push_back(nums[j]);
}
subs.push_back(subset); // hosil bo'lgan qism massivni javobga qo'shib qo'yamiz
}
return subs; // barcha qism massivlardan hosil bo'lgan massivni natija sifatida qaytaramiz
}
void solution()
{
int n; cin >> n;
vector<int> nums(n);
for(int i=0; i<n; i++) cin >> nums[i]; // massivni o'qib olamiz
vector<vector<int>> subs=subsets(nums); // natijani funksiyadan subs o'zgaruvchisiga olamiz
// pastda qism massivlar chiqarilgan
for(int i=0; i<subs.size(); i++){
for(int j=0; j<subs[i].size(); j++){
cout << subs[i][j] << ' ';
}
cout << '\n';
}
}
};