Need help in displaying using lists

Discussion of Scheme and Racket

Need help in displaying using lists

Postby kelvin » Wed Aug 04, 2010 6:38 am

Hi mates,

I'm trying to produce and algorithm that counts (base 10) and display in such a manner:
Numbers 0 to 9 will produce this output: ((0)(1)(2)(3).....(8)(9))
Numbers 10 to 20 will produce this ouput: ((00)(01)(02)...(09)(10)(11)...(20))

The thing is each time the number gets larger, I would like to cons it in a nice way.
if I call (method 1) then produce ((0)(1)....)
if I call (method 2) then produce ((00)(01)(02).....)
if I call (method 3) then produce ((000)(001)(002)....)

this is my current code which produce terrible output:
(define str "")
(define (method n str)
(if (= n 0)
(display str)
(let loop ((i 0))
(if (< i 52)
(begin
(list (method (- n 1)(list str i)))
(loop (+ i 1)))))))

I have been racking my brains on this problem for a week now. Hope u guys will have a solution for me. =)
kelvin
 
Posts: 4
Joined: Tue Aug 03, 2010 9:13 am

Re: Need help in displaying using lists

Postby Ramarren » Wed Aug 04, 2010 7:40 am

I don't really know Scheme, even from what I understand in your code sample I have no idea what it is you are trying to achieve. Could you perhaps explain your algorithm in prose, but algorithmically, that is, not by example. Knowing what it is exactly that you are trying to implement usually makes it easier to know how to implement it.
Ramarren
 
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

Re: Need help in displaying using lists

Postby nuntius » Wed Aug 04, 2010 8:53 am

I think you want to approach this differently. Factor the code into two functions, and merge them later if greater efficiency is required.

First write a function that prints a number, padded with leading zeros. Something like (padded-string x width). An easy implementation is to convert x to a string, compare the string's length to the desired width, and add leading "0"s as required.

Then write a function that makes a list of calls to padded-string. Print the biggest number in the range, find its width, and use that for padding all the other numbers.

Efficiency hacks:
- cache a long string of 0s, and index into it as required
- merge the two functions, so the main loop knows the string length before printing
... but don't do any of this until you have a working program! I have had too many cool programs die unfinished because I got distracted by some optimization like SSE2 or partial evaluation or ...

Also:
- Version control is your friend! Commit whenever you make progress. A good tool (e.g. git) lets you rewrite history to be beautiful as needed.
- It doesn't hurt to have parallel source files -- one set doing things the easy way, and the other with a bunch of optimizations.
- Always drive optimizations by benchmarks. Have a test suite showing what you may gain before ruining your code for nothing.

Ok. I went way off-topic there. Enjoy your day.
User avatar
nuntius
 
Posts: 497
Joined: Sat Aug 09, 2008 10:44 am
Location: Burlington, MA

Re: Need help in displaying using lists

Postby kelvin » Fri Aug 06, 2010 10:42 am

Hi thanks for the reply. But actually i can't use the function in mention.
Hmmm, what i would like to do is to produce a permutation. Let's take alphabets for a-z for example.
When I call my function (permutate n):
(permutate 1) output: (("a")("b")("c")....("x")("y")("z"))
(permutate 2) output: (("a" "a")("a" "b")("a" "c")....("b" "a")("b" "b")...("c" "a")("c" "b")("c" "c")("c" "d")....("z" "z")
(permutate 3) output: (("a" "a" "a")("a" "a" "b")...........("z" "z" "z"))

To permutate and give every possible outcome. So one of the condition is the count is up to base 26, a-z.
I have just no idea how to use cons and cons to produce a nice result.
kelvin
 
Posts: 4
Joined: Tue Aug 03, 2010 9:13 am

Re: Need help in displaying using lists

Postby Warren Wilkinson » Wed Aug 11, 2010 1:17 pm

Looking at your latest post, that looks like cross product to me... I'm not super familiar with scheme, but this might do what you need:

Code: Select all
(defun ensure-list (a) (if (listp a) a (list a)))
(defun cross (a b) (mapcan #'(lambda (outer) (mapcar #'(lambda (inner) (list* outer (ensure-list inner))) b)) a))

;; (cross '(a b c) '(1 2 3))  ---> ((A 1) (A 2) (A 3) (B 1) (B 2) (B 3) (C 1) (C 2) (C 3))


Then I wrote permutate to recursively apply cross.

Code: Select all
(defun permutate (list n)
  (if (zerop n)
      list
      (let ((next (permutate list (- n 1))))
   (cross list next))))

;; (permutate '(a b c) 2)
;;((A A A) (A A B) (A A C) (A B A) (A B B) (A B C) (A C A) (A C B) (A C C)
;; (B A A) (B A B) (B A C) (B B A) (B B B) (B B C) (B C A) (B C B) (B C C)
;; (C A A) (C A B) (C A C) (C B A) (C B B) (C B C) (C C A) (C C B) (C C C))


Of course, this is really common lisp code -- but I think porting it to scheme should be straight forward.
Need an online wiki database? My Lisp startup http://www.formlis.com combines a wiki with forms and reports.
User avatar
Warren Wilkinson
 
Posts: 116
Joined: Tue Aug 10, 2010 11:24 pm
Location: Calgary, Alberta

Re: Need help in displaying using lists

Postby kelvin » Tue Aug 17, 2010 4:47 am

Thanks for all the help. I have worked out a solution on my own, and it is some what similar. Here's my solution to share:
(define (permutate lst len)
(cond ((= 0 len) '(()))
(else (append-map
(lambda (x)
(map (lambda (y) (reverse (cons y x ))) lst))
(permutate lst (- len 1))))))

And similarly i do a mapping over it, e.g. (permutate '(1 2 3) a)
kelvin
 
Posts: 4
Joined: Tue Aug 03, 2010 9:13 am

Re: Need help in displaying using lists

Postby kelvin » Tue Aug 17, 2010 4:50 am

Ops sorry the calling should be (permutate '(1 2 3) 2), with the 2nd parameter being a number, where it will determine the number of permutates.
kelvin
 
Posts: 4
Joined: Tue Aug 03, 2010 9:13 am


Return to Scheme

Who is online

Users browsing this forum: sylwester and 1 guest