如何在Scheme中查找列表的分区 [英] How to find partitions of a list in Scheme
问题描述
说在Scheme中有任何给定的列表.此列表为‘(2 3 4)
Say there is any given list in Scheme. This list is ‘(2 3 4)
我想找到此列表的所有可能分区.这意味着分区将列表分为两个子集，这样列表中的每个元素都必须位于一个或另一个子集中，但不能同时位于两个子集中，并且不能将任何元素都排除在拆分之外.
I want to find all possible partitions of this list. This means a partition where a list is separated into two subsets such that every element of the list must be in one or the other subsets but not both, and no element can be left out of a split.
因此，给定列表‘(2 3 4)，我想找到所有可能的分区.这些分区如下:{2，3}和{4}，{2，4}和{3}，最后可能的分区是{3，4}和{2}.
So, given the list ‘(2 3 4), I want to find all such possible partitions. These partitions would be the following: {2, 3} and {4}, {2, 4} and {3}, and the final possible partition being {3, 4} and {2}.
我希望能够在Scheme中递归地找到给定列表的所有分区，但是我不知道如何执行此操作.如果有人可以为我提供代码或伪代码，它将对我有帮助！
我确实相信我必须对递归函数使用lambda.
I want to be able to recursively find all partitions given a list in Scheme, but I have no ideas on how to do so. Code or psuedocode will help me if anyone can provide it for me!
I do believe I will have to use lambda for my recursive function.
推荐答案
要对列表进行分区是直接的递归非确定性编程.
To partition a list is straightforward recursive non-deterministic programming.
给出一个元素，我们将其放入一个袋子或另一个袋子中.
Given an element, we put it either into one bag, or the other.
第一个元素将放在第一个包中，而不会失去一般性.
The very first element will go into the first bag, without loss of generality.
最后一个元素必须只能放入一个空袋中，如果当时存在的话.由于我们首先将第一个元素放入第一个包中，因此只能是第二个:
The very last element must go into an empty bag only, if such is present at that time. Since we start by putting the first element into the first bag, it can only be the second:
(define (two-parts xs)
(if (or (null? xs) (null? (cdr xs)))
(list xs '())
(let go ((acc (list (list (car xs)) '())) ; the two bags
(xs (cdr xs)) ; the rest of list
(i (- (length xs) 1)) ; and its length
(z '()))
(if (= i 1) ; the last element in the list is reached:
(if (null? (cadr acc)) ; the 2nd bag is empty:
(cons (list (car acc) (list (car xs))) ; add only to the empty 2nd
z) ; otherwise,
(cons (list (cons (car xs) (car acc)) (cadr acc)) ; two solutions,
(cons (list (car acc) (cons (car xs) (cadr acc))) ; adding to
z))) ; either of the two bags;
(go (list (cons (car xs) (car acc)) (cadr acc)) ; all solutions after
(cdr xs) ; adding to the 1st bag
(- i 1) ; and then,
(go (list (car acc) (cons (car xs) (cadr acc))) ; all solutions
(cdr xs) ; after adding
(- i 1) ; to the 2nd instead
z))))))
就是这样！
在撰写本文时，我遵循了这个我之前的相关答案，对我有所帮助.
In writing this I was helped by following this earlier related answer of mine.
测试:
(two-parts (list 1 2 3))
; => '(((2 1) (3)) ((3 1) (2)) ((1) (3 2)))
(two-parts (list 1 2 3 4))
; => '(((3 2 1) (4))
; ((4 2 1) (3))
; ((2 1) (4 3))
; ((4 3 1) (2))
; ((3 1) (4 2))
; ((4 1) (3 2))
; ((1) (4 3 2)))
可以在返回或路线之前颠倒零件；我想使代码简洁明了，没有多余的细节.
It is possible to reverse the parts before returning, or course; I wanted to keep the code short and clean, without the extraneous details.
edit:代码使用Richard Bird的技术，将(append (g A) (g B))替换为(g' A (g' B z))，其中(append (g A) y) = (g' A y)和z的初始值是一个空列表.
edit: The code makes use of a technique by Richard Bird, of replacing (append (g A) (g B)) with (g' A (g' B z)) where (append (g A) y) = (g' A y) and the initial value for z is an empty list.
另一种可能性是将对go的嵌套调用放在lambda之后(确实怀疑OP)并在对go的外部调用完成其工作时激活，从而使整个函数尾部递归，实质上 CPS样式.
Another possibility is for the nested call to go to be put behind lambda (as the OP indeed suspected) and activated when the outer call to go finishes its job, making the whole function tail recursive, essentially in CPS style.
这篇关于如何在Scheme中查找列表的分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
