Sometimes when writing pseudocodes in a paper I need to write statements of the form:

  • $A\gets\emptyset$ (initialization);
  • $A\gets A\cup\{i\}$ (add element $i$);
  • $|A|$ (calculate the cardinality);

which work fine with a set $A$.

The problem is that sometimes I need to access the $i$th element of a set $A$, $a_i$. What I understand is that there no such thing for sets. I mean I cannot write $a_i$ for the set $A$ unless the set $A$ is totally ordered. I decided to define everything from the beginning. So, I add a sentence like "All sets used in the pseudocodes are ordered. But, my supervisor told me why I do not simply use tuples? My question is that which one I should use, sets or tuples?

With a tuple $B$, I can absolutely write $b_i$ to access the $i$th element of $B$ but I afraid that I can write the following:

  • $B\gets\emptyset$ (initialize the tuple to be empty);
  • $B\gets B\cup\{i\}$ (add element $i$ to the tuple);
  • $|B|$ (get the cardinality of the tuple $B$);
  • $\begingroup$ The two sets $\{ 1,2 \}$ and $\{ 2,1 \}$ are the same set, while the two tuples $(1,2)$ and $(2,1)$ are different. $\endgroup$ – Mauro ALLEGRANZA Feb 20 '18 at 16:20
  • $\begingroup$ An $n$-uple is a function from $\{ 1,2,\ldots, n \}$ to a set $A$, where $a_i \in A$ is the value of the fucntion for the input $i$. $\endgroup$ – Mauro ALLEGRANZA Feb 20 '18 at 16:21

Many implementations of sets are ordered:

  • Java's TreeSet and the C++ STL set template both require that the set's elements are of an orderable type (or at least that you provide a comparator), which makes the ordering directly based on that of the element.
  • Since version 3.6, the Python implementation of sets preserves insertion order for the purposes of stuff like iteration and pop, though in 3.6 this is considered an implementation detail that is not to be relied upon.

I have a question for you though: why do you care about the index of items in the set? Is there something else going on here? Would something like pop suffice? Would something like iteration in arbitrary order suffice? Nowadays most languages of my acquaintance tend to prefer non-index-based iteration anyway:

in C++, for has a construction that accepts anything that has an iterator:

for (const auto& a: A) { ...do something with a... }

In Python, for is always about the iterator and if you really want indexes you'll actually use enumerate to get that:

for a in A: ...do something with a...

  • $\begingroup$ Thank you. Suppose I defined a set $A$. Then, I have a $\textbf{for}$ loop for i = 1 to length(A) do: get a_i. Here I needed the length of $A$ and the $i$th element of $A$. I can replace $A$ with an array (or tuple) and then do the same. How to do it with sets? $\endgroup$ – zdm Feb 20 '18 at 16:33
  • $\begingroup$ This is index-based iteration, so most languages let you get away without it: in C++ it's for (const auto& a: A) { ...do something with a... }, and in Python it's for a in A: ...do something with a... $\endgroup$ – Dan Uznanski Feb 20 '18 at 16:38
  • $\begingroup$ So I guess the real answer in this case is upgrade your pseudocode language to allow non-index-based iteration. $\endgroup$ – Dan Uznanski Feb 20 '18 at 17:11
  • $\begingroup$ But is it always possible to do the upgrade? I think sometimes we are forced to have the index of the array. $\endgroup$ – zdm Feb 20 '18 at 17:22
  • $\begingroup$ Bring an example and we'll see what we can come up with. Normally when I wish to iterate over a set in a specific orderi need to explain that order first $\endgroup$ – Dan Uznanski Feb 20 '18 at 17:26

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.