#include <cliext/algorithm>
#using <c:\Program Files\Reference Assemblies\Microsoft\Framework\v3.5\System.Core.dll>
using namespace cliext;
using namespace System;
using namespace System::Text;
using namespace System::Collections;
using namespace System::Collections::Generic;
public ref class Permu
{
private:
static String^ GetLexicoMinInPermu(array<Char>^ input)
{
array<Char>^ temp = gcnew array<Char>(input->Length);
Array::Copy(input, temp, input->Length);
Array::Sort(temp, 0, temp->Length);
return gcnew String(temp);
}
static String^ GetLexicoMaxInPermu(array<Char>^ input)
{
array<Char>^ temp = gcnew array<Char>(input->Length);
Array::Copy(input, temp, input->Length);
Array::Sort(temp, 0, temp->Length);
Array::Reverse(temp);
return gcnew String(temp);
}
// Lexicographic order algorithm.
static HashSet<String^>^ LexicoSortForPermu(String^ begin, String^ end)
{
HashSet<String^>^ result = gcnew HashSet<String^>();
result->Add(begin);
array<Char>^ temp = begin->ToCharArray();
String^ current = begin;
while(current < end)
{
for (int i = temp->Length – 2; i >= 0; i–)
{
if (temp[i] < temp[i + 1])
{
int index_of_num_gt_min = i + 1;
int j;
for (j = i + 1; j < temp->Length; j++)
{
// If there are duplicated number in array, use the most right one.
if (temp[i] < temp[j] && temp[j] <= temp[index_of_num_gt_min])
{
index_of_num_gt_min = j;
}
}
int temp_0 = temp[index_of_num_gt_min];
temp[index_of_num_gt_min] = temp[i];
temp[i] = temp_0;
// reverse all the numbers start from temp[i + 1]
int begin_index = i + 1;
for (j = temp->Length – 1; j >= begin_index; j–, begin_index++)
{
if (j <= begin_index)
{
break;
}
else
{
int temp_0 = temp[j];
temp[j] = temp[begin_index];
temp[begin_index] = temp_0;
}
}
current = gcnew String(temp);
if (!result->Contains(current))
{
result->Add(current);
}
break;
}
} // end for
} // end while
result->Add(end);
return result;
}
public:
static HashSet<String^>^ Compute(array<Char>^ input)
{
String^ begin = GetLexicoMinInPermu(input);
String^ end = GetLexicoMaxInPermu(input);
return LexicoSortForPermu(begin, end);
}
};
int main(array<System::String ^> ^args)
{
array<Char>^ input = { ‘2’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’};
HashSet<String^>^ result = Permu::Compute(input);
int count = 0;
for each(String^ temp in result)
{
if (temp->Contains("35") || temp->Contains("53") || temp->IndexOf("4") == 3)
continue;
Console::WriteLine(temp);
count++;
}
Console::WriteLine("Total count of Perm result: {0}", result->Count);
Console::WriteLine("Total count of filtered result: {0}", count);
return 0;
}
Yesterday is HISTORY, Tomorrow is MYSTERY. 