Распределение k-комбинаций - PullRequest
Новая
       23

Распределение k-комбинаций

0 голосов
/ 08 июля 2019

Я генерирую все возможные подмножества / 3-комбинации из списка в Clojure (не учитывая порядок элементов комбинаций - т. Е. Подмножество ABC совпадает с CBA и т. Д.).

Для списка (ABCDEFG) результат моих комбинаций в сумме составляет 35, как показано ниже: 

("A" "B" "C")
("A" "B" "D")
("A" "B" "E")
("A" "B" "F")
("A" "B" "G")
("A" "C" "D")
("A" "C" "E")
("A" "C" "F")
("A" "C" "G")
("A" "D" "E")
("A" "D" "F")
("A" "D" "G")
("A" "E" "F")
("A" "E" "G")
("A" "F" "G")
("B" "C" "D")
("B" "C" "E")
("B" "C" "F")
("B" "C" "G")
("B" "D" "E")
("B" "D" "F")
("B" "D" "G")
("B" "E" "F")
("B" "E" "G")
("B" "F" "G")
("C" "D" "E")
("C" "D" "F")
("C" "D" "G")
("C" "E" "F")
("C" "E" "G")
("C" "F" "G")
("D" "E" "F")
("D" "E" "G")
("D" "F" "G")
("E" "F" "G")

Это все хорошо, за исключением того, что мне нужно, чтобы пары комбинаций распределялись "равномерно", т.е. пара комбинаций, содержащая "A", должна быть толькоповторяется, когда все другие элементы в списке используются в комбинации, например, как показано ниже: 

("A" "B" "C")
("D" "E" "F")
("A" "B" "G")
("C" "D" "E")
("A" "F" "G")
... and onwards

Я, конечно, ожидаю, что это будет общая проблема, которая была решена много раз раньше, но ятрудно понять направление дальнейших исследований в этой области.Любые предложения по алгоритмам, чтобы изучить или основать дальнейшие исследования?

Я генерирую комбинации, как показано ниже. 

(defn k-combinations [n items]
  (concat (map
            #(cons (first items) %)                         
            (subsets (dec n) (rest items)))
          (subsets n (rest items))))

(defn subsets [n items]
  (cond
    (= n 0) '(())                                           
    (empty? items) '()                                      
    :else (k-combinations n items)))

(subsets 3 '("A" "B" "C" "D" "E" "F" "G"))
...