分區特定集合

Question

我想使用Clojure的劃分特定集合：

例如： 有一個向量[1 2 3 4 5]。這裏還有一張地圖，如{2 1, 3 1}，這意味着生成1個包含2個元素的集合，以及1個包含3個元素的集合。

(some_function {2 1, 3 1} [1 2 3 4 5]) 
;; I only want to these: 
(([1 2 3] [4 5]) 
([1 2 4] [3 5]) 
([1 2 5] [3 4]) 
([1 2] [3 4 5]) 
([1 3 4] [2 5]) 
([1 3 5] [2 4]) 
([1 3] [2 4 5]) 
([1 4 5] [2 3]) 
([1 4] [2 3 5]) 
([1 5] [2 3 4])) 

以前，我想到要用(combo/partitions [1 1 2])生成所有的情況下，再根據條件篩選，但它是如此低效的，當你有一個像[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17]大載體和地圖像{5 1, 6 2}(generate 1 set that contains 5 elements, and 2 sets that contain 6 elements)。我只是想在第一時間生成我需要的東西，我該如何完成這項工作？

Answer 1

在給出的具體示例中，有5,717,712個分區滿足這些約束條件，並且沒有約束條件的可能性更大。所以組合並不是很低效，我想你只是低估了有多少可能性。

組合函數是實現更直接組合的更好工具，您正在尋找。

在你的榜樣，

(def specific-partitions 
    (let [initial-list [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17]] 
    (for [c1 (combinations initial-list 5) 
      :let [remainder1 (remove (set c1) initial-list)] 
      c2 (combinations remainder1 6) 
      :let [remainder2 (remove (set c2) remainder1)]] 
     [c1 c2 remainder2]))) 

=>(take 10 specific-partitions) 

([(1 2 3 4 5) (6 7 8 9 10 11) (12 13 14 15 16 17)] 
[(1 2 3 4 5) (6 7 8 9 10 12) (11 13 14 15 16 17)] 
[(1 2 3 4 5) (6 7 8 9 10 13) (11 12 14 15 16 17)] 
[(1 2 3 4 5) (6 7 8 9 10 14) (11 12 13 15 16 17)] 
[(1 2 3 4 5) (6 7 8 9 10 15) (11 12 13 14 16 17)] 
[(1 2 3 4 5) (6 7 8 9 10 16) (11 12 13 14 15 17)] 
[(1 2 3 4 5) (6 7 8 9 10 17) (11 12 13 14 15 16)] 
[(1 2 3 4 5) (6 7 8 9 11 12) (10 13 14 15 16 17)] 
[(1 2 3 4 5) (6 7 8 9 11 13) (10 12 14 15 16 17)] 
[(1 2 3 4 5) (6 7 8 9 11 14) (10 12 13 15 16 17)]) 

它仍然是一個相當大的分區數，但至少你現在直接生成它們。

從這個例子中，你可以將這種技術推廣到一個函數，該函數使用描述分區結構的任意映射，就像你在問題中描述的那樣。

如果您的初始設置有重複的元素，我在這裏編寫的特定代碼將無法正常工作;這需要稍微不同的移除方法。