Wikipedia:Reference desk/Archives/Computing/2016 July 11

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 11

Algorithm for Union of Sets

Let us denote $I=\{1,\dots ,n\}$, and denote $P_{k}(A)=\{B|B\subseteq A,|B|\leq k\}$.

I am looking for an efficient algorithm to transform $\{A_{i}\}\in P_{n}(P_{n}(I))$ into $\{\cup _{a\in A_{i}}{a}\}$.

Thanks in advance! 31.154.81.65 (talk) 10:25, 11 July 2016 (UTC)

Expressed with words, $P_{k}(A)$ is a set of k-element subsets of some $A$, right?

Then $P_{n}(I)$ is a set of n-element subsets of $I$. However, $I=\{1,\dots ,n\}$ is itself an n-element set, so it has just one n-element subset: $I\subseteq I$, hence $P_{n}(I)=\{I\}$.

Consequently $P_{n}(P_{n}(I))$ is a set of n-element subsets of a singleton $P_{n}(I)=\{I\}$, so it is $\{\{I\}\}$ if $n=1$, or an empty set otherwise.

Alas I can't get the $\{A_{i}\}\in \ldots$ part. Do you mean 'a singleton belonging to'...? If so, $\{A_{i}\}\in P_{n}(P_{n}(I))$ could only be $\{A_{i}\}=\{I\}=\{\{1\}\}$, so $A_{i}=\{1\}$ for $n=1$ (and does not exist at all for $n\neq 1$) and I can't see the reason for the $i$ index at $A_{i}$... --CiaPan (talk) 12:07, 11 July 2016 (UTC)

I'm sorry for the typo... I fixed my mistake (replacing equality sign with inequality sign). 31.154.81.65 (talk) —Preceding undated comment added 13:36, 11 July 2016 (UTC)

So, P_n(I) is simply the power set of I (where I = {1, 2, ... n}), and could be denoted P(I). Then P_n(P_n(I)), or more simply P_n(P(I)), is a truncated power set of P(I), containing only those sets of sets which have n or fewer elements from P(I). And your {A_i} is an element of that truncated power set of the power set?

In other words, you have a list of at most n lists of integers, the integers themselves ranging from 1 to n, the lists of integers presumably unsorted, with the additional constraints that the individual lists of integers have no duplication and that no two lists of integers from your list of lists would be the same even if sorted, and you want an efficient way to merge this list of lists into a single list containing, without duplication, exactly those integers which appeared in any list of your list of lists. Presumably you hope that these constraints will allow for a more efficient algorithm. Note that our article merge algorithm discusses the merging of sorted lists; I don't know what we have on the merging of unsorted lists without duplication. -- ToE 14:51, 11 July 2016 (UTC)

Okay, I'll read the article about merge algorithm carefully. Thank you for the idea to read this! 31.154.81.65 (talk) 05:55, 12 July 2016 (UTC)

If you can tell us your actual task, it would help us know if we are up against an XY problem. The multiple roles of n -- it is both the maximum value of the integers in your sets and is the maximum size of the elements which are in the truncated power set of the power set of I -- strike me as unlikely to arise naturally.

Your task, as I understand it, has the (perhaps slight) advantages over simply merging unsorted lists with possible duplication in that you know that the individual sets of integers themselves contain no duplication. Note that some languages offer set abstract data types which are often implemented "using more efficient data structures, particularly various flavors of trees, tries, or hash tables." Our article mentions the expected union and add operations, but I see that Python's built-in set type also offers an update operation, which "update the set, adding elements from all others." (In essence, a ∪= augmented assignment.) Even if you wish to roll your own solution, the library implementations may offer suggestions for optimization. -- ToE 20:31, 12 July 2016 (UTC)

• Assuming ToE did represent correctly the problem, a solution that is optimal in time (but disastrous in space) would be to read all the lists once to find the maximum value $n_{max}\leq n$, then create a boolean array of $n_{max}$ elements set to false, then read all the list and flip the bits in the array when the value is found. If you know $n$ you do not even need to do the first pass, and there is no way to do it more efficiently (you will eventually have to read all the elements of all the lists, and practically, the bit-flipping is easy to vectorize in many programming languages such as Python). Returning the sorted union is trivial then.

The downside of course is that if there is reason to suspect that $n_{max}$ is much larger than the size of the final list, the array will be much bigger than it would need to be by other methods. Tigraan^{Click here to contact me} 09:01, 12 July 2016 (UTC)

uninstall Yahoo! powered

Yesterday I installed an update of Freemake Video Downloader. It seemed to install a browser hijacker. It installed "Yahoo! Powered" and I can't uninstall it. Is that a browser hijacker? Bubba73 ^{You talkin' to me?} 16:44, 11 July 2016 (UTC)

Well, I ran Revo Uninstaller and that seemed to get it. Bubba73 ^{You talkin' to me?} 19:22, 11 July 2016 (UTC)

That would be Search.yahoo.com browser hijacker -- There are instructions for manual removal which are somewhat complicated (depending on OS & browser). This seems to be the most recent and comprehensive:[1]. --2606:A000:4C0C:E200:A073:98E5:BA6B:E905 (talk) 23:35, 12 July 2016 (UTC)