Hey guys!
I am trying to map the following dictionary <int,List<T>>.
I am trying to get the i-th permutation of an input array, the List<t> being the i-th perm itself.
If I have: Input Array [1,2,3], the 0-th perm would be [1,2,3], the 1-st [1,3,2] and so on...
So, so far, the Dict would have {[0,{1,2,3}] , [1,{1,3,2}]}.
All sounds great, but after i reach i = 2 and need to carry on, I just don't seem to be able
to get the next permutation list back!
Help!
public class LehmerCode<T>
{
public LehmerCode() { }
private List<int> GetFactorial(int nthPerm, ref List<T> InputArray)
{
int arraySize = InputArray.Count();
List<int> res = new List<int>(arraySize);
int a = nthPerm;
int b = 1;
int c = 99999; //dummy value != 0
//a:b = c rem d
while (c != 0 && b <= arraySize)
{
c = a / b;
res.Add(a % b);
a = c;
b++;
}
//Ako vo nekoj cekor sme dosle do rezultat 0, ne mora da znaci deka
//postapkata e zavrsena
//togas, rezultantnata lista treba da se dopolni so 0-li;
if (res.Count < arraySize)
{
int lastIndex = res.IndexOf((res.Last()));
for (int i = 0; i < arraySize - lastIndex - 1; i++)
{
res.Add(0);
}
}
res.Reverse();
return res;
}
private List<T> MapFactorialToPermutation(List<int> input, ref List<T> InputArray)
{
List<T> tmp = InputArray;
List<T> res = new List<T>(InputArray.Count);
if (input.Count == 0) { return null; }
else
{
foreach (var t in input)
{
res.Add(tmp[t]);
tmp.RemoveAt(t);
}
return res;
}
}
private int Factorial(int n)
{
if (n == 0) return 1;
else return n * Factorial(n - 1);
}
public Dictionary<int, List<T>> GetAllPermutations(List<T> input)
{
Dictionary<int, List<T>> res = new Dictionary<int, List<T>>();
res.Add(0, input);
int nth_Perm = Factorial(input.Count);
for (int i = 1; i < nth_Perm; i++)
{
res.Add(i, MapFactorialToPermutation(GetFactorial(i, ref input),ref input));
}
return res;
}
}
