來自陣列的3個值的組合

Question

var example = new[]{1, 1, 1, 0, 1, 1} 

我想要生成一個所有數組的數組，這個數組有三個1組成的數組，這些數組有0個，所有其他位置都是0。

在這個例子中，這些將是：

1 1 1 0 0 0 
1 1 0 0 1 0 
1 1 0 0 0 1 
1 0 1 0 1 0 
1 0 1 0 0 1 
1 0 0 0 1 1 
0 1 1 0 1 0 
0 1 1 0 0 1 
0 1 0 0 1 1 
0 0 1 0 1 1 

代碼我寫了嘗試這成爲極長而凌亂，顯然有更好的辦法。

使用「計數器」那坐着的原始數組的位置，我試圖和感動，像這樣：

1 1 1 0 1 1 
c c c 
c c  c 
c c  c 
c c c 

等等

Answer 1

如果陣列相對較短（這是它應該要避免溢出內存），你可以用二進制計數來構建和算法，你正在尋找：

• 假設原來的數組元素N
• 將數組轉換爲int將每個位置視爲二進制數字;稱之爲set
• 設置一個mask數字，該數字在從0到(1 << N)-1（含）的循環中計數。這種面膜產生可以從原始
• 採取產生mask組合和set由位的所有可能的組合和-ING兩個：int candidate = mask & set
• 檢查多少位是如何在candidate
• 如果設置設置位的數量正好是三個，將candidate添加到列表中
• 一旦循環結束，您的列表表示爲int s。
• 消除重複項，並根據需要將這些int s轉換爲int s的數組。

下面是一個簡單的實現上述算法：

static uint FromArray(int[] data) { 
    uint res = 0; 
    for (int i = 0 ; i != data.Length ; i++) { 
     if (data[i] == 1) { 
      res |= (1U << i); 
     } 
    } 
    return res; 
} 
static int[] ToArray(uint set, int size) { 
    var res = new int[size]; 
    for (int i = 0 ; i != size ; i++) { 
     if ((set & (1U << i)) != 0) { 
      res[i] = 1; 
     } 
    } 
    return res; 
} 
static int CountBits(uint set) { 
    int res = 0; 
    while (set != 0) { 
     if ((set & 1) != 0) { 
      res++; 
     } 
     set >>= 1; 
    } 
    return res; 
} 
public static void Main() { 
    var example = new[]{1, 1, 1, 0, 1, 1}; 
    var set = FromArray(example); 
    int N = example.Length; 
    var res = new List<uint>(); 
    for (uint mask = 0 ; mask != 1U<<N ; mask++) { 
     var candidate = set & mask; 
     if (CountBits(candidate) == 3) { 
      res.Add(candidate); 
     } 
    } 
    foreach (var s in res.Distinct()) { 
     var array = ToArray(s, N); 
     Console.WriteLine(string.Join(" ", array.Select(i => i.ToString()).ToArray())); 
    } 
} 

此代碼產生以下輸出：

1 1 1 0 0 0 
1 1 0 0 1 0 
1 0 1 0 1 0 
0 1 1 0 1 0 
1 1 0 0 0 1 
1 0 1 0 0 1 
0 1 1 0 0 1 
1 0 0 0 1 1 
0 1 0 0 1 1 
0 0 1 0 1 1 

Demo on ideone.