すべての順列がC++のその数よりも大きい自然数を数えます

たとえば、numという自然数が与えられます。タスクは、すべての順列がその数よりも大きいすべての自然数の数を計算することです。

次の条件で作業しています −

• データは自然数のみである必要があります

• 自然数のすべての可能な順列または配置は、指定された数以上である必要があります。たとえば、数は20です

  • 1から始まる20までのすべての数字を考慮してください。つまり、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20

  • 次に、配置または順列が指定された数、つまり20以上の数を確認します。数は1、2、3、4、5、6、7、8、9、11 =11、12 <21、13<31です。 、14 <41、15 <51、16 <61、17 <71、18 <81、19<91。したがって、カウントは18になります。

入力 − num =10

出力 −カウントは9

説明 −数字1、2、3、4、5、6、7、8、9は、任意の方法で配置した場合の数字と等しい数字です。

入力 − num =13

出力 −カウントは12

説明 −数字1、2、3、4、5、6、7、8、9、11、12 <21、13 <31は、任意の方法で配置した場合の数字よりも大きい数字です。

以下のプログラムで使用されているアプローチは次のとおりです

• 数値numの値を入力します

• max_sizeを9に設定します。これは、その数自体と同じかそれ以上の順列を持つ少なくとも9つの数が常に存在するためです。

• 0からmax_sizeまでループを開始します

• ループ内で、リスト型変数を作成し、iがnum以下であるかどうかを確認します。はいの場合は、iをリストに挿入し、カウントを1ずつ増やします。

• リストを最後から最初までトラバースし、最初の要素から9まで別のループを開始します。

• temp <=numかどうかを確認してから、リストの先頭にあるtempを押して、カウントを1増やします

  。

• カウントを返す

• 結果を印刷します。

例

#include<bits/stdc++.h>
using namespace std;
//function to Count natural numbers whose
//all permutation are greater than that number
void count(int num){
   int count = 0;
   int max_size = 9;
   for (int i = 1; i <= max_size; i++){
      list<int> lists;
      if (i <= num){
         //insert element at the end of the list
         lists.push_back(i);
         count = count + 1;
      }
      //iterator starts from the last of the list
      for(auto iter = lists.end(); iter != lists.begin(); ++iter){
         int first_ele = lists.front();
         lists.pop_front();
         for (int next = first_ele%10; next <= 9; next++){
            int temp = first_ele*10 + next;
            if (temp <= num){
               lists.push_front(temp);
               count++;
            }
         }
      }
   }
   cout<<"count of num "<<num <<" is "<<count<<endl;
}
int main(){
   count(1);
   count(9);
   count(7);
   count(0);
   count(12);
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます-

count of num 1 is 1
count of num 9 is 9
count of num 7 is 7
count of num 0 is 0
count of num 12 is 11