Все возможные схемы подсписков

Question

Я хочу найти все возможные последовательные разделы списков:

(a b c d) => (((a) (b c d)) ((a b) (c d)) ((a b c) (d)) ((a) (b c) (d)) ((a b c d)) ((a) (b) (c) (d)))

Какой самый простой способ это сделать? в идеале без использования счетчиков.

Редактировать:

Вот пример того, что я пытался, но это не совсем работает (предполагается, что ответы даются наоборот, но это было бы нормально):

(define split-list-help
  (lambda (l h a)
    (begin
      (display a)
      (if
       (null? (cdr l))
       (list (cons (cons (car l) a) h))
       (let
       [(a-nosplit (cons (car l) a))
        (h-split (if (null? a)
             (cons (list (car l)) h)
             (cons (list (car l)) (cons a h))))]
     (append  (split-list-help (cdr l) h-split '())
          (split-list-help (cdr l) h a-nosplit)))))))

(split-list-help '(a b c) '() '())

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

Answer 1

Цель состоит в том, чтобы найти естественный способ описания проблемы с помощью рекурсии. Для того, чтобы найти списки (a b c d) мы можем сосредоточиться на элементе a, Существует четыре разных последовательных списка, содержащих a:

(a)  (a b)  (a b c)  (a b c d)

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

combining (a)       with (sublists '(b c d))
combining (a b)     with (sublists   '(c d))
combining (a b c)   with (sublists     '(d))
combining (a b c d) with (sublists     ' ())

То есть имеем:

(sublists '(a b c d)) = (append (combine '(a)       (sublists '(b c d)))
                                (combine '(a b)     (sublists   '(c d)))
                                (combine '(a b c)   (sublists    '(d)))
                                (combine '(a b c d) (sublists     '())))

Отметим, что мы описали подсписки списка из четырех элементов, используя рекурсивный вызов подсписков только из трех элементов. Базовый случай (sublists '()) должен вернуть пустой список '(),

Единственный оставшийся вопрос - что делает комбайн? Давайте рассмотрим отношение между входом и выходом в случае

(combine '(a) (sublists '(b c d)))

Сублилисты '(b c d) являются:

( ((b) (c) (d))
  ((b) (c d)  )
  ((b c) (d)  )
  ((b c d)    ) )

Так (combine '(a) (sublists '(b c d))) должен вернуться

( ((a) (b) (c) (d))
  ((a) (b) (c d)  )
  ((a) (b c) (d)  )
  ((a) (b c d)    ) )

Операция, которая предопределяет элемент (список '(a)) перед списком есть минусы, поэтому мы можем использовать map а также cons на концерте:

(define (combine x xss)
  (map (lambda (xs) (cons x xs)) ; function that prepends x to a list xs
       xss))

Теперь у нас есть все кусочки головоломки. Я оставлю вам окончательное определение подсписков.

Answer 2

Поскольку вы упомянули miniKanren, вот решение Prolog для этой проблемы:

splits(L, LS):-                % conde ...
  (   L  = []                  % L is empty list:
  ->  LS = []
  ;                            % OR
      A = [_ | _],             % A is non-empty,
      append(A, B, L),         % for each A, B such that A + B = L,
      splits(   B, BS),        %   for every splits BS of B,   
      LS = [ A |   BS]         %     prepend A to BS to get the splits of L
  ).

%%% in SWI Prolog:
?- splits([1,2,3,4], R).
R = [[1], [2], [3], [4]] ;
R = [[1], [2], [3, 4]] ;
R = [[1], [2, 3], [4]] ;
R = [[1], [2, 3, 4]] ;
R = [[1, 2], [3], [4]] ;
R = [[1, 2], [3, 4]] ;
R = [[1, 2, 3], [4]] ;
R = [[1, 2, 3, 4]] ;
false.

В переводе на miniKanren это будет определять splitso как conde с appendo и рекурсивный вызов splitso:

#lang racket
(require minikanren)

(define (splitso L LS)
  (conde
   [(== L '()) (== LS '())]
   [(fresh (A B BS _H _T)
           (== A `(,_H . ,_T))
           (appendo A B L)
           (== LS `(,A . ,BS))    
           (splitso   B   BS))]))    

;;;
> (run* (R) (splitso '(1 2 3 4) R))
'(((1 2 3 4))
  ((1) (2 3 4))
  ((1 2) (3 4))
  ((1) (2) (3 4))
  ((1 2 3) (4))
  ((1) (2 3) (4))
  ((1 2) (3) (4))
  ((1) (2) (3) (4)))

Я скопировал appendo отсюда

Порядок решений в miniKanren не соответствует порядку целей в определении предиката (как в Prolog), потому что miniKanren чередует результаты, полученные подцелями, для достижения того, что он называет "справедливым планированием".