1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
|
void PowerSet(int size, int *elements)
{
int bestSize;
int *R;
int *bestSet;
R = new int[size];
bestSet = new int[size + 1];
bestSize = 0;
printPSet(size, bestSet, bestSize, elements);
for (int i = 0; i < bestSize; i++)
{
R[i] = elements[bestSet[i + 1] - 1];
}
cout << "The longest non-decreasing subsequence has length: " << bestSize << endl;
cout << "The longest non-decreasing subsequence is: ";
printSeq(bestSize, R);
delete[] elements;
delete[] R;
}
void printSeq(int size, int *seq)
{
for (int i = 0; i < size; i++)
{
cout << seq[i] << " ";
}
cout << endl;
}
void printPSet(int size, int *&best, int &bestSize, int *ele)
{
int *stack;
int k = 0;
stack = new int[size + 1];
stack[0] = 0; //initialize first element since not considered as part of set
while (1)
{
if (stack[k] < size)
{
stack[k + 1] = stack[k] + 1;
k++;
}
else
{
stack[k - 1]++;
k--;
}
if (k == 0)
{
break;
}
}
checkSet(stack, k, best, bestSize, ele);
delete[] stack;
}
void checkSet(int *stack, int k, int *&best, int &bestSize, int *ele)
{
if (k < 2) //check if indices instack generate subsequence of non-dec
{
//this means the set contains isngle index, so it is in non-dec
if (k > bestSize) //means we found better set
{
//store stack into best set, update bestsize to k
for (int i = 0; i < k; i++)
{
best[i] = stack[i];
}
bestSize = k;
return;
}
}
else //means set contains more than single index
{
for (int i = 0; i < k - 1; i++)
{
if (ele[stack[i + 1] - 1] <= ele[stack[i + 2] - 1])
{
//do nothing
}
else
{
return;
}
}
}
//we have non-dec so we check it against best set
if (k > bestSize)
{
//we found a better set
//store stack into best set, update bestsize to k
for (int i = 0; i < k; i++)
{
best[i] = stack[i];
}
bestSize = k;
return;
}
else
{
return;
}
}
|