#include <bitset>
#include <iostream>
#include <iomanip>
using namespace std;

/*
Achtung: V={0,1,...,n-1}

Modifikation: Nicht pi(1)=1 sondern pi(n)=n,
damit S nur aus {0,1,...,n-2}
*/
const unsigned int n = 24;
const unsigned int zpn = 1<<(n-1); 
unsigned int g[n][zpn];
unsigned int m[n][n];



unsigned long formel(unsigned int i, unsigned long iS){
  bitset<30> S(iS), S2;
  unsigned int minimum=2000000000, m2;
   if (S.none()) return m[i][n-1] ;
   else {
     for (unsigned j=0;j<n-1;j++){
       if (S.test(j)){
           S2=S;
           S2.set(j,0);
           m2=m[i][j]+g[j][S2.to_ulong()];
           if (m2< minimum) minimum=m2;
       }
     }
     return minimum;
   }
};


int main(){

cout << "Parameter: "<< n <<", Teilmengen: "<< zpn<<"\n";

for(unsigned int i=0; i<n;i++) for(unsigned int j=0; j<n;j++) m[i][j]=4;
for(unsigned int i=0; i<n;i++)  m[i][i]=0;
for(unsigned int i=0; i<n-1;i++)  m[i][i+1]=2;  m[n-1][0]=2;


for(unsigned int i=0; i<n-1;i++)
	g[i][0]=formel(i,0);

for (unsigned int k=1; k<= n-2; k++){
    cout << k<< "...\n";
    for (unsigned int iS=1; iS< zpn;iS+=1) {
       bitset<30> S(iS);
         if (S.count()==k) {
         for (unsigned int i=0; i<n-1;i++)
           if (!S.test(i)){
                g[i][iS]=formel(i,iS);
	    };
    }}
}
cout << "\nResultat: "<<formel(n-1, zpn-1) << "\n";

}