計數可行的組合給出同時滿足類

Question

的時間表

場景：

• 一組學生（「001」，「002」 ...）都有一組類，他們需要在學校參加。
• 時間表是爲每個學期的每個時段發生的班級列表，分爲同時發生的班級集合
• 任務是分析給定時間表的「好」情況，哪裏好意味着每個學生都能參加他們需要的所有類的，在許多不同的排列儘可能

問題描述：

給定一個哈希：

hash = { 
    '001' => ['MX1','EF1','HG1','PN1','SP1','AU1'], 
    '002' => ['MP1','EF1','HG2','PN4','SC1','AU3'], 
    '003' => ['MG1','EF2','HP1','PP1','SC1','AU1'] 
    } 

和二維陣列：

schedule = [ 
['MX1','EF2','XE1','SP1','AU4'], 
['MX1','EF1','HP1','PP1','AU1'], 
['MP1','MG1','SP1','HG2','PN1','AU1','MX1','EG1','HG1'], 
['MG1','EF2','PN4','SC1','AU1','SP1'], 
['PP1','PN1','PN4','EF1','EF2'], 
['SC1','PP1','HP1','AU1'] 
] 

我想在多少不同的方式從hash值的元素可以與來自schedule陣列相匹配以發現，造成的結果散列：

{ 
'001' => 1, # just using example values, this is a count 
'002' => 0, # of the combinations of the array from hash 
'003' => 2 # that can be matched to each array in schedule 
} 

     # without replacement 

「匹配」意味着，給定一個哈希值數組： ['MX1','EF1','HG1','PN1','SP1','AU1'] 每個元素都可以在與schedule不同的數組中找到。爲hash['001']

一個匹配：

{ 
'MX1' => schedule[0], # given here in hash form only 
'EF1' => schedule[1], # for illustrative purposes, 
'HG1' => schedule[2], # I don't need to represent 
'PN1' => schedule[4], # each match 
'SP1' => schedule[3], 
'AU1' => schedule[5] 
} 

如果有學生0可能的匹配，我們知道，我們必須將一些類，更多的比賽，可能每一個學生，更好的安排。

Answer 1

假設一個學生必須參加以下類別：

classes = ['MX1','EF1','HG1','PN1','SP1','AU1'] 

首先，爲了提高效率，轉換schedule到的套陣列。

require 'set' 

sch_sets = schedule.map { |a| a.to_set } 
    #=> [#<Set: {"MX1", "EF2", "XE1", "SP1", "AU4"}>, 
    # #<Set: {"MX1", "EF1", "HP1", "PP1", "AU1"}>, 
    # #<Set: {"MP1", "MG1", "SP1", "HG2", "PN1", "AU1", "MX1", "EG1", "HG1"}>, 
    # #<Set: {"MG1", "EF2", "PN4", "SC1", "AU1", "SP1"}>, 
    # #<Set: {"PP1", "PN1", "PN4", "EF1", "EF2"}>, 
    # #<Set: {"SC1", "PP1", "HP1", "AU1"}>] 

然後爲每個學生重複以下步驟。

classes.permutation(classes.size). 
     count { |p| sch_sets.zip(p).all? { |s,cl| s.include?(cl) } } 
    #=> 1 

對於那些好奇，在這種情況下，工作的排列，我們只需要改變count到select（或者，因爲在這裏只有一個，find）。

classes.permutation(classes.size). 
     select { |p| sch_sets.zip(p).all? { |s,cl| s.include?(cl) } } 
    #=> [["MX1", "EF1", "HG1", "SP1", "PN1", "AU1"]] 

請參閱下列實例方法的文檔。

• permutation和size爲類Array
• include?爲類Set
• count，zip，all?和select所包含的模塊Enumerable

實例方法to_set加到Enumerable當時需要（請參閱Set文檔的第二段）。