仅使用基本构造使用方案创建n大小的排列 [英] Creating an n-sized permutation with scheme using only basic constructs

问题描述

是否可以仅使用基本方案构造来生成列表的n个大小的排列?

Is it possible to generate n-sized permutations of a list using only the basic scheme constructs?

推荐答案

这是对 Rosetta ，但是，我更改了变量名以使其更易读，并在下面的代码中添加了解释.我确实检查过代码是否可以在DrRacket中使用，并且可以.

This is an explanation of the code found in Rosetta, although, I have changed the variable names to help make it more readable, and added my explanation of the code below. I did check to see if the code works in DrRacket, and it does.

在定义置换之前，需要两个助手功能，即 seq 和插入.

Before defining permute, two helper functions are required namely, seq and insert.

seq 构建一个包含数字序列的列表.例如(seq 0 3)->(0 1 2 3). 列表中的元素(数字)用于插入函数，将 carItem 插入到 cdr "列表.

seq builds a list containing a sequence of numbers. For example (seq 0 3) -> (0 1 2 3). The elements (numbers) in the list are used in the insert function to insert the carItem at various positions in the 'cdr' list.

(define (seq start end) 
  (if (= start end) 
      (list end)    ; if start and end are the same number, we are done
      (cons start (seq (+ start 1) end)) 
      )
  )

插入会生成一个列表，其中将 carItem 插入在 cdrList 的第n个位置.例如，(插入'(b c)0'a)->'(a b c)和(插入'(b c)2'a)->'(b c a).

insert generates a list with the carItem inserted in the "n"th position of the cdrList. For example, (insert '(b c) 0 'a) -> '(a b c) and (insert '(b c) 2 'a) -> '(b c a).

(define (insert cdrList n carItem)
  (if (= 0 n)
      (cons carItem cdrList) ; if n is 0, prepend carItem to cdrList
      (cons (car cdrList)  
            (insert (cdr cdrList) (- n 1) carItem))))

最后，对于主要功能置换，它以递归方式使用插入和 seq . 例如，当plist ='(b，c)时，λ等于:

Finally, as for the main function permute, it uses insert and seq in a recursive manner. For example, when plist = '(b,c) the lambda evals to the following:

; (map (lambda (n)
;    (insert '(b c) n 'a))
;    '(0 1 2)) -> output of seq function given n = 2, which is length of '(b c)
; '((a b c) (b a c) (b c a)) ---> will be the output

(define (permute mylist)
  (if (null? mylist)
      '(())
      (apply append (map (lambda (plist)
                           (map (lambda (n)
                                  (insert plist n (car mylist)))
                                (seq 0 (length plist))))
                         (permute (cdr mylist))))))

(permute '(a b c))

如果上述嵌套lambda 使您的头部旋转(对我而言确实如此)，请在下面找到恕我直言，这是更易于理解的定义"版本，这要感谢Matthias Felleisen:

If the above nested lambdas makes your head spin (it did for me), find below, IMHO, a more readable "define" version, thanks to Matthias Felleisen:

(define (permute mylist)
  (cond 
    [(null? mylist) '(())]
    [else 
      (define (genCombinationsFor plist)
      (define (combineAt n) (insert plist n (car mylist)))
        (map combineAt (seq 0 (length plist))))
        (apply append (map genCombinationsFor (permute (cdr mylist))))]))

这篇关于仅使用基本构造使用方案创建n大小的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！