Nombor berbeza diperoleh dengan menjana semua pilih atur rentetan binari

Pernyataan Masalah

Kami diberi rentetan binari str panjang N. Kita perlu mencari semua pilih atur rentetan ini, menukarnya kepada nilai perpuluhan dan mengembalikan semua nilai perpuluhan yang unik.

Contoh

Masuk

str = ‘1’

Output

[1]

Arahan

Semua pilih atur "1" hanyalah "1". Oleh itu, nilai perpuluhan yang dikaitkan dengan "1" adalah sama dengan 1.

Masuk

str = ‘10’

Output

[1, 2]

Arahan

Susunan '10' hanyalah '01' dan '10', iaitu bersamaan dengan 1 dan 2 masing-masing.

Masuk

‘101’

Output

[3, 5, 6]

Arahan

Semua pilih atur yang mungkin bagi "101" ialah "110", "101", "110", "011", "101" dan "011", jika kita menukarnya kepada nombor perpuluhan kita mendapat 3, 5 dan 6 perpuluhan unik nombor.

Kaedah 1

Dalam kaedah pertama, kami akan menggunakan penjejakan belakang untuk mendapatkan semua pilih atur rentetan binari. Selepas itu, kami menukar pilih atur binari kepada nilai perpuluhan dan menggunakan set ini untuk memilih nilai perpuluhan yang unik. Kami akan menukar perpuluhan kepada binari menggunakan kaedah pow() dan untuk gelung.

Algoritma

• Langkah 1 - Takrifkan fungsi "getDecimalPermutations()" untuk mendapatkan nilai perpuluhan yang terhasil.

• Langkah 2 - Jalankan fungsi "getBinaryPermutations()" untuk mendapatkan semua pilih atur binari rentetan. Selain itu, rentetan, indeks kiri dan kanan serta vektor pilih atur diluluskan sebagai hujah.

• Langkah 2.1 - Dalam fungsi "getBinaryPermutations()", jika indeks kiri dan kanan adalah sama, tolak rentetan yang terhasil ke dalam senarai diubah suai.

• Langkah 2.2 - Jika indeks kiri dan kanan tidak sama, gunakan gelung for untuk mengulang rentetan dari indeks kiri ke indeks kanan.

• Langkah 2.3 - Tukar aksara pada indeks ke-i dan indeks kiri dalam gelung untuk.

• Langkah 2.4 - Panggil fungsi "getBinaryPermutations" sekali lagi dengan parameter yang sama dan indeks "kiri + 1".

• Langkah 2.5 - Tukar aksara pada indeks ke-i dan indeks kiri untuk tujuan menjejak ke belakang.

• Langkah 3 - Buat koleksi yang dipanggil "allDecimals". Selepas itu, ulangi semua pilihatur rentetan binari.

• Langkah 4 - Panggil fungsi bToD() untuk menukar binari kepada perpuluhan.

• Langkah 4.1 - Dalam fungsi bToD(), mulakan pembolehubah perpuluhan dengan nilai 0.

• Langkah 4.2 - Gunakan gelung for untuk mengulang rentetan binari bermula dari hujung dan tambah '(num[i] - '0') * pow(2, j )' untuk menukar kepada nilai perpuluhan.

• Langkah 4.3 - Kembalikan nilai perpuluhan.

• Langkah 5 - Dalam fungsi "getDecimalPermutations", masukkan nilai perpuluhan yang dikembalikan daripada fungsi bToD().

• Langkah 6 - Cetak semua nilai set, yang akan mengandungi nilai perpuluhan unik.

Contoh

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// Function to convert binary to decimal
int bToD(string num){
   int decimal = 0;
   for (int i = num.size() - 1, j = 0; i >= 0; i--, j++){
      decimal += (num[i] - '0') * pow(2, j);
   }
   return decimal;
}
// Function to get all permutations of a binary string
void getBinaryPermutations(string str, int left, int right, vector<string> &permutations){
   // Base case
   if (left == right){
      // push_back() function is used to push elements into a vector from the back
      permutations.push_back(str);
   } else {
      // Permutations made
      for (int i = left; i <= right; i++){
         // Swapping done
         swap(str[left], str[i]);
         // Recursion called for next index (left + 1)
         getBinaryPermutations(str, left + 1, right, permutations);
         // Backtrack
         swap(str[left], str[i]);
      }
   }
}
void getDecimalPermutations(string str){
   vector<string> permutations;
   getBinaryPermutations(str, 0, str.length() - 1, permutations);
   set<int> allDecimals;
   for (const auto &p : permutations){
      allDecimals.insert(bToD(p));
   }
   cout << "All decimal numbers which we can achieve using permutations are " << endl;
   for (const auto &d : allDecimals){
      cout << d << " ";
   }
}
int main(){
   string bString = "101";
   getDecimalPermutations(bString);
   return 0;
}

Output

All decimal numbers which we can achieve using permutations are 
3 5 6

• Kerumitan masa - O(n!). Kerumitan masa bagi fungsi "getBinaryPermutations()" ialah "n!" Kerumitan masa bagi fungsi bToD() ialah O(n).

• Kerumitan ruang - O(n!). Setiap rentetan mempunyai n!permutasi yang kami simpan dalam senarai.

Kaedah 2

Dalam kaedah ini, bukannya kaedah backtracking, kami akan menggunakan fungsi next_permutation() C++ untuk menjana pilih atur rentetan binari. Selain itu, kami menukar kaedah menukar binari kepada perpuluhan.

Algoritma

• Langkah 1 - Tentukan set "semuaNombor".

• Langkah 2 - kaedah sort() digunakan untuk mengisih rentetan binari.

• Langkah 3 - Gunakan gelung do-while untuk mengulangi setiap pilih atur rentetan.

• Langkah 4 - Dalam gelung do-while, panggil fungsi bToD() dengan menghantar rentetan sebagai parameter untuk menukar perduaan kepada nombor perpuluhan.

• Langkah 4.1 - Dalam fungsi bToD(), takrifkan pembolehubah "currentBase" dan mulakannya kepada 1.

• Langkah 4.2 - Gunakan gelung for dan ulangi rentetan bermula dari indeks terakhir.

• Langkah 4.3 - Dalam gelung for, jika aksara semasa adalah sama dengan '1', kita perlu menambah nilai currentBase kepada 'decimal_number'.

• Langkah 4.4 - Darabkan Asas semasa dengan 2.

• Langkah 5 - Masukkan nombor perpuluhan ke dalam set "allNumber".

• Langkah 6 - Gunakan kaedah next_permutation() dalam keadaan gelung do-while kerana ia akan kembali benar jika pilih atur rentetan seterusnya wujud.

• Langkah 7 - Cetak semua nombor yang ditambahkan dalam "allNumbers" untuk mendapatkan nombor perpuluhan unik yang dikaitkan dengan semua pilih atur rentetan binari yang diberikan.

示例

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;
int bToD(string num){
   int decimal_number = 0;
   // Initializing base value to 1, and it increases by power of 2 in each iteration
   int currentBase = 1;
   for (int i = num.length() - 1; i >= 0; i--){
      if (num[i] == '1'){
         decimal_number += currentBase;
      }
      currentBase = currentBase * 2;
   }
   return decimal_number;
}
void getDecimalPermutations(string str){
   // create set
   set<int> allNumbers;
   // sort the string
   sort(str.begin(), str.end());
   do {
      // convert binary string to decimal
      int result = bToD(str);
      // insert the decimal number to set
      allNumbers.insert(result);
      // get the next permutation
   } while (next_permutation(str.begin(), str.end()));
   //Print all distinct decimal numbers
   cout << "All decimal numbers which we can achieve using permutations are " << endl;
   for (auto num : allNumbers)
      cout << num << " ";
      cout << endl;
}
int main(){
   string bString = "101";
   getDecimalPermutations(bString);
   return 0;
}

输出

All decimal numbers which we can achieve using permutations are 
3 5 6

• 时间复杂度 - O(n*n!)。这里，next_permutations() 需要 O(n) 时间来找到一个排列，并且我们正在找到总共 n！排列。

• 空间复杂度 - O(n!)，因为我们将所有排列存储在列表中。

结论

我们学习了不同的方法来获取通过给定二进制字符串的所有排列获得的唯一十进制值。在第一种方法中，我们使用了回溯；在第二种方法中，我们使用了 next_permutation() 方法。

第二种方法的代码更清晰，但需要更多的时间和复杂性。

Atas ialah kandungan terperinci Nombor berbeza diperoleh dengan menjana semua pilih atur rentetan binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!