Hello, I am new to LISP and I am having a problem trying to program this
algorithm.
Let's say I have two lists:
list1: (A B C)
list2: (1 2 3)
What I need to perform is an exhaustive append that creates a result list
that looks like so:
(((A 1)(B 1)(C 1))
((A 1)(B 1)(C 2))
((A 1)(B 1)(C 3))
((A 1)(B 2)(C 1))
((A 1)(B 2)(C 2))
((A 1)(B 2)(C 3))
((A 1)(B 3)(C 1))
etc etc etc....
((A 3)(B 3)(C 3)))
In the end, it should have 3^3 = 27 sublists.
I have no idea how to do this in LISP. If anyone can help me out, this would
be greatly appreciated!
········@aol.com wrote:
> Hello, I am new to LISP and I am having a problem trying to program this
> algorithm.
>
> Let's say I have two lists:
>
> list1: (A B C)
> list2: (1 2 3)
>
> What I need to perform is an exhaustive append that creates a result list
> that looks like so:
>
> (((A 1)(B 1)(C 1))
> ((A 1)(B 1)(C 2))
> ((A 1)(B 1)(C 3))
> ((A 1)(B 2)(C 1))
> ((A 1)(B 2)(C 2))
> ((A 1)(B 2)(C 3))
> ((A 1)(B 3)(C 1))
>
> etc etc etc....
>
> ((A 3)(B 3)(C 3)))
>
> In the end, it should have 3^3 = 27 sublists.
>
> I have no idea how to do this in LISP. If anyone can help me out, this would
> be greatly appreciated!
>
>
>
What have you tried so far? What results did you get?
I take it you have some idea how to write simple programs in Lisp,
using DEFUN and so on.
Do you know how to do loops? Are you forced to use recursion on this
problem, or can you use Lisp constructs like DOLIST, MAPCAR or even
LOOP?
You might want to think about how you would do it with arrays in C (or
some other programming language that you already know) and then see
how that would translate into Lisp. It might at least get you off
the ground.
If you're forced to use recursion and simple list processing
operations like CAR and CDR this will be harder. You can iterate
through a list recursively in Lisp as follows:
(defun iterate-example (list)
(cond ((null list) nil)
(t (print (car list))
(iterate-example (cdr list)))))
(iterate-example '(a b c))
A
B
C
NIL
This is how you can use recursion to process a list one element at a
time.
If you could tell us a little more about your situation, we might be
able to "safely" say more.
--
Fred Gilham ······@csl.sri.com
What if thou make us able to make like thee ---
To light with moons, to clothe with greenery,
To hang gold sunsets o'er a rose and purple sea!
-- George MacDonald
On 28 Apr 2004 08:12:10 -0700, Fred Gilham
<······@snapdragon.csl.sri.com> wrote:
>
>I take it you have some idea how to write simple programs in Lisp,
>using DEFUN and so on.
>
>Do you know how to do loops? Are you forced to use recursion on this
>problem, or can you use Lisp constructs like DOLIST, MAPCAR or even
>LOOP?
>
>You might want to think about how you would do it with arrays in C (or
>some other programming language that you already know) and then see
>how that would translate into Lisp. It might at least get you off
>the ground.
>
>If you're forced to use recursion and simple list processing
>operations like CAR and CDR this will be harder. You can iterate
>through a list recursively in Lisp as follows:
>
>(defun iterate-example (list)
> (cond ((null list) nil)
> (t (print (car list))
> (iterate-example (cdr list)))))
>
>(iterate-example '(a b c))
>
>A
>B
>C
>NIL
>
>
>This is how you can use recursion to process a list one element at a
>time.
>
>If you could tell us a little more about your situation, we might be
>able to "safely" say more.
Yeah, there are no restrictions to what I can use since it's a small
part of a larger function that I am trying to get working. It's not a
homework assignment or anything.
I have posted my current code on a previous post, but it does not work
well at all :(
I've tried also to only use LOOPS but I haven't figured out an
algorithm that will handle this.
········@aol.com wrote:
>
>
> Yeah, there are no restrictions to what I can use since it's a small
> part of a larger function that I am trying to get working. It's not a
> homework assignment or anything.
>
> I have posted my current code on a previous post, but it does not work
> well at all :(
>
> I've tried also to only use LOOPS but I haven't figured out an
> algorithm that will handle this.
>
You claim this is not homework, so here's a piece of the solution. See
if you can finish the rest.
What we are generating here are called 'repeated permutations'. The
order of the sublists is significant, e.g., (1 1 2) is different from (1
2 1), thus they are permutations rather than combinations. Furthermore,
we are allowed to use each item more than once, i.e., each item may be
'repeated'. The general formula for the number of repeated permutations
RP, where r items are chosen out of n total items is:
n RP r = n^r
In the special case you illustrated, where r = n, we have n^n (3^3 in
your case).
Let's look at the pattern of such repeated permutations to come up with
a function definition. Suppose we have 3 elements (1 2 3). The set of
repeated permutations taking 0 elements is:
(())
If we take 1 element at a time:
((1) (2) (3))
2 at a time:
((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3))
And finally 3 at a time (this is enough for illustration):
((1 1 1) (1 1 2) (1 1 3) (1 2 1) (1 2 2) (1 2 3) (1 3 1) (1 3 2) (1 3 3)
(2 1 1) (2 1 2) (2 1 3) (2 2 1) (2 2 2) (2 2 3) (2 3 1) (2 3 2) (2 3 3)
(3 1 1) (3 1 2) (3 1 3) (3 2 1) (3 2 2) (3 2 3) (3 3 1) (3 3 2) (3 3 3))
The pattern that seems to be evident is this:
"Given the result for r-1 elements, take each sublist and add each of
the n elements to the front creating n times as many sublists."
In Lisp, this looks like:
(defun spread-layer (l1 l2)
(cond ((null l1) '())
(t (spread-elt (car l1) l2 (spread-layer (cdr l1) l2)))) )
(defun spread-elt (elt l result)
(cond ((null l) result)
(t (cons (cons elt (car l)) (spread-elt elt (cdr l) result)))) )
Here, SPREAD-LAYER takes each element of L1 (the original list (1 2 3))
and "spreads" it over the previous result, L2. For example to generate
the 2-element set from the 1-element set:
(spread-layer '(1 2 3) '((1) (2) (3))) =>
((1) (2) (3))
|
|
V
((1 1) (1 2) (1 3) (2 1) (2 2) ...)
Now all we need is a function to start the process:
(defun repeated-permutations (l r)
(cond ((zerop r)'(()))
(t (spread-layer l (repeated-permutations l (1- r)))) ))
This is surely not the most efficient implementation, but there is an
elegant simplicity to these 3 tiny functions.
David Sletten
Hello!
<········@aol.com> wrote:
>Hello, I am new to LISP and I am having a problem trying to program this
>algorithm.
It's most often called Lisp without shouting nowadays.
>Let's say I have two lists:
>list1: (A B C)
>list2: (1 2 3)
>What I need to perform is an exhaustive append that creates a result list
>that looks like so:
>(((A 1)(B 1)(C 1))
>((A 1)(B 1)(C 2))
>((A 1)(B 1)(C 3))
>((A 1)(B 2)(C 1))
>((A 1)(B 2)(C 2))
>((A 1)(B 2)(C 3))
>((A 1)(B 3)(C 1))
>etc etc etc....
>((A 3)(B 3)(C 3)))
>In the end, it should have 3^3 = 27 sublists.
>I have no idea how to do this in LISP. If anyone can help me out, this would
>be greatly appreciated!
This doesn't really seem like a Lisp (or LISP) specific problem, but
like a problem of algorithms. Or do you know how to do it in any other
programming language? If so, what algorithm steps are difficult for
you to express in Lisp?
For the algorithm:
Call the two lists list-1 and list-2. And the function should be
something like
(defun assignments (list-1 list-2)
...)
These are base cases:
- list-1 empty
What's the result? I'd say '(()) (one result, containing no "assignments"
at all)
- list-2 empty
This is simple: ()
- list-1 non-empty, first element is first-1, rest is rest-1
What about combining every assignment of first-1 to an element of list-2
with every result of a recursive call to (assignment rest-1 list-2)?
You could use mapcar and/or mapcan there, or loop with
collect/append/nconc clauses.
Write those three cases as alternatives in e.g. a cond expression.
I've just done that:
[10]> (assignments '(A b c) '(1 2 3))
(((A 1) (B 1) (C 1)) ((A 1) (B 1) (C 2)) ((A 1) (B 1) (C 3))
((A 1) (B 2) (C 1)) ((A 1) (B 2) (C 2)) ((A 1) (B 2) (C 3))
((A 1) (B 3) (C 1)) ((A 1) (B 3) (C 2)) ((A 1) (B 3) (C 3))
((A 2) (B 1) (C 1)) ((A 2) (B 1) (C 2)) ((A 2) (B 1) (C 3))
((A 2) (B 2) (C 1)) ((A 2) (B 2) (C 2)) ((A 2) (B 2) (C 3))
((A 2) (B 3) (C 1)) ((A 2) (B 3) (C 2)) ((A 2) (B 3) (C 3))
((A 3) (B 1) (C 1)) ((A 3) (B 1) (C 2)) ((A 3) (B 1) (C 3))
((A 3) (B 2) (C 1)) ((A 3) (B 2) (C 2)) ((A 3) (B 2) (C 3))
((A 3) (B 3) (C 1)) ((A 3) (B 3) (C 2)) ((A 3) (B 3) (C 3)))
Does that look like what you wanted?
Kind regards,
Hannah.
On Wed, 28 Apr 2004 10:34:29 +0000 (UTC), ······@schlund.de (Hannah
Schroeter) wrote:
Yes, this is exactly what I need!
This algorithm is a part of a larger function that I am trying to
write. Currently, I have the following code:
-------------------
(setq nouns '(A B C))
(setq domains '(1 2 3))
(defun subset-generator (nouns domains)
(setq t1 '(0))
(setq result nil)
; Creates a blank array
(loop as i from 2 to (list-length nouns)
do (setq t1 (append t1 '(0))))
(subset-generator-helper nouns domains result t1 0)
)
; Helps generate the subset
(defun subset-generator-helper (nouns domain res1 t2 p)
; Break condition
(if (eq (nth p t2) (list-length domain))
break)
(loop as i from 0 to (- (list-length nouns) 1)
do (print (setq res1 (append res1 (list (nth i nouns)))))
(print (setq res1 (append res1 (list (nth (nth i t2)
domain))))))
; Temp separator
(print ".")
(loop as j from 0 to (- (list-length nouns) 1)
do (+ (nth j t2) 1)
(subset-generator-helper nouns domain res1 t2 j)
(- (nth j t2) 1))
res1
)
---------------------------
Unfortunately, since I am pretty lost with LISP, it gives me an
infinite loop and also does not iterate through the domain: (1 2 3).
Am I going about it the right way or is there something stupid that I
have done? Thanks a lot!
>This doesn't really seem like a Lisp (or LISP) specific problem, but
>like a problem of algorithms. Or do you know how to do it in any other
>programming language? If so, what algorithm steps are difficult for
>you to express in Lisp?
>
>For the algorithm:
>
>Call the two lists list-1 and list-2. And the function should be
>something like
>
>(defun assignments (list-1 list-2)
> ...)
>
>These are base cases:
>- list-1 empty
> What's the result? I'd say '(()) (one result, containing no "assignments"
> at all)
>- list-2 empty
> This is simple: ()
>- list-1 non-empty, first element is first-1, rest is rest-1
> What about combining every assignment of first-1 to an element of list-2
> with every result of a recursive call to (assignment rest-1 list-2)?
> You could use mapcar and/or mapcan there, or loop with
> collect/append/nconc clauses.
>
>Write those three cases as alternatives in e.g. a cond expression.
>
>I've just done that:
>
>[10]> (assignments '(A b c) '(1 2 3))
>(((A 1) (B 1) (C 1)) ((A 1) (B 1) (C 2)) ((A 1) (B 1) (C 3))
> ((A 1) (B 2) (C 1)) ((A 1) (B 2) (C 2)) ((A 1) (B 2) (C 3))
> ((A 1) (B 3) (C 1)) ((A 1) (B 3) (C 2)) ((A 1) (B 3) (C 3))
> ((A 2) (B 1) (C 1)) ((A 2) (B 1) (C 2)) ((A 2) (B 1) (C 3))
> ((A 2) (B 2) (C 1)) ((A 2) (B 2) (C 2)) ((A 2) (B 2) (C 3))
> ((A 2) (B 3) (C 1)) ((A 2) (B 3) (C 2)) ((A 2) (B 3) (C 3))
> ((A 3) (B 1) (C 1)) ((A 3) (B 1) (C 2)) ((A 3) (B 1) (C 3))
> ((A 3) (B 2) (C 1)) ((A 3) (B 2) (C 2)) ((A 3) (B 2) (C 3))
> ((A 3) (B 3) (C 1)) ((A 3) (B 3) (C 2)) ((A 3) (B 3) (C 3)))
>
>Does that look like what you wanted?
>
>Kind regards,
>
>Hannah.
Hello!
········@aol.com <········@aol.com> wrote:
>Yes, this is exactly what I need!
Ok.
>This algorithm is a part of a larger function that I am trying to
>write. Currently, I have the following code:
It seems you have to learn a few Lisp *basics*, too.
>-------------------
>(setq nouns '(A B C))
>(setq domains '(1 2 3))
Naming convention: Global variables (if used at all!) usually have their
names surrounded with stars. Such as in
(defparameter *nouns* '(a b c))
(defparameter *domains* '(1 2 3))
>(defun subset-generator (nouns domains)
> (setq t1 '(0))
Why do you set a global variable?
> (setq result nil)
> ; Creates a blank array
> (loop as i from 2 to (list-length nouns)
> do (setq t1 (append t1 '(0))))
> (subset-generator-helper nouns domains result t1 0)
>)
As the whole code's quite a mess still (sorry for the wording!),
I'll comment a few Lisp basics only:
(defun subset-generator (nouns domains)
(let ((t1 (make-sequence 'list (list-length nouns) :initial-element 0))
(result nil))
(subset-generator-helper nouns domains result t1 0)))
Now, why do you pass a constant (result, i.e. nil) into
subset-generator-helper at all? No, there are no reference or in-out
parameters in Lisp in general. At least not in the way you might be
used to them in Pascal, C++ (Type& parameter) or Ada.
>; Helps generate the subset
>(defun subset-generator-helper (nouns domain res1 t2 p)
> ; Break condition
> (if (eq (nth p t2) (list-length domain))
> break)
eq isn't right for numbers! Use eql or =. What's break supposed to
do? Looks like a reference to an unbound variable, in fact!
(return-from subset-generator-helper nil) would at least do something,
but still probably not the right thing anyway, if seen in connection
with the later parts.
> (loop as i from 0 to (- (list-length nouns) 1)
> do (print (setq res1 (append res1 (list (nth i nouns)))))
> (print (setq res1 (append res1 (list (nth (nth i t2)
> domain))))))
You do stuff that terminates here.
> ; Temp separator
> (print ".")
> (loop as j from 0 to (- (list-length nouns) 1)
> do (+ (nth j t2) 1)
^^^^^^^^^^^^^^^^ Just just calculate something w/o changing
anything
> (subset-generator-helper nouns domain res1 t2 j)
> (- (nth j t2) 1))
^^^^^^^^^^^^^^^^ Dito
> res1
>)
>---------------------------
Why do you print so much? Just debugging? Then I'd separate that from
the calculations a bit more so it's easier to disable.
>Unfortunately, since I am pretty lost with LISP, it gives me an
>infinite loop and also does not iterate through the domain: (1 2 3).
>Am I going about it the right way or is there something stupid that I
>have done? Thanks a lot!
The idea of the algorithm itself looks contorted, and your coding style
is quite far from what's ok in Lisp.
>[...]
You *could* do things like "counting" up numbers of k (number of elements
in *nouns*) digits in base l (number of elements in *domains*) from zero
to maximum, collecting the appropriate result list.
Like in
(defun assignments (nouns domains)
(let* ((n-nouns (length nouns))
(n-domains (length domains))
(indexes (make-array n-nouns :initial-element 0)))
(flet ((result-item ()
(loop for i from 0 below n-nouns
for noun in nouns
collect (list noun (nth (aref indexes i) domains))))
(increment ()
(loop for i from (1- n-nouns) downto 0
do (if (>= (incf (aref indexes i)) n-domains)
(setf (aref indexes i) 0) ; and carry to the next
; digit by continuing the
; loop!
(return t)) ; increment terminated ok!
finally (return nil))))
(loop collect (result-item)
while (increment)))))
That's a more imperative variant.
The first version I did recently was more functional, using recursion
and mapcar.
Kind regards,
Hannah.
* Hannah Schroeter:
> The first version I did recently was more functional, using recursion
> and mapcar.
Something like
(defun pairls (keys data)
(labels ((pairls (keys pairls)
(if keys
(pairls (rest keys)
(mapcan (lambda (datum)
(mapcar (lambda (pairl)
(cons (cons (first keys)
datum)
pairl))
pairls))
data))
pairls)))
(pairls keys (list '()))))
?
--
"Hurry if you still want to see something. Everything is vanishing."
-- Paul C�zanne (1839-1906)
* Hannah Schroeter:
> The first version I did recently was more functional, using recursion
> and mapcar.
For those Functionals who don't mind the absence of recursion:
(defun pairls (keys data)
(reduce (lambda (pairls key)
(mapcan (lambda (datum)
(mapcar (lambda (pairl)
(cons (cons key datum) pairl))
pairls))
data))
keys :initial-value (list '())))
--
"Hurry if you still want to see something. Everything is vanishing."
-- Paul C�zanne (1839-1906)
This sounds like homework so I'll just give you some hints.
First the structute of the problem can be reduced to something like:
000 001 002
010 011 012
020 021 022
100 101 102
110 111 112
120 121 122
200 201 202
210 211 212
220 221 222
Note that A, B, C are just placeholders and can be abbreviated by the
position of
the position of the three numbers. Second the contents elements can be
abbreviated by
the index into the list. Lists are a very inefficient way to grind
permutations as
access is linear. You are better off with a array.
Start the function by recursivly "pumping" ut to the last digit.
loop for each value (0, 1, 2)
if not in the last position recursivly go up one position
Finally translate the notation into the lisp format
p� Wed, 28 Apr 2004 02:40:47 -0400, skrev <········@aol.com>:
> Hello, I am new to LISP and I am having a problem trying to program this
> algorithm.
>
> Let's say I have two lists:
>
> list1: (A B C)
> list2: (1 2 3)
>
> What I need to perform is an exhaustive append that creates a result list
> that looks like so:
>
> (((A 1)(B 1)(C 1))
> ((A 1)(B 1)(C 2))
> ((A 1)(B 1)(C 3))
> ((A 1)(B 2)(C 1))
> ((A 1)(B 2)(C 2))
> ((A 1)(B 2)(C 3))
> ((A 1)(B 3)(C 1))
>
> etc etc etc....
>
> ((A 3)(B 3)(C 3)))
>
> In the end, it should have 3^3 = 27 sublists.
>
> I have no idea how to do this in LISP. If anyone can help me out, this
> would
> be greatly appreciated!
>
>
>
--
Sender med M2, Operas revolusjonerende e-postprogram: http://www.opera.com/
John Thingstad writes:
> This sounds like homework so I'll just give you some hints.
> First the structute of the problem can be reduced to something like:
>
> 000 001 002
> 010 011 012
> 020 021 022
> 100 101 102
> 110 111 112
> 120 121 122
> 200 201 202
> 210 211 212
> 220 221 222
Oh my god, but this is counting from 0 to 26 in base 3!
> Note that A, B, C are just placeholders and can be abbreviated by the position of
> the position of the three numbers.
Exactly.
To sum things up, just count in base 3 and assign each digit to the
corresponding elements of the first and second list. The first list
being the "placeholders" and the second list is the "letters" you use
to write down your number.
(defun to-base-b (n b w)
"Converts integer N to a list of digits in base B and width W"
(let ((res '()))
(dotimes (w width)
(multiple-value-bind (q r) (truncate n b)
(push r res)
(setq n q)))
res))
(defun assignation (l1 l2)
(let ((len1 (length l1))
(len2 (length l2)))
(loop for i upto (1- (expt len2 len1))
collect (map 'list
(lambda (l v) (list l (nth v l2)))
l1
(to-base-b i len2 len1)))))
Kim Minh.