Алгоритм кучи для коллекций с дубликатами

Question

Для задачи (N выберите K) я получил массив с длиной = (N выберите K) * K (я сплющил двумерный массив путем объединения линий), содержащий цифры от 1 до N каждая (N выберите K) * К / ш раз.

int []a = {4,4,4,3,3,3,2,2,2,1,1,1}; 

Я хочу собрать и посчитать все различные перестановки. Существует ли модификация алгоритма Heap, которая бы препятствовала созданию дубликатов (не меняя цифры одного и того же значения), или я лучший способ просто запустить Heap и собрать результаты в HashSet?

public class GFG { 
//Prints the array 
static void printArr(int []a, int n) 
{ 
    for (int i=0; i<n; i++) 
        Console.Write(a[i] + " "); 
    Console.WriteLine(); 
} 

//Generating permutation using Heap Algorithm
//Source: GeeksForGeeks


static void heapPermutation(int []a, int size, int n) 
{ 
    // if size becomes 1 then prints the obtained 
    // permutation 
    if (size == 1) 
        printArr(a,n); 

    for (int i=0; i<size; i++) 
    { 
        heapPermutation(a, size-1, n); 

        // if size is odd, swap first and last 
        // element 
        if (size % 2 == 1) 
        { 
            int temp = a[0]; 
            a[0] = a[size-1]; 
            a[size-1] = temp; 
        } 

        // If size is even, swap ith and last 
        // element 
        else
        { 
            int temp = a[i]; 
            a[i] = a[size-1]; 
            a[size-1] = temp; 
        } 
    } 
} 

// Driver code 
public static void Main() 
{ 

    int []a = {4,4,4,3,3,3,2,2,2,1,1,1}; 
    heapPermutation(a, a.Length, a.Length); 
} 
} 

Answer 1

В зависимости от длины массива, сбор результата в HashSet может быстро вызвать проблемы с производительностью и памятью. Вы могли бы рассмотреть другой подход, который вообще не генерирует дубликаты. Следующий код основан на стратегии "алгоритм для изменения-перестановки-алгоритм-для-предотвращения-дублирования-распечатки" :

    public static void Main()
    {
        //int[] x = new int[]{4,4,4,3,3,3,2,2,2,1,1,1};
        int[] x = new int[] { 1, 2, 2 };
        PermutationsWithoutDuplicates(x);
        Console.ReadLine();
    }

    static void printArr(int[] a)
    {
        for (int i = 0; i < a.Length; i++)
            Console.Write(a[i] + " ");
        Console.WriteLine();
    }

    public static void PermutationsWithoutDuplicates(int[] a)
    {
        HashSet<int> hs = new HashSet<int>(a);
        int[] uniquekeys = hs.ToArray();

        Dictionary<int, int> next_fixable = new Dictionary<int, int>(uniquekeys.Length);
        Dictionary<int, int> count = new Dictionary<int, int>(uniquekeys.Length);
        foreach (int i in uniquekeys)
        {
            next_fixable.Add(i, 0);
            count.Add(i, 0);
        }

        int[] int_number = new int[a.Length];
        for (int i = 0; i < a.Length; i++)
        {
            int_number[i] = count[a[i]];
            count[a[i]] += 1;
        }

        Permute(a, next_fixable, int_number, 0, a.Length);
    }

    static void Permute(int[] a, Dictionary<int, int> next_fixable, int[] int_number, int begin, int end)
    {
        if (end == begin + 1)
            printArr(a);
        else
        {
            for (int i = begin; i < end; i++)
            {
                if (next_fixable[a[i]] == int_number[i])
                {
                    next_fixable[a[i]] += 1;

                    // swap
                    int temp = int_number[begin];
                    int_number[begin] = int_number[i];
                    int_number[i] = temp;

                    // swap
                    temp = a[begin];
                    a[begin] = a[i];
                    a[i] = temp;

                    Permute(a, next_fixable, int_number, begin + 1, end);

                    // swap
                    temp = a[begin];
                    a[begin] = a[i];
                    a[i] = temp;

                    // swap
                    temp = int_number[begin];
                    int_number[begin] = int_number[i];
                    int_number[i] = temp;

                    next_fixable[a[i]] -= 1;
                }
            }
        }
    }

Если вы используете {4,4,4,3 , 3,3,2,2,2,1,1,1} в качестве входных данных имеется 479,001,600 перестановок, в то время как только 369,600 являются уникальными.

Я измерил следующие значения (без Console.Write (. ..)):

• Ваш алгоритм кучи (без использования HashSet): 13,73 se c
• Предлагаемый выше подход: 0,08 se c

Тем не менее, следующая строка все еще стоит много производительности, так как next_fixable является словарем:

if (next_fixable [a [i]] == int_number [i])

Следующий подход представляет собой обобщенный вариант c (принимает строку, int или любой другой сопоставимый тип), который преобразует массив intput в массив int, основанный на нуле. Например, {22, 5, 5, 63} становится {1, 0, 0, 2}, вместо этого помещая {22, 5, 5, 63} в словарь. Конечно, во время перестановки выходной массив преобразуется обратно во входной формат. {0, 0, 2, 1} становится {5, 5, 63, 22}. Поскольку массивы намного быстрее словарей, время выполнения увеличивается с 0,08 сек c до 0,03 сек c. Если входной массив не содержит дубликатов, используется более быстрый алгоритм кучи.

    class Program
    {
        public static void Main()
        {
            //int[] x = new int[] { 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1 };
            int[] x = new int[] { 1, 2, 2 };

            PermutationTool<int> tool = new PermutationTool<int>(printArr);
            tool.PermutationsWithoutDuplicates(x);

            Console.ReadLine();
        }

        static void printArr(int[] a)
        {
            for (int i = 0; i < a.Length; i++)
                Console.Write(a[i] + " ");
            Console.WriteLine();
        }
    }

    class PermutationTool<T> where T : IComparable
    {
        T[] _uniquekeys;
        Action<T[]> _callback;

        public PermutationTool(Action<T[]> callback)
        {
            _callback = callback;
        }

        public void PermutationsWithoutDuplicates(T[] a)
        {
            HashSet<T> hs = new HashSet<T>(a);
            List<T> sortedlist = new List<T>(hs.ToArray());
            Dictionary<T, int> map = new Dictionary<T, int>();

            sortedlist.Sort();
            _uniquekeys = sortedlist.ToArray();

            for (int i = 0; i < _uniquekeys.Length; i++)
            {
                map.Add(_uniquekeys[i], i);
            }

            int[] a2 = new int[a.Length];

            for (int i = 0; i < a.Length; i++)
                a2[i] = map[a[i]];

            int[] next_fixable = new int[_uniquekeys.Length];

            Dictionary<int, int> count = new Dictionary<int, int>(_uniquekeys.Length);
            for (int i = 0; i < _uniquekeys.Length; i++)
            {
                count.Add(i, 0);
            }

            int[] int_number = new int[a2.Length];
            for (int i = 0; i < a2.Length; i++)
            {
                int_number[i] = count[a2[i]];
                count[a2[i]] += 1;
            }

            hs.Clear();
            sortedlist.Clear();
            count.Clear();

            if (_uniquekeys.Length != a.Length)
                PermutationWithoutDuplicates(a2, next_fixable, int_number, 0, a2.Length);
            else
                HeapPermutation(a2, a2.Length); //all permutation are unique, switch to the faster heap algorithm
        }

        private void PermutationWithoutDuplicates(int[] a, int[] next_fixable, int[] int_number, int begin, int end)
        {
            if (end == begin + 1)
                FoundPermutation(a);
            else
            {
                for (int i = begin; i < end; i++)
                {
                    if (next_fixable[a[i]] == int_number[i])
                    {
                        next_fixable[a[i]] += 1;

                        // swap
                        int temp = int_number[begin];
                        int_number[begin] = int_number[i];
                        int_number[i] = temp;

                        // swap
                        temp = a[begin];
                        a[begin] = a[i];
                        a[i] = temp;

                        PermutationWithoutDuplicates(a, next_fixable, int_number, begin + 1, end);

                        // swap
                        temp = a[begin];
                        a[begin] = a[i];
                        a[i] = temp;

                        // swap
                        temp = int_number[begin];
                        int_number[begin] = int_number[i];
                        int_number[i] = temp;

                        next_fixable[a[i]] -= 1;
                    }
                }
            }
        }

        private void HeapPermutation(int[] a, int size)
        {
            if (size == 1)
                FoundPermutation(a);

            for (int i = 0; i < size; i++)
            {
                HeapPermutation(a, size - 1);

                if (size % 2 == 1)
                {
                    int temp = a[0];
                    a[0] = a[size - 1];
                    a[size - 1] = temp;
                }
                else
                {
                    int temp = a[i];
                    a[i] = a[size - 1];
                    a[size - 1] = temp;
                }
            }
        }

        private void FoundPermutation(int[] a)
        {
            if (_callback != null)
            {
                T[] p = new T[a.Length];

                for (int i = 0; i < a.Length; i++)
                    p[i] = _uniquekeys[a[i]];
                _callback(p);
            }
        }
    }