• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Paul Clapham
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Rob Spoor
  • Henry Wong
  • Liutauras Vilda
Saloon Keepers:
  • Tim Moores
  • Carey Brown
  • Stephan van Hulst
  • Tim Holloway
  • Piet Souris
Bartenders:
  • Frits Walraven
  • Himai Minh
  • Jj Roberts

Product of cross-ness

 
Marshal
Posts: 72407
315
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Please have a look at this thread, where somebody is trying to create a Set of tuples from other sets. Is that a Cartesian product, a cross‑product or what? To save me the bother of finding my copy of your book, how many of those types of product do you describe?
 
Saloon Keeper
Posts: 4350
163
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just had a look at that topic. It is unclear what OP wants: het starts off with having a Set and getting all possible combinations from it. and ends with two sets of which he wants a Cartesian product. The first is simply drawing from a Set with replacement and getting all possibilities when drawing 0, 1, 2, ... times. Paul mentiones a name, never knew that that had a name.
 
Author
Posts: 13
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hey, fun question! (Though this is not something covered in Math for Programmers... perhaps a future book!)

The power set of a set is the set of all of its subsets; it is a set of sets.  Sets by their nature don't come with orders.    It sounds like this is asking for all possible lists of length <= n whose entries are taken from some set.  This is related to cartesian products and cartesian power sets more so than ordinary power sets.

Here's an example.  If S is the set of possible values, like {4,5,6,7} then there's one singleton list for every element of S: [4], [5], [6], [7]

The cartesian product S x S is the set of all ordered pairs taken from the list, consisting of [4,4], [4,5], [4,6], [4,7], [5,4], [5,5], ... and so on (there are 4*4 = 16 of these)

The cartesian product S x S x S is the set of all ordered triples of elements of S, so [4,4,4], [4,4,5], and so on...

We also write S^n to be the n-fold cartesian product, so the cartesian product of n copies of S which looks like S x S x S x ... x S.  This is the set of all ordered n-tuples of elements of S.  For example, S^2 = S x S and S^4 = S x S x S x S, the set of all ordered 4-tuples.  S^0 contains a 0-tuple of elements of S, i.e. an empty list.  (I'm not sure how to write superscripts in this forum but, S^n is written like S to the nth power, indicating that it's a repeated product).

If you want, say, all possible lists of length <= 4 what you want to do is take the union of the carteisan powers S^0, S^1, S^2, S^3, and S^4, as in the combination of all elements of these sets.  This is

So, the point is, this problem looks expressible in terms of set terminology, but perhaps not using the power set.  Here's a Python solution, where the first function computes the nth cartesian power of a list elts of inputs, and then the second function computes their union

 
Piet Souris
Saloon Keeper
Posts: 4350
163
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Paul,

it is always amazing how short these python codes are, given one is used to java!

I use a Map<Integer, List<List<Integer>>> where the key is the length of the lists in the value, and I fill it using recursion, although that is not required. You could start with key = 0.

To make it generic, I have a method that sees all the integers in the map as indices into some List<T>.

But the code is a "few" lines longer than yours...    
 
Rototillers convert rich soil into dirt. Please note that this tiny ad is not a rototiller:
SKIP - a book about connecting industrious people with elderly land owners
https://coderanch.com/t/skip-book
reply
    Bookmark Topic Watch Topic
  • New Topic