C ++での混乱のカウント（元の位置に要素が表示されないような順列）

混乱とは、元の位置に数字が表示されないようにN個の数字を並べ替えることです。たとえば、{1,2,3}の考えられる混乱の1つは、{1,1,3}です。この中の要素は元の位置にありません。ここでの目標は、N個の数字の混乱の可能性を数えることです。

これは、再帰的なソリューションを使用して行います。以下の番号について。要素の-

• N =0、混乱なし、1を返します
• N =1、1つの数値のみ、0を返します
• N =2、可能な位置の交換は1つだけ、{1,2}→{1,1}、1を返す
• N =3、2つの可能な順列、例：{1,2,3}→{1,3,1}、{3,1,2}カウント2
• N =4、9つの可能な順列
• .......................
• N、（N-1）*（順列（N-1）+順列（N-2））

配列内のすべての要素について、

• インデックス0の要素には、n-1個の位置があります。

• インデックスiの要素がインデックス0に配置されている場合、arr[i]とarr[0]が交換されます。これで、計算用にn-2個の要素があります。

• インデックスiの要素がインデックス0に配置されていない場合、n-1個の要素にはn-2個の選択肢があります。

図

入力

Arr[] = { 1, 2 }

出力

No. of derangements : 1

説明 − 1と2の位置はインデックス0と1です。取得できる位置は、元の位置を交換することだけです。 {2,1}

入力

Arr[] = { 1, 2, 3 }

出力

No. of derangements : 2

説明 − 1、2、および3の位置はインデックス0、1、2です。

1はインデックス1と2に配置でき、2はインデックス0と3に配置でき、3はインデックス0と1に配置できます。

{2,3,1}と{3,1,2}は2つの混乱です。

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

• Integer Numは、存在する数値の数を格納します。

• 再帰関数derangements（int N）は、数値のカウントを入力として受け取り、noを返します。混乱の。

• N =0,1,2のreturnステートメントは、順列がすでに1,0および1として計算されている基本ケースを処理しています。

• N> 2の場合、derangements（）の再帰呼び出しは、式を使用して行われます。

  （N-1）*（混乱（N-1）+混乱（N-2））。

バックトラックが開始されると、カウントが計算されて返されます。

例

#include <bits/stdc++.h>
using namespace std;
int derangements(int N){
   if (N == 0)
      return 1;
   if (N == 1)
      return 0;
   if (N == 2)
      return 1;
   return (N - 1) * (derangements(N - 1) + derangements(N - 2));
}
int main(){
   int Numbers=5;
   cout<<"Number of Derangements :"<<derangements(Numbers);
}

出力

Number of Derangements :44