所有排列

Question

由不明確提出的問題的啓發的高效計算，就覺得挑戰是要解決它的更硬的解釋，這是如下：

怎樣計算最有效的所有可能的整數值含有（32位值）正好n零（0位）？例如，給定N = 7，含有不同的整數值的數目恰好零是：用恰好7零

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

一個例子的整數值將是：

11111111000000011111111111111111 

在如果您想自己解決問題，請避免閱讀我的答案。否則，評估我的答案，改進它或發佈更好，更有效的答案。

Answer 1

我的算法的想法如下：

1. 在給出的函數permut()權（至少顯著位）創建與儘可能多的零整數值。
2. 開始左移最左側的位。
3. 將移動零點右側的所有位作爲目標值，將相同的算法應用於縮短的值。

的算法有兩個重要特徵：

• 這是遞歸
• 它需要儘可能多的計算作爲值來計算

這裏的算法Java代碼：

public static void main(String[] args) { 
    List<Integer> permutations = permut(7); 
} 

private static List<Integer> permut(int zeros) { 
    List<Integer> permutations = new ArrayList<>(); 
    permut(zeros == 32 ? 0 : 0xFFFFFFFF << zeros, zeros, 31, permutations); 
    return permutations; 
} 

/* 
* @param value 
*  for which to move the zero digit at bit position (zeros - 1) 
*  to the stopBit position 
* @param zeros 
*  number of 0 digits available at the right most bit positions 
*  of value 
* @param stopBit 
*  the left most bit position to move the zero digit at bit position 
*  (zeros - 1) to 
* @param values 
*  to add the newly calculated integer values to 
*/ 
private static void power(int value, int zeros, int stopBit, List<Integer> values) { 
    values.add(value); 
    if (zeros == 0) return; 
    int cleared = value | (1 << (zeros - 1)); 
    for (int bit = zeros - 1; bit < stopBit;) { 
     power(cleared^(1 << ++bit), zeros - 1, bit - 1, values); 
    } 
} 

如果你是好奇，如果該算法正確行爲，嘗試與改性main()方法如下檢查方法：

public static void main(String[] args) { 
    int zeros = 7; 
    List<Integer> permutations = permut(zeros); 
    System.out.println("Expected number of values: " + combinations(zeros)); 
    System.out.println("Returned number of values: " + permutations.size()); 
    System.out.println("Returned values are unique: " + (new HashSet<>(permutations).size() == permutations.size())); 
    System.out.printf("All values contain %d zeros: %s\n", zeros, haveZeros(zeros, permutations)); 
} 

private static long combinations(int zeros) { 
    long p = 1; 
    long q = 1; 
    for (int count = 0; count < zeros;) { 
     p *= (32 - count); 
     q *= (++count); 
    } 
    return p/q; 
} 

private static boolean haveZeros(int zeros, List<Integer> values) { 
    for (Integer value : values) { 
     int count = 0; 
     for (int bit = 1; bit != 0; bit = bit << 1) { 
      if ((value & bit) == 0) count++; 
     } 
     if (count != zeros) { 
      System.out.println(Integer.toBinaryString(value)); 
      return false; 
     } 
    } 
    return true; 
} 

Answer 2

假設要列舉的實際號碼，可以簡單地創建大小爲32的字符數組與恰好n 0 ，然後排列陣列

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以加快速度。