0

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;
        }
    }
2
Contributors
1
Reply
15
Views
2 Years
Discussion Span
Last Post by ddanbe
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.