Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

[stackoverflow] [algorithm] Smashing sets together

Name: Anonymous 2015-02-17 20:46

Marxist feminist game developer Anita Leigh Goldbergstein is given N sets, e. g.:

★ <a, b>
★ <a, d>
★ <c>
★ <d, e>
★ <b, f, c>

She wants to merge them in such way that:

1⟩ resulting list of sets is the smallest possible,
2⟩ operations on sets that have non-null intersection (that is, if an element appears in both) are strictly forbidden.

For the data above, the smallest list will be:

★ <a, b, c, d, e> -- from 1, 3, 4
★ <a, b, c, d, f> -- from 2, 5

What algorithm would you donate to her to solve this problem‽

Name: Anonymous 2015-02-18 6:35

Define a graph whose vertices are the sets, and put edges between each pair of sets that share an element. The problem is then to 'fold' this graph into the smallest number of vertices.

So for example, if your graph contains a triangle (<a,b>, <b,c>, <a,c>) you can't expect to get better than 3.

Name: Anonymous 2015-02-18 6:39

>>3
You mean, that do not share an element

Name: Anonymous 2015-02-18 6:44

>>4
no i dont

Name: Anonymous 2015-02-18 6:49

>>5
nvm youre right

Name: Anonymous 2015-02-18 6:50

>>3
Yeah, it's edge coloring of a graph if the sets all have size 2.

Name: Anonymous 2015-02-18 7:01

letters are vertices, two element subsets are edges, and colors are unions of disjoint edges. Minimize colors.

Name: Anonymous 2015-02-18 8:19

>>8
The OP data has three-element sets, so unless you define something like "n-vertex edge" your approach makes no sense

Name: Anonymous 2015-02-18 8:33

>>9
>>7,8 show op's problem is at least as hard as edge coloring. >>3-kun actually described vertex coloring. Contracting two vertices together means you give them the same color. And since you can describe any graph with these sets, this problem is vertex coloring of arbitrary graphs. So, it's NP-hard.

Name: Anonymous 2015-02-18 8:40

DUBS CHECK'M

Name: Anonymous 2015-02-18 8:42

>>11
This one. This is the best algorithm in the thread.

Name: Anonymous 2015-02-18 8:46

I don't think Anita deserves better than brute force, construct all possible combinations and evaluate between them.

Name: Anita Goldsteinman 2015-02-18 17:53

>>2-13
Wow thank you /prog/, you surprised me with your math ability!

Name: Anonymous 2015-02-18 18:18

>>1
What algorithm would you donate to her to solve this problem‽

None. I wouldn't donate anything to a stupid Jewish cunt, as a matter of fact.

Name: Anonymous 2015-02-18 19:37

Actually no. There are 4 * 4 possible ways to transition from the OP's state to a smaller state. 4 * 4 / 2 actually because set union is commutative. From each of these, there are ceil(3 * 3 / 2). Etc. Therefore complexity of a bruteforce solution is n^4 (n^2 because obviously, another ^2 because each transition can involve any pair of sets)

Name: >>16 2015-02-18 19:39

If you add some optimizations on when to quit (e. g. if the number of unmergeable sets at the beginning of your step is already larger than the current leader, drop the branch), the real-life complexity can become quite manageable, especially for smaller values of n.

Name: Anonymous 2015-02-18 20:07

real-life complexity can become quite manageable, especially for smaller values of n.
Any time complexity is manageable for small n.

Name: Anonymous 2015-02-18 20:17

>>16
Actual complexity is n!!
4 * 3 * 2 * 1 is n!, and having each term squared makes things even worse…

Name: ok !Iy8llHQG2g 2015-02-19 10:21

no one has solved it except me

Name: Anonymous 2015-02-19 10:28

>>20
Who are you quoting?

Name: Anonymous 2015-02-19 10:51

>>20
I've been thinking about it, but I've come to the conclusion that OP's problem is ill defined.

Name: Anonymous 2015-02-19 11:29

>>22
Consider you're repeating digits checked.

Name: Anonymous 2015-02-19 12:08

>>21
back to the image boards please

Name: Anonymous 2015-02-19 13:30

The jugger, the jugger jugger man means war
The jugger, the jugger jugger man means war
The jugger, salute to the jugger means war
The jugger, the jugger jugger man means war

Name: Anonymous 2015-02-19 13:31

>>22
How so?
Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode + RSS -