バイナリ文字列のすべての順列を生成することで得られるさまざまな数値

＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃問題文＃＃＃

長さ N のバイナリ文字列 str が与えられます。この文字列のすべての順列を検索し、それらを 10 進数値に変換し、すべての一意の 10 進数値を返す必要があります。 ＃＃＃例＃＃＃ ＃＃＃入力＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

イラスト

「1」の順列はすべて単なる「1」です。したがって、「1」に関連付けられた 10 進数値は 1 と等しくなります。

＃＃＃入力＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

イラスト

「10」の配列は「01」と「10」のみで、それぞれ1と2に相当します。

＃＃＃入力＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

イラスト

「101」の可能な順列はすべて「110」、「101」、「110」、「011」、「101」、「011」です。これらを 10 進数に変換すると、3、5、6 になります。固有の 10 進数。

方法1

最初の方法では、バックトラッキングを使用してバイナリ文字列のすべての順列を取得します。その後、バイナリの順列を 10 進数値に変換し、このセットを使用して一意の 10 進数値を選択します。 pow() メソッドと for ループを使用して 10 進数を 2 進数に変換します。

＃＃＃アルゴリズム＃＃＃

ステップ 1

- 「getDecimalPermutations()」関数を定義して、結果の 10 進数値を取得します。

ステップ 2

- 「getBinaryPermutations()」関数を実行して、文字列のすべてのバイナリ順列を取得します。さらに、文字列、左右のインデックス、および置換ベクトルが引数として渡されます。

ステップ 2.1

- 「getBinaryPermutations()」関数で、左と右のインデックスが等しい場合、結果の文字列を並べ替えられたリストにプッシュします。

ステップ 2.2

- 左と右のインデックスが等しくない場合は、for ループを使用して、左のインデックスから右のインデックスまで文字列を繰り返します。

• ステップ 2.3
- for ループ内の i 番目のインデックスと左側のインデックスの文字を交換します。

• ステップ 2.4
- 同じ引数と「left 1」インデックスを使用して、「getBinaryPermutations」関数を再度呼び出します。

• ステップ 2.5
- バックトラックの目的で、i 番目のインデックスと左のインデックスにある文字を交換します。

• ステップ 3
- 「allDecimals」というコレクションを作成します。その後、バイナリ文字列のすべての置換を繰り返します。

• ステップ 4
- bToD() 関数を呼び出して、2 進数を 10 進数に変換します。

• ステップ 4.1
- bToD() 関数で、10 進変数を値 0 で初期化します。

• ステップ 4.2
- for ループを使用してバイナリ文字列を末尾から繰り返し、「(num[i] - '0') * pow(2, j )」を追加して変換します10 進数値に変換します。

• ステップ 4.3
- 10 進数値を返します。

• ステップ 5
- 「getDecimalPermutations」関数に、bToD() 関数から返された 10 進数値を挿入します。

• ステップ 6
- 一意の 10 進数値を含むセットのすべての値を出力します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

• 時間計算量

  - O(n!)。すべての順列を見つけるためにバックトラッキングを使用するため、「getBinaryPermutations()」関数の時間計算量は「n!」です。 bToD() 関数の時間計算量は O(n) です。

• 空間複雑度

  - O(n!)。各文字列には n! 順列があり、それをリストに保存します。

方法 2

• このアプローチでは、バックトラッキング メソッドの代わりに C の next_permutation() 関数を使用してバイナリ文字列の置換を生成します。また、2進数から10進数への変換方法も変更しました。 ＃＃＃アルゴリズム＃＃＃

ステップ 1

- 「allNumbers」セットを定義します。

• ステップ 2

  - sort() メソッドは、バイナリ文字列を並べ替えるために使用されます。

• ステップ 3

  - do-while ループを使用して、文字列の各順列を反復処理します。

ステップ 4

- do-while ループで、文字列を引数として渡して bToD() 関数を呼び出し、2 進数を 10 進数に変換します。

ステップ 4.1

- bToD() 関数で、「currentBase」変数を定義し、1 に初期化します。

• ステップ 4.2
- for ループを使用し、最後のインデックスから文字列を繰り返します。

• ステップ 4.3
- for ループで、現在の文字が '1' に等しい場合、currentBase の値を '10 進数' に追加する必要があります。

• ステップ 4.4
- currentBase を 2 で乗算します。

• ステップ 5
- 「allNumber」セットに 10 進数を挿入します。

• ステップ 6
- do-while ループの条件で next_permutation() メソッドを使用します。これは、文字列の次の順列が存在する場合に true を返すためです。

• ステップ 7
- 「allNumbers」に追加されたすべての数値を出力して、指定されたバイナリ文字列のすべての順列に関連付けられた一意の 10 進数を取得します。

示例

#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() 方法。

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

以上がバイナリ文字列のすべての順列を生成することで得られるさまざまな数値の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。