[Chicago] Printing out the Cartesian product.

[Lewit, Douglas]

Hey thanks for the great feedback guys.  It has been a really crazy busy
day and I haven't had a chance to carefully go over all the replies.  Len,
your comparison to the BigInt algorithm is interesting.  I wrote that
program last semester in Data Structures.  You know, you've got two arrays
that represent giant int values greater than 2**31 - 1, and then you use a
carry variable whose initial value is 0 and then can take on values of 0 or
1 depending on the two integers being added.  I can see the resemblance to
what I'm trying to do here, although the problem is a tad bit different.
I'll think about it!

On a totally different subject, I've been messing around with Ocaml
lately.  Found some great YouTube tutorial videos about Ocaml and bought a
couple books on it.  Very interesting.  Is there any connection between
Python and Ocaml?  Just wondering.

Thanks guys!  Your feedback is a huge help to me in my studies.  Not sure
if I'll ever be a big league developer/programmer, but I've learned a lot
from your posts and replies.  Thank you so much.

Have a great weekend even if it's like monsoon season here in Chicago.
Yuck, I hate all this rain!

Doug.


On Thu, Jul 16, 2015 at 11:17 AM, Len Wanger <len_wanger at hotmail.com> wrote:

> Douglas,
>
> There are a lot of ways to do this, but since it's your homework I'll give
> you hints but not the code. One easy way to look at this is like
> implementing addition (with carrying digits) or an odometer. Create a
> vector/list of N digits, then loop over that list adding 1 each iteration
> by adding 1 to the least significant digit. If the digit set exceeds the
> high range for the digit (exceeds 4 in your example), then setting it to
> the low digit (in your example 1) and carry it the next least significant
> digit (i.e. add 1 to the next digit to the left). When you get to the
> maximum value (i.e. in your example 4 in each digit) stop.
>
> A couple of notes:
>
> 1) I would avoid recursion here. This is an example of simple tail
> recursion, and can easily be unrolled into a loop. In a language with a
> good optimizer you could right this recursively and let the compiler take
> care of it, but in Python it is very inefficient.
>
> 2) This is a great place to use a generator. The list can get very large
> (e.g. 4 choices per digit and 10 digits is a list with 4**10 entries, which
> is > 1 million). A yield statement in the right place in the loop will make
> it a generator which would be much more efficient.
>
> 3) The previous posting that this is like  a conversion to a different
> number base is not quite right. If you had 0 for a digit value that would
> be a nice way to look at it (then you could loop to base**num_digits and do
> a conversion to that base for each value). Since your example used digits
> "1" to "4" that's not quite right.
>
> Good luck,
>
> Len
>
> > Date: Wed, 15 Jul 2015 17:15:23 -0500
> > From: "Lewit, Douglas" <d-lewit at neiu.edu>
> > To: The Chicago Python Users Group <chicago at python.org>
> > Subject: [Chicago] Printing out the Cartesian product.
> >
> > Hi everyone,
> >
> > I need some advice on how to do something. Let's say that I want to print
> > out the Cartesian product of the integers 1 to 4. It would look something
> > like this:
> >
> > 1, 1, 1, 1
> > 1, 1, 1, 2
> > 1, 1, 1, 3
> > 1, 1, 1, 4
> > 1, 1, 2, 1
> > 1, 1, 2, 2
> > 1, 1, 2, 3
> > 1, 1, 2, 4
> > 1, 1, 3, 1
> > 1, 1, 3, 2
> > 1, 1, 3, 3, etc, etc until finally we have
> > ..............
> > 4, 4, 4, 3
> > 4, 4, 4, 4
> >
> > This is NOT a permutation because repetition is allowed. Nor is it a
> > combination because for example 1, 1, 1, 2 is distinct from 2, 1, 1, 1. I
> > believe this is technically called a Cartesian product.
> >
> > I know of two ways to do this:
> >
> > Method #1:
> >
> > *for a in range(1, 5):*
> > * for b in range(1, 5):*
> > * for c in range(1, 5):*
> > * for d in range(1, 5):*
> > * print( a, end = ", " )*
> > * print( b, end = ", " )*
> > * print( c, end = ", " )*
> > * print( d, end = "\n" )*
> >
> >
> > The above works just fine! But there's a problem. What if let's say I
> > want the Cartesian product of all the integers from 1 to 10? That means
> > working with 10 nested for-loops! That's insane! It's tedious to write
> > and probably even worse for the person who is reading it. So this method
> > is limited to smaller examples.
> >
> > Method #2:
> >
> > Cheat by using Python's itertools package! (Or is it a library? What's
> > the difference between a package and a library?)
> >
> > import itertools
> >
> > carProduct = itertools.product([1, 2, 3, 4], repeat = 4)
> >
> > *try:*
> > * while True:*
> > * print( next(carProduct) )*
> > *except StopIteration:*
> > * pass*
> >
> > This method is short and sweet! It works great! But it's really cheating
> > in the sense that the programmer is taking advantage of code that has
> > already been written. (I have nothing against doing that! But in a CS
> > class if I write down that answer on an exam do you think the professor
> is
> > going to give me any credit? Probably not!!! LOL! )
> >
> > Is there some other way? I'm guessing that I would need a for-loop that
> > contains a recursive function. Or.... maybe a recursive function that
> > contains a for-loop? I really don't know. I've been struggling with this
> > for a couple days now and I can't think of a solution. Can someone please
> > enlighten me?
> >
> > Gratefully,
> >
> > Douglas.
>
>
> _______________________________________________
> Chicago mailing list
> Chicago at python.org
> https://mail.python.org/mailman/listinfo/chicago
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/chicago/attachments/20150716/4d9d9a36/attachment.html>