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 ------------------------------------------------------

------ uucp address: ...!uunet!netcom.com!rfg -------------------------------



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)
                      (map (lambda (head) (cons head 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)
                         (map (lambda (head) (cons head 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  
 
 [ 6 post ] 

 Relevant Pages 

1. Help! Need Eiffel small example programs

2. Help needed writing small program -- possible?

3. Small MODULA 2 program needed ...

4. Small Program needed !!

5. Need small Ada program

6. Interesting Programming Problem, Need Some Help

7. Interesting Programming Problem, Need Some Help

8. need help with fortan 77 programming problems

9. Need help with Python programming problem.

10. problem with my small program

11. two small problems in my program

12. cw 2.0003, filter box on report properties is too small, need help...mucho

 

 
Powered by phpBB® Forum Software