所有可能的子列表方案
All possible sublists scheme
我想找到列表的所有可能的连续分区:
(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) '() '())
我们的想法是我们逐项遍历列表,在每一步我们都可以将其拆分或不拆分,然后我们分成两个新的迭代,一个有拆分,一个没有拆分。这会产生接近我想要但又不完全是我想要的结果。
目标是找到一种使用递归来描述问题的自然方式。
为了找到 (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 '())
必须 return 空列表 '()
.
唯一剩下的问题是 combine 的作用。
让我们检查一下案例
中输入和输出之间的关系
(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)))
必须return
( ((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))
现在我们已经完成了拼图的所有部分。我会留下最后的定义
给你的子列表。
既然你提到了 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
定义为带有 appendo
的 conde
和对 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)))
我从 here 复制了 appendo
。
miniKanren 中的解决方案顺序不遵循谓词定义中的目标顺序(就像在 Prolog 中那样),因为 miniKanren 交错了子目标产生的结果以实现它所谓的 "fair scheduling".
我想找到列表的所有可能的连续分区:
(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) '() '())
我们的想法是我们逐项遍历列表,在每一步我们都可以将其拆分或不拆分,然后我们分成两个新的迭代,一个有拆分,一个没有拆分。这会产生接近我想要但又不完全是我想要的结果。
目标是找到一种使用递归来描述问题的自然方式。
为了找到 (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 '())
必须 return 空列表 '()
.
唯一剩下的问题是 combine 的作用。 让我们检查一下案例
中输入和输出之间的关系(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)))
必须return
( ((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))
现在我们已经完成了拼图的所有部分。我会留下最后的定义 给你的子列表。
既然你提到了 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
定义为带有 appendo
的 conde
和对 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)))
我从 here 复制了 appendo
。
miniKanren 中的解决方案顺序不遵循谓词定义中的目标顺序(就像在 Prolog 中那样),因为 miniKanren 交错了子目标产生的结果以实现它所谓的 "fair scheduling".