如何在分區對象時遍歷所有情況

Question

假設我有k個相同的項目，我想將它們劃分爲n個組。我如何遍歷每一個可能的組合？

到目前爲止，我已經在板子上寫了一些數字。假設k = n = 4，那麼系統地列出它們的方法是查找所有4位數字（其中0可以是數字），其數字合計爲k。按升序排列：

0 0 0 4 
0 0 1 3 
0 0 2 2 
0 0 3 1 
0 0 4 0 
0 1 0 3 
0 1 1 2 
0 1 2 1 
0 1 3 0 
0 2 0 2 
0 2 1 1 
0 2 2 0 
0 3 0 1 
0 3 1 0 
0 4 0 0 
1 0 0 3 
... 

我想避免第一不考慮和發生的所有組合，然後刪除不加起來k是所有組合。由於這會產生k^n個組合，並且可能需要很長時間。不管它是for還是遞歸都沒關係，但它必須相當高效。

Answer 1

我設法通過遞歸和循環的組合找到解決方案。

這裏是僞代碼（我不知道如何寫僞代碼...我表示通過列表[A; B; C ...]：

// Returns a list of integers in range [0, k]. 
function num_list k = 
... 


// Recursively generate all the possible partitions with [total] objects 
// and [groups] partitions. Returns a list of list of integers. 
function generate (int groups, int total) = { 
    if (groups == 1) then { 
     return [[total]]; 
    } else { 
     int list nums = num_list total; 
     // looping through all values for one of the partitions. 
     int list list list container1; 
     foreach (i in nums) { 
      // recursive step - generate all combinations without the first 
      // partition 
      int list list subset = generate (groups - 1) (total - i); 
      // append the first partition onto each element of this list 
      int list list container2 = []; 
      foreach (l in subset) { 
       container2.add(l.prepend i); 
      } 
      container1.add container2; 
     } 
     // Flatten just takes a list of lists, and extract everything in each 
     // list and mesh everything together. 
     return container1.flatten(); 
} 

這裏的代碼蟒蛇：

# Recursively generate all the possible partitions with [total] objects 
# and [groups] partitions. Returns a list of list of integers. 
def generate (groups, total): 
    if (groups == 1): 
     return [[total]]; 
    else: 
     nums = range(total + 1); 
     # looping through all values for one of the partitions. 
     container1 = []; 
     for i in nums: 
      # recursive step - generate all combinations without the first 
      # partition 
      subset = generate (groups - 1, total - i); 
      # append the first partition onto each element of this list 
      container2 = []; 
      for l in subset: 
       container2 += [([i] + l)]; 
      container1 += [container2]; 
     # Flatten just takes a list of lists, and extract everything in each 
     # list and mesh everything together. 
     return [item for sublist in container1 for item in sublist]; 

下面是在...函數式編程語言OCaml的代碼：

(* Returns a list of integers in range [0, k]. *) 
let num_list n : int list = 
    let rec helper num = 
    if num = 0 then 
     [0] 
    else 
     num :: (helper (num - 1)) in 
    List.rev (helper n) 

(** 
* Recursively generate all the combinations when dividing total number of 
* objects among groups. 
*) 
let rec generate groups total : int list list = 
    (* generate all the possible *) 
    match groups, total with 
    | 1, t -> [[t]] 
    | g, t -> 
    let nums = num_list t in 
    (* looping through all values for the head group *) 
    let helper e : int list list = 
     let subset = generate (g - 1) (t - e) in 
     (* appending in front of every single result from generate *) 
     List.map (fun l -> e :: l) subset in 
    List.flatten (List.map helper nums)