1 Replies - 4072 Views - Last Post: 17 February 2012 - 06:09 AM

#1 eric.mercer  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 14-February 12

Scheme: Permutations of a list

Posted 16 February 2012 - 08:00 PM

So I am trying to write a Scheme function that takes a list and returns a list of lists, each is a different permutation of the argument.

I know how to do it by using a function that removes an element and then recursively use that function to generate all permutations. I now have a problem where I want to use the following function:

(define (insert-everywhere item lst)
  (define (helper item L1 L2)
    (if (null? L2) (cons (append L1 (cons item '())) '())
        (cons (append L1 (cons item L2)) 
              (helper item (append L1 (cons (car L2) '())) (cdr L2)))))
  (helper item '() lst))


This function will insert the item into every possible location of the list, like the following:
(insert-everywhere 1 '(a B)) will get: '((1 a B) (a 1 B) (a b 1))

How would I use this function to get all permutations of a list?

View Posteric.mercer, on 16 February 2012 - 07:58 PM, said:

So I am trying to write a Scheme function that takes a list and returns a list of lists, each is a different permutation of the argument.

I know how to do it by using a function that removes an element and then recursively use that function to generate all permutations. I now have a problem where I want to use the following function:

(define (insert-everywhere item lst)
  (define (helper item L1 L2)
    (if (null? L2) (cons (append L1 (cons item '())) '())
        (cons (append L1 (cons item L2)) 
              (helper item (append L1 (cons (car L2) '())) (cdr L2)))))
  (helper item '() lst))


This function will insert the item into every possible location of the list, like the following:
(insert-everywhere 1 '(2 3)) will get: '((1 2 3) (2 1 3) (2 3 1))

How would I use this function to get all permutations of a list?


Is This A Good Question/Topic? 0
  • +

Replies To: Scheme: Permutations of a list

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2117
  • View blog
  • Posts: 3,242
  • Joined: 21-June 11

Re: Scheme: Permutations of a list

Posted 17 February 2012 - 06:09 AM

To get all permutations you can insert the head of the list everywhere into each permutation of the tail.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1