Wolfram Mathematica

4:02 AM

@Beli Can you help me with a simple thing?

(seed = 343808)
Give the id[] array that results from the following sequence of union operations
on a set of 10 items using the quick-find algorithm.

8-1 5-3 2-1 2-3 2-0 7-9

Recall: our quick-find convention for the union operation p-q is to change id[p]
(and perhaps some other entries) but not id[q].

I can understand how I'll make these unions.

But I haven't a sofisticated way to make the unions, for example: Create the set {2,3,0} from {2,3} and {2,0}.

R.M

4:52 AM

@GustavoBandeira {2,3} ~Join~ {2,0} // Union?

Gustavo Bandeira

@R.M Yep, But I want to create it for all the sets here: 8-1 5-3 2-1 2-3 2-0 7-9

I would do it with If - dunno if there's another way.

R.M

You have those in a list?

Gustavo Bandeira

Yep.

l = {{8, 1}, {5, 3}, {2, 1}, {2, 3}, {2, 0}, {7, 9}};

R.M

Union@Flatten@l

Gustavo Bandeira

No, it's not to perform the union in all them.

R.M

4:54 AM

oh, ok. I don't know what you're doing then... I just saw the last msg

Gustavo Bandeira

It's to perform the union on them if they share similar elements.

{2,3} {2,0} = {0,2,3}
{8,1}{5,3} = {8,1}{5,3}

Now as we have the set: {0,2,3} we should perform the union also with {5,3}

Until no further sets can be created.

Was I clear?

R.M

And similarity is only checked between adjacent sublists?

Gustavo Bandeira

Adjacent = Only who's beside him?

R.M

yes

Gustavo Bandeira

Nope, it's with all sets.

R.M

5:04 AM

Ok, here's one straightforward way:

l //. {h___, a_List, b_List, t___} :> {h, Union[a, b], t} /; Intersection[a, b] =!= {}

Note that this uses //. along with ___ which is very inefficient and will be slow for large lists, but is simple to follow and gets the job done for small lists. There are probably more efficient ways, but I'm too sleepy to think of any now

For your list, this gives {{0, 1, 2, 3, 5, 8}, {7, 9}}, which looks correct

Gustavo Bandeira

@R.M I'm looking at this in a Algorithms course. Do you think it's safe to use functions such as intersection and union? - I believe the course has a more generalist approach, and I still dunno if such functions are available in other programming languanges.

R.M

Well, it doesn't matter if Union is written simply as Union or as a bunch of for and if loops as long as they do the same thing. If you want, you can expand out the logic for Intersection if your prof wants pseudocode... However, if the focus is on algorithmic complexity, there are probably better (procedural) ways.

I think you should clarify with your prof if they expect you to write procedural code. Most probably they will, because it's easier for the students to understand the inner workings. Like how you can't get away using Sort in a lecture where the focus is on sorting algorithms...

rcollyer

@R.M any word on whether there will be a Town Hall chat?

R.M

5:21 AM

@rcollyer Probably before Wednesday:

12 hours ago, by F'x

@belisarius yeah, I already contacted Grace Note, and he feels (and I agree with his reasoning) that the chat cast cannot be any later than Wednesday… otherwise too many will have already cast their vote

Gustavo Bandeira

@R.M Ok. Thanks for the help.

R.M

No worries :)

If you want help with breaking that down into much simpler and efficient procedural constructs, you could ask at SO, for instance (explain in words what that code does) and use the algorithm tag

belisarius frequents that tag too, so he might answer it for all you know, but don't forget that SO is filled with people who are good at this

xzczd

7:23 AM

What's the meaning of clicking "This is a favorite question"? I used to think that it's an enhanced upvote but these days I find that I seemed to be wrong…

Oleksandr R.

7:50 AM

@xzczd Favorites are purely for your convenience and don't confer any rep points or other status on the poster. The list is part of your user profile (i.e. here); it is basically just a way to bookmark questions that you found useful. I suppose the list is visible to other users so that others can see what your interests are.

xzczd

8:38 AM

@OleksandrR. Ah~I see.

J. M.

10:35 AM

@Oleksandr: looks like you won't have to ask that question after all... >:)

Grace Note

11:28 AM

@J.M. @R.M - You two seen the invite for the town hall?

Oleksandr R.

@J.M. we'll see. I was wondering why he thinks a 1500-point plot takes too long, and then I realised: he's typing the points in manually! That and the use of a finite difference derivative on noisy data make me wonder whether this will be such a good opportunity after all...

J. M.

@GraceNote I haven't checked my e-mail today; wait...

Transcript for