如何高效生成由0和1组成的数组的唯一排列

问题背景 #

需求：生成由0和1组成的数组的所有唯一排列，示例数组如下：

int[] arr = { 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

现有C#代码可生成排列，但因交换相同的0或1产生大量无意义重复，数组规模较大时耗时极久，需要在生成前跳过重复以提升效率。注：组合无法满足需求（如数组{1,0}需生成{1,0}和{0,1}两种排列），不局限于修改现有代码。

高效解决方案推荐：直接基于位置选择生成唯一排列 #

由于数组只有0和1两种元素，唯一排列的本质就是选择k个位置放置1，剩余位置自动为0（k是原数组中1的总数）。这种方式完全跳过了重复排列的可能，不需要先生成全排列再去重，是效率最高的方案。

代码实现 #

static IEnumerable<int[]> GenerateUniqueBinaryPermutations(int[] arr)
{
    int totalLength = arr.Length;
    int oneCount = arr.Count(x => x == 1);
    
    // 生成所有含oneCount个1的位置组合，据此构建排列
    foreach (var positions in GetCombinations(totalLength, oneCount))
    {
        int[] permutation = new int[totalLength];
        foreach (int pos in positions)
        {
            permutation[pos] = 1;
        }
        // 未赋值的位置默认是0，无需额外处理
        yield return permutation;
    }
}

// 辅助方法：生成从0到n-1中选k个元素的所有位置组合
static IEnumerable<int[]> GetCombinations(int n, int k)
{
    int[] result = new int[k];
    Stack<int> stack = new Stack<int>();
    stack.Push(0);
    
    while (stack.Count > 0)
    {
        int index = stack.Count - 1;
        int value = stack.Pop();
        
        while (value < n)
        {
            result[index] = value;
            if (index == k - 1)
            {
                yield return (int[])result.Clone();
                value++;
            }
            else
            {
                stack.Push(++value);
                index++;
            }
        }
    }
}

效率说明 #

以示例数组为例，原数组有5个1、20个0，唯一排列总数是组合数C(25,5)=53130。原全排列方法会尝试生成25!次循环（天文数字级别的无用计算），而这个方法直接生成53130个有效结果，完全避免了重复计算。

备选方案：修改原全排列逻辑避免重复 #

如果一定要基于原有的全排列框架修改，可以通过在NextPermutation中跳过相同元素的交换来避免生成重复排列。核心是先将数组排序（让相同元素相邻），然后在找交换位置时跳过相同值的元素。

修改后的代码 #

static IEnumerable<int[]> GeneratePermutations(int[] arr)
{
    // 先排序数组，确保相同元素相邻，这是去重的前提
    int[] sortedArr = (int[])arr.Clone();
    Array.Sort(sortedArr);
    
    int n = sortedArr.Length;
    int[] indexes = Enumerable.Range(0, n).ToArray();
    int[] currentPermutation = (int[])sortedArr.Clone();

    yield return currentPermutation;

    while (NextUniquePermutation(indexes, sortedArr))
    {
        for (int i = 0; i < n; i++)
        {
            currentPermutation[i] = sortedArr[indexes[i]];
        }
        yield return currentPermutation;
    }
}

static bool NextUniquePermutation(int[] indexes, int[] arr)
{
    int n = indexes.Length;
    int i = n - 2;

    // 找到第一个比后一个元素小的位置i，跳过连续相同的元素
    while (i >= 0 && arr[indexes[i]] >= arr[indexes[i + 1]])
    {
        while (i >= 1 && arr[indexes[i]] == arr[indexes[i - 1]])
        {
            i--;
        }
        i--;
    }

    if (i == -1)
    {
        return false; // 所有排列已生成
    }

    int j = n - 1;
    // 找到第一个比indexes[i]对应值大的位置j
    while (arr[indexes[j]] <= arr[indexes[i]])
    {
        j--;
    }

    Swap(ref indexes[i], ref indexes[j]);

    // 反转i+1到末尾，同时跳过相同元素优化
    int left = i + 1;
    int right = n - 1;
    while (left < right)
    {
        Swap(ref indexes[left], ref indexes[right]);
        // 跳过左边连续相同元素
        while (left < right && arr[indexes[left]] == arr[indexes[left + 1]])
        {
            left++;
        }
        // 跳过右边连续相同元素
        while (left < right && arr[indexes[right]] == arr[indexes[right - 1]])
        {
            right--;
        }
        left++;
        right--;
    }

    return true;
}

static void Swap(ref int a, ref int b)
{
    int temp = a;
    a = b;
    b = temp;
}

注意事项 #

必须先对数组排序，让相同元素相邻，否则去重逻辑无法生效。这种方法比原代码高效，但仍不如第一种方法，因为本质还是基于排列逻辑，只是减少了重复步骤。

内容的提问来源于stack exchange，提问作者Pato Srna