5
$\begingroup$

Does Mathematica support any data structure representing an unordered set (without multiplicity) of Mathematica expressions? I would like this data structure to support $O(1)$ insertion, deletion, and membership testing.

Note that according to this answer, Associations only support $O(\log n)$ insertion and deletion.

$\endgroup$
  • 4
    $\begingroup$ I think that for all practical purposes, you can consider Association to have O(1) complexity for all those operations. The point is that, implementing on the top-level any such structure would lead to constant factors far greater that log n for any sensible size of the set. You can also try System`Utilities`HashTable, described in e.g. this answer. $\endgroup$ – Leonid Shifrin Mar 19 '15 at 13:28
1
$\begingroup$

DeleteDuplicates is another way to build sets, or, more precisely, ordered lists with no duplicates (a friend of mine calls such things "suits," I think a brilliant name). Note the last little minitest here fails:

{DeleteDuplicates[{}],
 DeleteDuplicates[{1}] == DeleteDuplicates[{1, 1}],
 DeleteDuplicates[{2, 1, 3, 1, 2, 3, 3, 2, 2, 1}] == 
  DeleteDuplicates[{1, 2, 3}]}
{{}, True, False}

Easy to fix by composing with Sort:

ClearAll[set];
set = Sort@*DeleteDuplicates;
{set[{}],
 set[{1}] == set[{1, 1}],
 set[{2, 1, 3, 1, 2, 3, 3, 2, 2, 1}] == set[{1, 2, 3}]}
{{}, True, True}

Here's a specific implementation of the ideas in Leonid's comment:

ClearAll[set];
set[l_List] := Sort@Keys@Association@MapThread[Rule, {l, l}];
{set[{}],
 set[{1}] == set[{1, 1}],
 set[{2, 1, 3, 1, 2, 3, 3, 2, 2, 1}] == set[{1, 2, 3}]}
{{}, True, True}

Keep or remove the Sort depending on whether you want a set or a suit. However, the Sort introduces more overhead, getting you away from (close to) O(1) perf, as you requested.

EDIT: The difference between set and suit can be important if you're trying to emulate a combinatorial function like Permutations. This function treats duplicate elements as identical, but it is also 'stable', meaning that it doesn't change the orders of inputs. If you try to emulate it using a set instead of a suit, you can get a scrambled answer. For instance, consider

Permutations[{1, 1, 1, 0, 0}] // TeXForm

\begin{array}{ccccc} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ \end{array}

Let's make our own permutations that can take a collector function as an input, and try it out with suit to check that we get the same answer, in the same order, as with the built-in Permutations:

ClearAll[permutations, set, suit];
set[l_List] := Sort@Keys@Association@MapThread[Rule, {l, l}];
suit[l_List] := Keys@Association@MapThread[Rule, {l, l}];
permutations[collector_, {}] := {{}};
permutations[collector_, xs_List] :=
  collector[
   Flatten[
    Table[
     With[{
       x = xs[[i]],
       plucked = Join[xs[[;; i - 1]], xs[[i + 1 ;;]]]},
      Prepend[x] /@ permutations[collector, plucked]],
     {i, Length[xs]}],
    1]];

permutations[suit, {1, 1, 1, 0, 0}] // TeXForm

\begin{array}{ccccc} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ \end{array}

Now try it with set as the collector:

permutations[set, {1, 1, 1, 0, 0}] // TeXForm

\begin{array}{ccccc} 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ \end{array}

| improve this answer | |
$\endgroup$

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.