在方案中创建列表的排列 [英] creating permutation of a list in scheme

问题描述

我正在尝试编写一个仅使用基本列表结构(cons，空，第一，其余)来创建列表排列的函数.我正在考虑在列表的其余部分的递归调用中的任何地方插入列表的第一个值，但是我的基本情况遇到了一些麻烦.

I'm trying to write a function that creates the permutation of a list using just the basic list constructs (cons, empty, first, rest). I'm thinking of inserting the first value of the list everywhere in the recursive call of the rest of the list, but I'm having some trouble with my base case.

我的代码:

(define (permutation lst) 
   (cond
      [(empty? lst) (cons empty empty)]
      [else (insert_everywhere (first lst) (permutation (rest lst)))]))

(排列(列表1 2))给我(列表1 2空2 1空).我可以做些什么来在不同组合之间创建一个占位符(例如空)，但是程序没有将占位符解释为列表中的元素吗?

(permutation (list 1 2)) gives me (list 1 2 empty 2 1 empty). Is there anything I can do to create a placeholder (such as empty) between the different combinations but not have the program interpret the placeholder as an element in the list?

我的基本情况正确吗?

Is my base case right?

谢谢！

推荐答案

排列算法并不像您想象的那么简单，仅根据您提到的基本列表操作编写代码就非常棘手，除非您编写自己的帮助程序以反映诸如map，append之类的内置功能(但是为什么不首先使用内置功能?).

The permutation algorithm isn't as simple as you imagine, it'll be really, really tricky to write just in terms of the basic list operations you mention, unless you write your own helpers that mirror built-in functions such as map, append (but why not use the built-ins in the first place?).

要了解需要做什么，请查看Rosetta代码页面描述几种可能的解决方案，请在方案"或球拍"链接下查看.这是链接页面中显示的从头实现的一种改编-除了问题中提到的基本列表操作之外，它还使用append和map:

To get an idea of what needs to be done, take a look at the Rosetta Code page describing several possible solutions, look under the Scheme or Racket links. Here's an adaptation of one of the implementations from scratch shown in the linked page - and besides the basic list operations mentioned in the question, it uses append and 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))

这篇关于在方案中创建列表的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！