1
$\begingroup$

I have two sets of multisets, like this:

a: { { 11, 21, 31, 41 }, { 12, 22, 32, 42 }, { 13, 23, 33, 43 } }

b: { { 21, 121, 131 }, { 22, 122, 132 } }

I'm combining them together into another set of multisets by joining each multiset in a with each multiset in b:

a (operation) b = { 
  { 11, 21, 31, 41, 21, 121, 131 },
  { 12, 22, 32, 42, 21, 121, 131 },
  { 13, 23, 33, 43, 21, 121, 131 },
  { 11, 21, 31, 41, 22, 122, 132 },
  { 12, 22, 32, 42, 22, 122, 132 },
  { 13, 23, 33, 43, 22, 122, 132 }
}

The closest thing I can think of to describe this is a Cartesian product, but that's not really accurate.

Is there a name for the operation I'm performing on a and b?


I just realized that this operation is the same as a cross join in SQL, and took a look at some documentation on cross join to see how people describe that. Some docs for SQL Server describe it as "the Cartesian product of the tables involved in the join." Oracle's docs, Wikipedia, and others all describe it essentially the same way.

Is Cartesian product a correct name for this after all?

$\endgroup$
  • $\begingroup$ In coding theory we do a similar thing for set of vectors and for elements u,v say, we show it as u|v $\endgroup$ – S.B. Dec 6 '14 at 21:47
  • $\begingroup$ I don't think there's a standard name for the operation, however it does resemble more common operations like sumsets where we define $$A+B = \{a+b:a\in A,b\in B\}$$ except that instead of $+$ you use $\cup$ (or whatever joining multisets is usually). I've used your operation before, but I just wrote it as a function of the two sets without any special name. $\endgroup$ – Milo Brandt Dec 6 '14 at 21:48
  • $\begingroup$ @AlgebraicallyClosed if you were writing a function that did this in a program, what might you name it? $\endgroup$ – user198143 Dec 6 '14 at 22:01
  • $\begingroup$ it depends on which program you use ofcourse, I prefer SAGE, and it works fine with lists. I convert each set to list, and then this operation corresponds to adding two lists in SAGE, after I had done, I can convert the result back to a set. These conversions are easy in SAGE. Let me try to do it $\endgroup$ – S.B. Dec 6 '14 at 22:04
0
$\begingroup$
a = [[11, 21, 31, 41 ], [12, 22, 32, 42 ], [ 13, 23, 33, 43 ]]
b = [[ 21, 121, 131 ], [ 22, 122, 132 ] ]
︡︠[a[i]+b[j] for i in range (0,len(a))  for j in range (0,len(b))]

#gives the desired result on SAGE;

[[11, 21, 31, 41, 21, 121, 131], [11, 21, 31, 41, 22, 122, 132], [12, 22, 32, 42, 21, 121, 131], [12, 22, 32, 42, 22, 122, 132], [13, 23, 33, 43, 21, 121, 131], [13, 23, 33, 43, 22, 122, 132]]

you may also name the result, and check the size;

a = [[11, 21, 31, 41 ], [12, 22, 32, 42 ], [ 13, 23, 33, 43 ]]
b = [[ 21, 121, 131 ], [ 22, 122, 132 ] ]
︡︠L = [a[i]+b[j] for i in range (0,len(a))  for j in range (0,len(b))]
len(L)

gives you the output 6.

$\endgroup$
  • $\begingroup$ sorry for being this late, but I didn't have time. $\endgroup$ – S.B. Dec 6 '14 at 22:58
  • $\begingroup$ This is pretty much the algorithm I'm using, I'm trying to figure out what to call this operation though. $\endgroup$ – user198143 Dec 6 '14 at 23:46
  • $\begingroup$ For vectors they call a similar thing as "minkowski sum" or it is sometimes considered as "setwise addition". Maybe you can search about these and similar definitions $\endgroup$ – S.B. Dec 9 '14 at 5:54
  • $\begingroup$ I would rather call it "setwise union of multisets" .. $\endgroup$ – S.B. Dec 9 '14 at 6:06
  • $\begingroup$ I also found this Wikipedia definition, which looks like a similar thing Concatenation of sets of strings $\endgroup$ – S.B. Dec 9 '14 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.