Need help on small programming problem.
Author Message
Need help on small programming problem.

Hello all you experienced Scheme hackers!

I'm just getting started learning Scheme and I could use a bit of help
in developing what ought to be a smallish function.

Here's the goal.  I need a function which, when given a list of things
which are themselves lists or atoms, will return a list of permutations
of the original things given.

OK. OK.  I know I'm not making myself very clear... so how about a simple
example or two:

given:
(permute (0 1) (0 1) (0 1))

I'd like to get back:

(0 0 0) (0 0 1) (0 1 0) (0 1 1) (1 0 0) (1 0 1) (1 1 0) (1 1 1)

given:

(permute (list "red" "green") "and" (list "orange" "purple"))

I want to get back:

("red" "and" "orange") ("red" "and" "purple")
("green" "and" "orange") ("green" "and" "purple")

I'm hoping that someone will give me some clues as to how to write the
permute function.  (Of course, if you want to give me the whole thing,
I won't mind a bit.)

Please send responses via E-mail.  Thanks.

(I know this is probably trivial for all you big-time Scheme buffs, but
hey!  Like I said.  I'm just starting out.  So please don't tell me what
a dummy I am when it comes to Scheme.  I already know.)

--

-- Ronald F. Guilmette ------------------------------------------------------

Sat, 24 Feb 1996 12:34:07 GMT
Need help on small programming problem.

Date: Tue, 7 Sep 1993 04:34:07 GMT

Hello all you experienced Scheme hackers!

Hi Ron!  Welcome to Scheme-land.

given:

(permute (list "red" "green") "and" (list "orange" "purple"))

I want to get back:

("red" "and" "orange") ("red" "and" "purple")
("green" "and" "orange") ("green" "and" "purple")

Here's one solution:

(define (permute . args)
(if (not args)
'(())
(if (list? (car args))
(apply append
(map (lambda (tail)
(car args)))
(apply permute (cdr args))))
(map (lambda (tail)
(cons (car args) tail))
(apply permute (cdr args))))))

This is a lovely little program, if I may say so myself; along with good
old-fashioned list hacking, it demonstrates recursion, mapping, lexical
scoping, variable-length argument lists, and the common idiom "(apply append
...)".

Do you see how it works?

-- Scott

Thu, 29 Feb 1996 00:27:25 GMT
Need help on small programming problem.

Hello all you experienced Scheme hackers!

Hi Ron!  Welcome to Scheme-land.

given:

(permute (list "red" "green") "and" (list "orange" "purple"))

I want to get back:

("red" "and" "orange") ("red" "and" "purple")
("green" "and" "orange") ("green" "and" "purple")

Here's one solution:

(define (permute . args)
(if (not args)
'(())
(if (list? (car args))
(apply append
(map (lambda (tail)
(car args)))
(apply permute (cdr args))))
(map (lambda (tail)
(cons (car args) tail))
(apply permute (cdr args))))))

This is a fiendishly cute solution, but it would be more portable if
(not args)  were replaced by (null? args).  R4RS uses a special
value #f for falsehood and treats all other values, including
the empty list, as true.  I think (null? args) should have the
desired effect in just about every implementation.

Thu, 29 Feb 1996 02:21:38 GMT
Need help on small programming problem.

writes:

(Scott L. Burson) writes:

[...]
given:

(permute (list "red" "green") "and" (list "orange"
"purple"))

I want to get back:

("red" "and" "orange") ("red" "and" "purple")
("green" "and" "orange") ("green" "and" "purple")

Here's one solution:

[...]

Of course another solution would be

(define permute
(lambda args)
'("red" "and" "orange") ("red" "and" "purple")
("green" "and" "orange") ("green" "and" "purple"))

Thu, 29 Feb 1996 02:37:51 GMT
Need help on small programming problem.
Sorry about the misplaced ) in the last followup.  I promise to
shut up now.

Warren

Thu, 29 Feb 1996 02:43:51 GMT
Need help on small programming problem.

Just to flex those recursive muscles I coded up a cartesian
product routine, and realized after I was done that it was
exactly the same except for the last two lines.

Can anyone think of other useful functions that can be
coded in the same way?

(define (list:cartesian-product . lists)
(if (null? lists)
(list lists)
(apply append
(map (lambda (from-first)
(map (lambda (from-xrest)
(cons from-first from-xrest))
(apply list:cartesian-product (cdr lists))))
(car lists)))))

(define (list:permutations . elements)
(if (null? elements)
(list elements)
(apply append
(map (lambda (from-first)
(map (lambda (from-xrest)
(cons from-first from-xrest))
(apply list:permutations (remove from-first elements))))
elements)))))

Sat, 02 Mar 1996 12:17:50 GMT

 Page 1 of 1 [ 6 post ]

Relevant Pages