/*
*
* written by: Gregor Kronenberger
* Drizzt81
*
*
* MA 2733
*
*/
#include
#include
//#include
#include
using namespace std; //more vector stuff
list A;
int Permute(int* alist, int Size);
int Swap(int* src, int* target);
int PrintList(int* alist, int Size);
bool IsSpecial(int* alist, int Size);
int max();
int main(int argc, char *argv[])
{
int iSpecial= 0;
if(argc != 2)
{
cout <<"Usage: Display \n";
return 1;
}
//argv[1] = 'n'
int n;
n = atoi(argv[1]);
int* iArray, *iInvArray, *d;
iArray = new int[n+2];
iInvArray = new int[n+2];
d = new int[n+2];
for(int j1 = 1; j1 <= n+1; j1++)
{
iArray[j1] = j1;
iInvArray[j1] = j1;
d[j1] = -1;
}
iArray[0] = n +1;
bool Done = false;
for(int k = 2; k <= n; k++)
{
A.push_back(k);
}
int m, iCounter;
while(!Done)
{
if(IsSpecial(iArray, n))
{
PrintList(iArray, n);
iSpecial++;
}
if(!A.empty())
{
m = max();
int j;
j = iInvArray[m];
iArray[j] = iArray[j + d[m]];
iArray[j + d[m]] = m;
iInvArray[m] = iInvArray[m] + d[m];
iInvArray[iArray[j]] = j;
if(m < iArray[j+2*d[m]])
{
d[m] = -d[m];
A.remove(m);
}
//A = A union {m+1...n}
for(iCounter = m+1; iCounter <= n; iCounter++)
{
A.push_back(iCounter);
}
A.sort(); //sorts the list
A.unique(); //eliminates duplicates
}
else
Done = true;
}
//PrintList(iArray, i);
//iSpecial = Permute(iArray, n);
cout <<"The size n was " <
cout <<"Within all the permuations of [n] there were" <
cout <<"exactly: " <
delete [] iArray;
delete [] iInvArray;
delete [] d;
return 0;
}
int Permute(int* alist, int Size)
{
int iSpecialNumbers = 0;
int iOutside = 0;
int iInside = 0;
int inLoop = Size-1;
int nFactorial = 1;
for(iOutside = (Size-1); iOutside > 1; iOutside--)
{
nFactorial = iOutside * nFactorial;
}
for(iOutside = 1; iOutside <= nFactorial; iOutside++)
{
//if(IsSpecial(list, Size))
//{
iSpecialNumbers++;
PrintList(alist, Size);
//}
if(iOutside % 2)
{
for(iInside = 1; iInside < Size; iInside++)
{
Swap(&alist[Size-iInside], &alist[Size-iInside-1]);
// if(IsSpecial(list, Size))
// {
iSpecialNumbers++;
PrintList(alist, Size);
// }
}
Swap(&alist[Size-1], &alist[Size-2]);
}
else
{
for(iInside = 1; iInside < Size; iInside++)
{
Swap(&alist[iInside-1], &alist[iInside]);
// if(IsSpecial(list, Size))
// {
iSpecialNumbers++;
PrintList(alist, Size);
// }
}
Swap(&alist[0], &alist[1]);
}
cout <
//inLoop
}
return iSpecialNumbers;
}
int Swap(int* src, int* target)
{
int tmp;
tmp = *target;
*target = *src;
*src = tmp;
return 1;
}
int PrintList(int* alist, int Size)
{
for(int j = 1; j <= Size; j++)
{
cout.width(3);
cout <
}
cout <
return 1;
}
bool IsSpecial(int* alist, int Size)
{
bool* used;
used = new bool[Size];
int iCounter = 0;
int iResult;
int iTmp;
for(iCounter = 0; iCounter < Size; iCounter++)
used[iCounter] = false;
for(iCounter = 0; iCounter < Size; iCounter++)
{
iResult = (alist[iCounter] - (iCounter+1)) % Size;
if(iResult < 0)
{
iTmp = (abs((alist[iCounter] - (iCounter+1)))) % Size;
if(iTmp == 0)
{
iResult = 0;
}
else
{
iResult = Size - iTmp;
}
}
if(used[iResult])
{
delete [] used;
return false;
}
else
used[iResult] = true;
}
delete [] used;
return true;
}
int max()
{
int temp = -2;
list::iterator list_Iter;
list_Iter = A.begin();
while(list_Iter != A.end())
{
if(*list_Iter > temp)
temp = *list_Iter;
list_Iter++;
}
return temp;
}
___________________
get font
I see your 4 Crushs and raise you 3 As The Rush Comes. - Yan from PvD's first summerstage event in '03
|