在方案中创建列表的排列
在方案中创建列表的排列
提问于 2013-12-02 09:44:23
我正在尝试编写一个仅使用基本列表结构(cons、empty、first、rest)创建列表排列的函数。我正在考虑将列表的第一个值插入到列表其余部分的递归调用中的任何地方，但我在基本情况下遇到了一些问题。
我的代码：
(define (permutation lst)
(cond
[(empty? lst) (cons empty empty)]
[else (insert_everywhere (first lst) (permutation (rest lst)))]))(排列(列表1 2))给我(列表1 2空2 1空)。有没有什么我可以做的，在不同的组合之间创建一个占位符(比如空)，而不是让程序将占位符解释为列表中的一个元素？
我的基本情况正确吗？
谢谢!
回答 3
Stack Overflow用户
发布于 2013-12-02 11:28:48
置换算法并不像你想象的那么简单，仅仅根据你提到的基本列表操作来编写它将非常非常棘手，除非你编写自己的辅助函数来镜像内置函数，如map、append (但为什么不首先使用内置函数呢？)
要了解需要做什么，请查看Rosetta Code page，其中描述了几种可能的解决方案，请查看方案或球拍链接。以下是链接页面中显示的从头开始的实现之一的改编-除了问题中提到的基本列表操作之外，它还使用了append和map
(define (permutations s)
(cond [(empty? s) empty]
[(empty? (rest s)) (list s)]
[else
(let splice [(l '()) (m (first s)) (r (rest s))]
(append
(map (lambda (x) (cons m x))
(permutations (append l r)))
(if (empty? r)
empty
(splice (cons m l) (car r) (cdr r)))))]))看看它是如何工作的：
(permutations '(1 2 3))
=> '((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 2 1) (3 1 2))Stack Overflow用户
发布于 2016-10-24 10:36:14
我知道这是一个古老的帖子，但遵循基于随机数检查的相对简单和容易理解的解决方案可能会很有趣。它使用排列阶乘公式来确定是否收集了所有排列。
(define (f n k) ; lists will be from 0..(n-1)
(define pl '()) ; all permutations list;
(let loop ((ol '())) ; one permutation list;
(define a (random n)) ; 0 to n-1
(if (member a ol) (loop ol)
(begin (set! ol (cons a ol))
(if (< (length ol) k) (loop ol)
(if (member ol pl) (loop '())
(begin (set! pl (cons ol pl))
(if(< (length pl)
(/(factorial n)
(factorial (- n k))))
(loop '())
pl ))))))))(上面的代码是用Racket- a方案派生的)
测试：
(f 3 2)
(f 3 3)
(f 4 2)输出：
'((2 1) (1 0) (0 1) (0 2) (1 2) (2 0))
'((2 1 0) (1 0 2) (0 1 2) (1 2 0) (0 2 1) (2 0 1))
'((2 1) (3 0) (1 0) (1 3) (3 2) (2 3) (0 3) (0 1) (0 2) (2 0) (1 2) (3 1))Stack Overflow用户
发布于 2020-05-01 08:22:37
在您的基本情况下，尝试使用map和lambda是正确的
#lang scheme
(define (permutations items)
(if (null? items) '(())
(apply append
(map (lambda (element)
(map (lambda (permutation)
(cons element permutation))
(permutations (remove element items))))
items))))页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20319593
复制相关文章
相似问题
腾讯云开发者
