Page 1 of 1

Need help in displaying using lists

Posted: Wed Aug 04, 2010 6:38 am
by kelvin
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. =)

Re: Need help in displaying using lists

Posted: Wed Aug 04, 2010 7:40 am
by ramarren
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.

Re: Need help in displaying using lists

Posted: Wed Aug 04, 2010 8:53 am
by nuntius
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.

Re: Need help in displaying using lists

Posted: Fri Aug 06, 2010 10:42 am
by kelvin
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.

Re: Need help in displaying using lists

Posted: Wed Aug 11, 2010 1:17 pm
by Warren Wilkinson
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.

Re: Need help in displaying using lists

Posted: Tue Aug 17, 2010 4:47 am
by kelvin
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)

Re: Need help in displaying using lists

Posted: Tue Aug 17, 2010 4:50 am
by kelvin
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.