Mathematica: supply list of list to Intersection?

[jackmell]

I notice there are some functions in Mathematica in which you can't supply directly, an array of arguments but rather must give it a list. For example, GCD and LCM. I can use for example, GCD[2,3,8] and it returns 1. However if I code: GCD[{2,3,8}], the function call fails. I know of one way to correct this problem by using Apply, for example, Apply[GCD,{2,3,8}]. Intersection works this way also. However, I'm having problems implementing this with some code I'm writing with a list of lists. I would like to supply to the function, a list of lists and have it compute the intersections of members {a,b} such that a is from the first list and b from that second, then generalize this for a variable number of sublists. For example, suppose my list is:

myList={{{1,2},{3,4},{5,6}},{{7,1},{8,3},{9,5}}}

So that's 2 lists in myList and I I want to compute:

Intersection[{1,2},{7,1}], Intersection[{1,2},{8,3}],Intersection[{1,2},{9,5}]
Intersection[{3,4},{7,1}], Intersection[{3,4},{8,3}],Intersection[{3,4},{9,5}]
Intersection[{5,6},{7,1}], Intersection[{5,6},{8,3}],Intersection[{5,6},{9,5}]I realize I could just hard-code a loop but it would get messy because my list would have a variable number of sub-lists. I'm sure there is a compact way in a single-line command to formulate all those intersections for a variable number of sub-list in myList. However I just cannot figure it out.

Here's what I have so far but I must explicitly code each sublist and I'd like a way to avoid doing that since the number is variable so I'm hoping someone could help me:

myList = {{{1, 2}, {3, 4}, {5, 6}}, {{5, 7}, {3, 8}, {9, 6}}};
myOuter = Outer[Intersection, myList[[1]], myList[[2]], 1]

{{{}, {}, {}}, {{}, {3}, {}}, {{5}, {}, {6}}}

Ok thanks for reading,
Jack

 

[kontejnjer]

This is a bit of a mess, but it gets the job done:

Flatten@Table[
  Intersection[myList[[i, k]], myList[[j, n]]], {i,
  Length@myList}, {j, i + 1, Length@myList}, {k,
  Length[myList[[i]]]}, {n, Length[myList[[j]]]}]

The "j" iterator goes from i+1 to avoid comparing a list with itself. Though I haven't tested it myself, this should work for any number of lists. If you want to use it for something like GCD, just add "Sequence@@" before Flatten. Unfortunately I'm unaware of any "neat" solutions for this problem, although maybe MapThread could get the job done in a more concise form.

 

[jackmell]

Hi konte,

I've been working on this since 3am this morning and been frustrated. Looks like your code will do it although I need to flatten it out correctly so I can locate where all the intersections are {1}:

myList = {{{1, 2}, {3, 4}, {5, 6}, {17, 9}}, {{5, 7, 12}, {3, 8, 4}, {9, 6, 1}}};
Flatten[Table[Intersection[myList[[i,k]], myList[[j,n]]], {i, Length[myList]},
{j, i + 1, Length[myList]}, {k, Length[myList[[i]]]}, {n, Length[myList[[j]]]}], 2]

{{{}, {}, {1}}, {{}, {3, 4}, {}}, {{5}, {}, {6}}, {{}, {}, {9}}}

Think I'll go with that.

Thanks a bunch!
Jack

 

[jackmell]

Looks like the code won't work for more than 2 sublist:

myList = {{{1, 2,13}, {3, 4}, {5, 6}, {17, 9}}, {{5, 7, 12,13}, {3, 8, 4}, {9, 6, 1}},{{5, 7, 12}, {3, 8, 4,1}, {9, 6, 1,2}}};
Flatten[Table[Intersection[myList[[i,k]], myList[[j,n]]], {i, Length[myList]},
{j, i + 1, Length[myList]}, {k, Length[myList[[i]]]}, {n, Length[myList[[j]]]}], 2]
{{{13},{},{1}},{{},{3,4},{}},{{5},{},{6}},{{},{},{9}},{{},{1},{1,2}},{{},{3,4},{}},{{5},{},{6}},{{},{},{9}},{{5,7,12},{},{}},{{},{3,4,8},{}},{{},{1},{1,6,9}}}

As you can see the first intersection of {1,2,13}, {5,7,12,13}, {5,7,12} should be empty but is reporting {13}.
Ok,

I'll work on is some more. I just thought there was an easy elegant solution to this problem. If not I'll just code is messy. I'm really good at coding messy code that works. :)

 

[kontejnjer]

Hmm, I see, this is because my code just makes an intersection of at most 2 lists. This complicates matters a bit, but it should be possible to construct something similar that has a variable number of iterators using sequences. The main problems I see here is that you need to compare every list with every other list, without including the list itself, and that the lists aren't necessarily the same length.

 

[jackmell]

Hi konte!

Ok, this is what happened: It got too complicated and messy and very difficult for me to follow my own code so in the interest of just making the code understandable, I just decided to hard-code individual cases of 2,3, and 4 sub-sets as those are the ones I'm working on now. I first create all possible tuples, delete any non-distinct cases, then just run then through one by one with a For-loop hard-coded for Intersection[set1,set2] for two sets and so on. It's working, just not too elegantly.

Thanks for helping me though!
Jack

 

[Akater]

It's quite unclear what you're trying to achieve.

Does this help?

Outer[Intersection, ##, 1]& @@ myList

 

[jackmell]

It's quite unclear what you're trying to achieve.

Does this help?

Outer[Intersection, ##, 1]& @@ myList

Wow. I do believe that's going to get it Akater.

Here's a quick check:

myList={{{1,2,3},{4,5,6,1},{8,7,2}},{{2,4},{4,5,6}},{{3,4},{6,2}}};
(Outer[Intersection,##1,1]&)@@myList

{{{{},{2}},{{},{}}},{{{4},{}},{{4},{6}}},{{{},{2}},{{},{}}}}

I'm working with integer mod unit groups and the orbits of sets of elements of the group. For example, I may have 4 sets of integers, each containing 5,10,15, and 20 integers. That corresponds to a list containing four sub-lists: first sub-list has 5 sub-list in it (an orbit list for each of the 5 integers), then next sub-list has 10 sublists, and so fourth. I then need to check all combinations of orbits from each list for intersection={1}.

Right now, I have a function for each 2, 3, and 4 sets of integers and each function is about 200 lines of code. Coding it for the general case will cut down on a lot of code and make it cleaner-looking (unless it gets too hard to follow and edit later).I'll work today to see if your code works with the actual data.Thanks for you help,
Jack

 

[jackmell]

Dang it. Sorry, that's not going to work: I need "distinct" comparisons like (5,7,8) and not something like (5,5,8) and I don't think we can get Order to do that and I don't know of any other way to form "distinct" combinations other than using "Tuple" and then manually looping through them to remove non-distinct sets. Unless you guys know of a way of forming distinct n-tuples of a list of numbers. Here's an actual set of numbers:

{{7,17,23,25,31,41,47},{7,17,23,25,31,41,47},{5,11,13,19,29,35,37,43}}

Now, I cannot use the first of each list. That would be the 3-tuple (7,7,5) and they're not distinct. But I can choose 7 from the first, 17 from the second and 5 from the third giving me (7,17,5) and so on. Is there a way to find all the distinct 3-tuples (a,b,c) with a from first, b from second list, and c from third list other than first forming all possible tuples then deleting the non-distinct ones?

However, I can resolve the problem with passing a variable number of subsets to Intersection. First use Tuple to generate all possible combinations, then loop through the set and delete any non-distinct elements. Or figure out a more elegant way. Save the results to theOrbitList, then:

Apply[Intersection,#1]& /@ theOrbitList

and I'm pretty sure that's going to work for a variable number of sub-sets in theOrbitList.

This may look a little confusing. That first list of numbers are just the group elements. Each number in the list corresponds to an "orbit" list and it's the (distinct) orbit lists I'm passing to Intersection.

 

[Akater]

Before we go further,

are you aware of Mathematica symbols AbelianGroup, GroupGenerators and such?

 

[jackmell]

Before we go further,

are you aware of Mathematica symbols AbelianGroup, GroupGenerators and such?

I did initially work with permutation groups about a year ago when I first began studying Group Theory. But Mathematica's cycles are the inverse of my textbook format and that made it difficult to work with them.

Maybe though I should look at the Group Theory routines again to see if they could help me write better, cleaner code.

Thanks for that suggestion. :)

 

[Akater]

It's still hard to understand what you're trying to do. I don't have much background in finite groups but nevertheless I recommend not keeping your data in boring same-looking lists. Try introducing symbolic objects: orbits, underlying sets of groups, direct products, isomorphisms, etc., whatever you feel the need to work with right now. Things will probably become far cleaner.

It might also be useful to tell yourself once and for all there are no loops in Mathematica, at all, especially if you're involved with algebra problems like this one. (I can't stress the word “especially” enough.)

Concerning your question above,

a way of forming distinct n-tuples of a list of numbers

this

tuplesWithAllDistinctElements@lists:{___List} :=
Select[Tuples@lists, UnsameQ@@#&]

would do what you want (if I understood you correctly this time).

 

[jackmell]

It's still hard to understand what you're trying to do

I'm just studying integer mod groups and in particular this problem which I was hesitant to cite because I thought it was off-topic:

https://www.physicsforums.com/threa...-generators-and-automorphisms-of-z-nz.817628/

It might also be useful to tell yourself once and for all there are no loops in Mathematica, at all, especially if you're involved with algebra problems like this one. (I can't stress the word “especially” enough.)

I don't understand. Could you please explain? Do you mean simply just don't use For loops, While loops, Do loops etc.?

Concerning your question above,

this

tuplesWithAllDistinctElements@lists:{___List} :=
Select[Tuples@lists, UnsameQ@@#&]

would do what you want (if I understood you correctly this time).

Ok, you're light-years ahead of me. Afraid I can't even figure out how to use it. I'll work on it though. Might you however explain how I would use that to get the distinct elements in "testTuples"?

 

[jackmell]

Alright, I figured it out.

tuplesWithAllDistinctElements@lists:{___List} :=
Select[Tuples@lists, UnsameQ@@#&]

I mean I understand the function body: Apply Tuples to lists, then select from that list, all the elements which have distinct elements using the UnsameQ function. Don't quite understand how to drill down an extra level to check if they're the same but maybe be due to the double-at operator.

It's just a function that I call with the element list I wish to tuple-ize and then find the distinct ones. So here's the list of elements I want to 3-tuple:

genList={{5,7,11,13,17,19,23},{5,7,11,13,17,19,23},{5,7,11,13,17,19,23}}

then just call:

tuplesWithAllDistinctElements[genList]

and it indeed finds all the distinct ones. Wow. That's some sophisticated piece of code!

 

[Akater]

I've read the description of your problem. Again, I'm not sure if I understand it. For example, there are several “hanging indices” ($g_i$, in both cases — what indexing set does $i$ point to?) It's also not clear why you choose to represent group of units as a product of additive groups, and notations for automorphic generator and mappings between them are weird. But that could be due to my uninvolvement with the field, so I suspect I'd be wasting everyone's time trying to make this clear.

Do you mean simply just don't use For loops, While loops, Do loops etc.?

Well, yes. But I just happen to actively dislike those things since the first day I met them. However, if you're dealing with modern algebra, you study homomorphisms and notions [largely] derived from them. Those fit perfectly with something like Thread, Map, etc. So it's useful to try to forget about loops just for a day or two, and see how your writing style changes because of that. I don't consider Mathematica (or any other programming language) as a mere tool to calculate things; for me it's a powerful language to express ideas in. You might disagree but, whether you want it or not, if you use any language long enough, you'll start thinking in it. For abstract algebra, Mathametica is probably the best choice because you can very effectively express your thoughts in it using symbols that have direct counterparts in modern mathematics. But if you're using loops… why not just go Python? It's open source, and the community is huge, and sciPy probably has more algebra in it (though maybe less polished). Mathematica has lots of subtle flaws, and if you try to use it as a conventional language, you don't get the benefits it has. But the drawbacks are always there, silently crawling in the background in form of slow loops, weird-looking conditionals, and overall unnatural way of doing pretty much everything.

 

[jackmell]

Oh there's a simple explanation for all that Akater: I'm a complete novice in Abstract Algebra and mostly barely understand what I'm doing. I know what you mean by hanging indices. It's a work in progress. Also, I inserted your code into my code:

genNames=theOrderTable[[orderLocations,3]];
tList=tuplesWithAllDistinctElements[genNames];
orbitIndex=Flatten[Map[Position[orbitTable[[All,1]],#,1,1]&,#]]&/@ tList;
theOrbitList=Map[orbitTable[[#,2]]&,orbitIndex];

So, from the list of group elements, create all the possible distinct 3-tuples and then using that list, cross-reference into the orbit tables, and compile the associated orbit groupings so that I can then feed theOrbitList into the Intersection function so that I can then check which ones have intersection {1} as per that thread I cited.

 

[Akater]

Apply Tuples to lists, then select from that list, all the elements which have distinct elements using the UnsameQ function. Don't quite understand how to drill down an extra level to check if they're the same but maybe be due to the double-at operator.

If you really want to describe in words,

1) better say we don't “Apply” Tuples, but rather “Compose”:

In[1] := Apply[Test`Tuples, {a, b, c}]
Out[1] = Test`Tuples[a, b, c]

In[2] := Compose[Test`Tuples, {a, b, c}]
Out[2] = Test`Tuples[{a, b, c}]

2) OTOH, UnsameQ is not “drilled down” but is indeed Applied :-)

In[3] := Apply[Test`UnsameQ, {a, b, c}] // FullForm
Out[3] = Test`UnsameQ[a, b, c]

various @'s are merely infix forms of Compose and Apply:

In[4] := f@x === f[x] === Compose[f, x]
Out[4] = True

In[5] := f@@{x, y} === f[x, y] === Apply[f, {x, y}]
Out[5] = True

In[6] := f@@@{{x, y}, {q, p}} === {f[x, y], f[q, p]} === Apply[f, {{x, y}, {q, p}}, {1}]
Out[6] = True

 

[jackmell]

That's extremely informative Akater and I've been studying your examples and think I have come up with a solution to my original problem but my code that I think should be working isn't and I was wondering if you could look at it.

Edit: I made a mistake interpreting the data below. The code is working as expected.

First I save both the generators and their orbits in a single table named combinedList and the reason is, if I'm going to do a single Intersection operation, then I need to keep track of the generators whose orbit intersections are {1}. For example, here's the first five entries of combinedList//MatrixForm showing the 3-tuple generator lists in column 1 and their respective orbits in the second column:

$\left( \begin{array}{cc} \left( \begin{array}{c} 13 \\ 15 \\ 3 \\ \end{array} \right) & \left( \begin{array}{c} \{1,13\} \\ \{1,15\} \\ \{1,3,9,19,25,27\} \\ \end{array} \right) \\ \left( \begin{array}{c} 13 \\ 15 \\ 5 \\ \end{array} \right) & \left( \begin{array}{c} \{1,13\} \\ \{1,15\} \\ \{1,5,9,13,25,45\} \\ \end{array} \right) \\ \left( \begin{array}{c} 13 \\ 15 \\ 11 \\ \end{array} \right) & \left( \begin{array}{c} \{1,13\} \\ \{1,15\} \\ \{1,9,11,25,43,51\} \\ \end{array} \right) \\ \left( \begin{array}{c} 13 \\ 15 \\ 17 \\ \end{array} \right) & \left( \begin{array}{c} \{1,13\} \\ \{1,15\} \\ \{1,9,17,25,33,41\} \\ \end{array} \right) \\ \left( \begin{array}{c} 13 \\ 15 \\ 19 \\ \end{array} \right) & \left( \begin{array}{c} \{1,13\} \\ \{1,15\} \\ \{1,3,9,19,25,27\} \\ \end{array} \right) \\ \end{array} \right)$

as you can see, the entry (13,15,5) has orbit intersections of {1,13} so should not be selected. I thought this command would work:

myvals=Select[combinedArray,Intersection@@#[[2]]=={1}&];
myvals[[1;;5]]//MatrixForm

but it's not. Here's the first five entries for myvals which is still showing the entry for {13,15,5}.
$\left( \begin{array}{cc} \left( \begin{array}{c} 13 \\ 15 \\ 3 \\ \end{array} \right) & \left( \begin{array}{c} \{1,13\} \\ \{1,15\} \\ \{1,3,9,19,25,27\} \\ \end{array} \right) \\ \left( \begin{array}{c} 13 \\ 15 \\ 5 \\ \end{array} \right) & \left( \begin{array}{c} \{1,13\} \\ \{1,15\} \\ \{1,5,9,13,25,45\} \\ \end{array} \right) \\ \left( \begin{array}{c} 13 \\ 15 \\ 11 \\ \end{array} \right) & \left( \begin{array}{c} \{1,13\} \\ \{1,15\} \\ \{1,9,11,25,43,51\} \\ \end{array} \right) \\ \left( \begin{array}{c} 13 \\ 15 \\ 17 \\ \end{array} \right) & \left( \begin{array}{c} \{1,13\} \\ \{1,15\} \\ \{1,9,17,25,33,41\} \\ \end{array} \right) \\ \left( \begin{array}{c} 13 \\ 15 \\ 19 \\ \end{array} \right) & \left( \begin{array}{c} \{1,13\} \\ \{1,15\} \\ \{1,3,9,19,25,27\} \\ \end{array} \right) \\ \end{array} \right)$

I'll continue working on it too.

 

[Akater]

I'd gladly look at your definitions but, again, your data structures don't talk to me, and hence definitions don't either, since they're supposed to operate with that obscure data.

When I Import combinedArray from MathML posted here, I get

{{{{13}, {15}, {3}}, {{{1, 13}}, {{1, 15}}, {{1, 3, 9, 19, 25,
  27}}}}, {{{13}, {15}, {5}}, {{{1, 13}}, {{1, 15}}, {{1, 5, 9, 13,
  25, 45}}}}, {{{13}, {15}, {11}}, {{{1, 13}}, {{1, 15}}, {{1, 9,
  11, 25, 43, 51}}}}, {{{13}, {15}, {17}}, {{{1, 13}}, {{1,
  15}}, {{1, 9, 17, 25, 33, 41}}}}, {{{13}, {15}, {19}}, {{{1,
  13}}, {{1, 15}}, {{1, 3, 9, 19, 25, 27}}}}}

which is probably not what you have in mind. But even if the list was more shallow, it would still be more or less a mess.

I guess you represent elements of abelian groups as lists of integers. Why don't you pick something more user-friendly, like, for example,

element[soAndSo, abelianGroup[suchAndSuch]]

?

Then we could see what happens more clearly.

Note: AbelianGroup (capitalized) has built-in meaning, so I suggest you use abelianGroup instead. This is a common practice with Mathematica, in general.

 

[jackmell]

Ok, so here is the code to what I feel is finally a solution to the original problem:

genNames=theOrderTable[[orderLocations,3]];
tList=tuplesWithAllDistinctElements[genNames];
orbitIndex=Flatten[Map[Position[orbitTable[[All,1]],#,1,1]&,#]]&/@tList;
theOrbitList=Map[orbitTable[[#,2]]&,orbitIndex];
combinedArray=MapThread[{#1,#2}&,{tList,theOrbitList}];
theGeneratorMaps=Select[combinedArray,Intersection@@#[[2]]=={1}&];

So the code above does the following:
(1) compile all the 3-tuple generators meeting the requisite criteria in genNames,
(2) select only distinct 3-tuple genNames
(3) for each 3-tuple generator in tList, make cross-reference into orbit table to get orbits,
(4) combine into one table {{{3-tuple1},{orbits1}},{{3-tuple2},{orbits2}},...{{3-tuplen},{orbitn}}}
(5) select orbit tuples with intersections={1} and since the generators are in the same entry, we have a list of the generators in which the orbit intersections={1}.

 

[jackmell]

Sorry about the data, I just imported the Mathematica output as Latex so I wouldn't have to type in all that latex.

I guess you represent elements of abelian groups as lists of integers. Why don't you pick something more user-friendly, like, for example,

element[soAndSo, abelianGroup[suchAndSuch]]

I don't understand what you mean by this. I'm mainly interested in integer mod unit groups. For example, what would you recommend for the group $\mathbb{Z}_{15}^*=\{1,2,4,7,8,11,13,14\}$?

 

[Akater]

Well, that's a decision you better make: I'm certainly less familiar with those structures than you are.

I can only acknowledge that I can't make sense of the (obviously incomplete) pieces of your definitions and data that I saw. For example, I have no idea what tuplesWithAllDistinctElements does in your setting. You evaluate tuplesWithAllDistinctElements@genNames where genNames looks like a list of subsets of underlying sets of some groups of units, and sounds like a list of generator's names (which is clearly contradicting). Since you're computing Tuples, I guess elements of genNames participate in some direct product. It's not clear what is that product, exactly, or why do you then sieve its underlying set. The point is, I shouldn't really be guessing at all. When you pick appropriate data structures and write appropriate functions to work with them, everything becomes pretty self-explanatory. (Anyway, I certainly can't decypher what's going on when I don't know, e.g., what orderLocations or theOrderTable is.)

 

[jackmell]

I'm afraid I made a mistake which was being inadvertently corrected by another part of this function: I can't use Intersection because I need to find the sets of orbits which have no common elements except the identity element. In the second set of 3 orbits above, two of the orbits had 13 in common and so Intersection={1} would still pick out this set even though it doesn't meet the requirements. I have come up with a work-around:

myIdentityIntersections=Select[combinedArray,Length[DeleteDuplicates[Flatten[#1[[2]]]]]==minIntersectionLength&];

where I previously compute minIntersectionLength=8.

It works albeit not so elegant-looking. Anyway, I've learned a great deal today about Mathematica programming.

Thanks again Akater,
Jack