用于重复的集合的堆算法

Question

对于（N个选择K）问题，我得到了一个数组，长度为=（N个选择K）* K（我通过沿行方向将其扁平化了二维数组），每个数字都包含1到N（N个选择K）* K / N次。

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中可能会迅速导致性能和内存问题。您可以考虑使用一种完全不产生重复项的方法。以下代码基于strategy-to-modify-permutation-algorithm-to-prevent-duplicate-printouts：

    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是唯一的。