java对所有置换的高效计算

Question

受到一个模棱两可的问题的启发，我觉得有必要解决更难的解释，具体如下：

如何最有效地计算所有可能的整数值（32位值），精确地包含n零（0位）？例如，给定n=7，正好包含7零的不同整数值的数量为：

32*31*30*29*28*27*26 / (1*2*3*4*5*6*7) = 3.365.856

具有7个零的整数值示例如下：

11111111000000011111111111111111

如果你想自己解决这个问题，避免阅读我的答案。否则，请评估我的答案，改进它，或者发布一个更好、更有效的答案

Answer 1

假设您想枚举实际的数字，只需创建一个大小为32且正好为n0的字符数组，然后排列该数组

import java.io.*;
import java.util.*;

public class Solution
{

    static char [] arr;
    public static void main(String[]args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new char[5];
        for(int i = 0; i < arr.length; i++)
        {
            if(n > 0)
            {
                arr[i] = '0';
                n ;
            }
            else
                arr[i] = '1';
        }
        permute(0);
    }

    public static void permute(int i)
    {
        if(i >= arr.length)
        {
            System.out.println(arr);
            return;
        }

        int [] dups = new int[2];

        for(int j = i; j < arr.length; j++)
        {
            if(dups[arr[j]-'0'] == 1)
                continue;
            dups[arr[j]-'0'] = 1;
            char temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            permute(i+1);
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}

它很慢，因为有m！排列，其中m是数组的大小。我将大小设置为5以加快速度