Схема всех возможных подсписков - PullRequest
Новая
       33

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

0 голосов
/ 24 июня 2018

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

(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)))

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

Edit:

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

(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) '() '())

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

Ответы [ 2 ]

0 голосов
/ 25 июня 2018

Поскольку вы упомянули 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 чередует результаты, полученные подцелями, для достижения того, что он называет «справедливым».планирование».

0 голосов
/ 24 июня 2018

Цель состоит в том, чтобы найти естественный способ описания проблемы с помощью рекурсии. Чтобы найти подсписки (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))

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

...