Нахождение подмножеств произвольной длины элементов списка

Question

Disclaimer: Я почти уверен, что мне удалось испортить что-то действительно простое, возможно, потому что я выискивал это между "настоящая работа" в ожидании медленной сборки C ++, так что моя голова не в нужном месте.

При взгляде на Какой самый эффективный способ создания всех возможных комбинаций зелий Skyrim (PC Game)? У меня было наивное представление, что это будет действительно очень простой рекурсивный фильтр в Лиспе для генерации всех комбинаций размера "n «. Ответ, данный там, на R, элегантен и хорошо показывает язык, но этот метод combn(list,n) привлек мое внимание. (http://stat.ethz.ch/R-manual/R-patched/library/utils/html/combn.html)

(defun combn (list n)
  (cond ((= n 0) nil)
        ((null list) nil)
        ((= n 1) (mapcar #'list list))
        (t (mapcar #'(lambda (subset) (cons (car list) subset))
                   (combn (cdr list) (1- n))))))

(combn '(1 2 3 4 5 6 7 8 9) 3)

((1 2 3) (1 2 4) (1 2 5) (1 2 6) (1 2 7) (1 2 8) (1 2 9))

Кроме того, это просто возвращает первый набор комбинаций ... Я не могу точно понять, что не так, точно. Кажется, что дело (= n 1) работает правильно, но дело t должно делать что-то по-другому, такое как удаление (1 2) из списка и повторение?

Итак, моя попытка это исправить стала еще более неприятной:

 (defun combn (list n)
  (cond ((= n 0) nil) ((= n 1) (mapcar #'list list))
        ((null list) nil)
        (t (cons (mapcar #'(lambda (subset) (cons (car list) subset))
                         (combn (cdr list) (1- n)))
                 (combn (cdr list) n)))))

что неправильно в точке (t cons( ... я думаю. Но если cons неправильный ответ, я не уверен, что правильно ...? (Сокращено до использования 2 для демонстрации результата…)

(combn '(1 2 3 4 5 6 7 8 9) 2)
(((1 2) (1 3) (1 4) (1 5) (1 6) (1 7) (1 8) (1 9))
 ((2 3) (2 4) (2 5) (2 6) (2 7) (2 8) (2 9))
 ((3 4) (3 5) (3 6) (3 7) (3 8) (3 9))
 ((4 5) (4 6) (4 7) (4 8) (4 9))
 ((5 6) (5 7) (5 8) (5 9))
 ((6 7) (6 8) (6 9))
 ((7 8) (7 9))
 ((8 9))
  NIL)

… что кажется правильным, за исключением постороннего вложения и бонуса NIL в конце. (Я ожидал, что ((null list) nil) отфильтрует это?)

Что я сделал не так? : - (

(И, кроме того, есть ли стандартная процедура для более эффективной работы?)

Answer 1

Решение с использованием Common Lisp.

Обратите внимание, что в этой версии преднамеренно используется assert, чтобы выдавать постоянную ошибку, если переданный список не делится равномерно на указанное число, но было бы достаточно просто поместить в него любые «оставшиеся» элементы. более короткий список в конце, или используйте error, чтобы полностью освободить его под залог без возможности интерактивного исправления.

Основано на схеме srfi-1, настроено мной на CL и значительно улучшено Райнером Йосвигом

(defun split-by (list n &aux length)

"splits a list into multiple lists of length n.

Parameters:
  * list - the list to be split
  * n    - the size of the lists it should be broken into.

Returns:
 A list of smaller lists of the specified length (or signals an error).

Examples:
  (split-by '(1 2 3 4) 2)   ; => ((1 2) (3 4))
  (split-by '(1 2 3)   2)   ; => not evenly divisible"

  (assert (zerop (mod (setf length (length list)) n))
      (list)
    "list is not evenly divisible by ~A: ~A" n list)

  (if (plusp length)
      (cons (subseq list 0 n)
            (split-by (subseq list n) n))
    '()))

Answer 2

Да, cons это не то, вам нужно добавить. И это также то, что дает вам NIL в конце. Я не могу написать Лисп, поэтому я дам тебе Хаскель:

comb :: Int -> [a] -> [[a]]
comb 0 _ = [[]]
comb k (x:xs) = [x:ys | ys <- comb (k-1) xs] ++ comb k xs
comb _ _ = []

Это коротко и мило, но неэффективно (и не проверяет на отрицательность k). Он часто пытается выбрать больше элементов, чем в списке в течение длительного времени. Чтобы предотвратить это, нужно было бы отслеживать, сколько элементов еще доступно.

comb :: Int -> [a] -> [[a]]
comb 0 _ = [[]]
comb k xs
  | k < 0     = []
  | k > len   = []
  | k == len  = [xs]
  | otherwise = go len k xs
    where
      len = length xs
      go l j ys
        | j == 1 = map (:[]) ys
        | l == j = [ys]
        | otherwise = case ys of
                        (z:zs) -> [z:ws | ws <- go (l-1) (j-1) zs] ++ go (l-1) j zs

Гадкий, но эффективный.