Best way to convert set to sequence?

[jk1234]

I have a set of pairs (NAME X DATE) that are returned from a pre-defined function, Member.

I want to convert this to a sequence, such that the earliest DATE is first in the order.

After spend too much time on this, I would like to ask the group what is the best way to convert the set into a sequence.

All pointers and suggestions are most welcome.

JK

 

[HallsofIvy]

So you want to convert from ordered pairs to an ordered sequence?

With something like (x, y) where x and y separately have discrete values, typically, what one does is use the "Lexicographic order": to order (x1, y1) and (x2, y2) look at x1 and x2 first. If x1< x2, (x1, y1) is before (x2, y2) no matter what y1 and y2 are. Or course, if x2< x1, then (x2, y2) is before (x1, y1). In the case that x1= x2, then you look at y1 and y2 and order by y1 and y2: if y1< y2, then (x, y1) is before (x, y2). If y2< y1, then (x, y2) is before (x, y1).

Of course, that is called "lexicographic" because that is precisely how words are ordered alphabetically. Since your pairs consist of "(name, date)" that is how you would decide if "x1< x2" and, of course, "y1< y2" is based on which date comes first.

 

[CRGreathouse]

I guess the real question is, what's the form of the data? If it were just in your head, just say that it's ordered and be done with it.

If you have this in a spreadsheet, most can sort automatically. If you have the data in a custom format, there are lots of sorting functions that can be written. Depending on the size of your data it might not be worthwhile even writing a particularly good one (sorting 10 elements with bubble sort just isn't that hard). You may also need to write a comparison function that takes two pairs and returns TRUE if the date of the first is <= the date of the second, and FALSE otherwise.

 

[gel]

is this a maths question, or a computing one?
a maths answer is to use lexicographic order as HallsofIvy says. Surely CRGreathouse's answer would only be correct if this was in the computing section.

 

[jk1234]

Many thanks for the responses, but I think I should provide more information. I am doing this as part of a formal software engineering task, which means I must adhere to set theory.

In simple terms, we have set comprehension, which allows me to describe a set of elements using a function. What I would like to know is whether there is anything like "sequence comprehension" that allows me to describe a sequence using a function?

Must sequences I have seen in books are explicitly described by listing their elements.

JK

 

[CRGreathouse]

In simple terms, we have set comprehension, which allows me to describe a set of elements using a function. What I would like to know is whether there is anything like "sequence comprehension" that allows me to describe a sequence using a function?

Ah.

Well, formally, a sequence is a type of set:

(a, b, c, d) = {{1, {a}}, {2, {b}}, {3, {c}}, {4, {d}}}

so set comprehension is sufficient for sequence comprehension.(Of course there are different ways of defining sequences in terms of sets.)

 

[jk1234]

True, but I have a problem defining a suitable set comprehension.

For example, suppose I have the set containing the following:

{Mary, Fred, Alice, Jack, Bob}

I now want that set converted to an equivalent sequence:

<Mary, Fred, Alice, Jack, Bob>

If I could iterate over the set, then I could concatenate each element of the set to a sequence. But, how do I iterate over the members of a set?

Thanks for helping.
JK

 

[gel]

I don't know the best way to answer your question, because I'm not sure what it is you are really wanting. Mathematically you could define a sequence of length n as a function f:{1,2,...,n}->S, where S is the set containing the range of elements that can be in the sequence. An arbitrary length sequence is then a pair (n,f). In C++ you could represent such an object using the http://www.cplusplus.com/reference/stl/vector/" class, which has the member functions size() to return the size (i.e., n) and operator[] to access elements (i.e., f).

I don't think representing it in terms of sets is such a good idea unless there's a particular reason for doing so.

Your initial question though was about sorting it in order of increasing date, for which you need an order on your set S of values, or at least a partial order.

how do I iterate over the members of a set?

I don't think that can be answered without first knowing how you have represented the set. You state that you have been given this set, but given it how? What does the function Member do?

 

[HallsofIvy]

True, but I have a problem defining a suitable set comprehension.

For example, suppose I have the set containing the following:

{Mary, Fred, Alice, Jack, Bob}

I now want that set converted to an equivalent sequence:

<Mary, Fred, Alice, Jack, Bob>

If I could iterate over the set, then I could concatenate each element of the set to a sequence. But, how do I iterate over the members of a set?

Thanks for helping.
JK

By DEFINING an order on the set. Obviously that can be done in many different ways.

 

[jk1234]

Feel free to state the obvious. ;)

 

[jk1234]

Ok, I will try to provide more information without too much detail.

I have a pre-defined function called members, as follows,

members : Group -> P (Name x Date)

where
Group represents a particular group
Name represents the name of the member
Date represents the year they joined

And P is the Power Set symbol.

Now, I need to pass a sequence of dates to another function that will tell me how many members joined in a particular year:

intake : seq Date -> N

I must use a sequence, to ensure duplicate dates are not ignored, because in sets {1965, 1965} = {1965}, whereas with a sequence the duplicates are kept <1965, 1965>.

I hope that helps, and once again thank you all for helping me.

JK

 

[HallsofIvy]

Now, I need to pass a sequence of dates to another function that will tell me how many members joined in a particular year:
Do you mean the ouput must be a sequence of integers telling how many people joined in each year of the input sequence? You say "tell how many members joint in a particular year". It that is true the input is just a single year.
If your input is a sequence of years, I see no reason why you have to allow duplicate dates. If your input is "1996, 1997, 1997" and your output is the number of members who joined in each year, why would you want to put 1997 twice? You would just get same output number twice. In any case, I think you are using the terms "set" and "sequence" in the computer sense, not mathematics.

It seems to me that what you want to do is first write a function that takes a single year as input, searches the data base, adding 1 each time you see that date, then, if you want it, write a function that accepts multiple years, running that first function for each year. The real question is what kind of iterator you are defining on your database.

 

[jk1234]

I never mentioned that I had a database, because I do not. I do not even have the luxury of a programming language. I must describe this using only mathematics, because it is part of a formal sprecification.

So, to re-iterate: I have the two predefined functions, and the output from the first function must be "manipulated" so it can be passed as input to the second function.

1. members : Group -> P (Name x Date)

2. something here that creates a sequence of all Dates from P (Name x Date)

3. intake : seq Date -> N

Using a filter, I can filter the sequence of dates from (2) (e.g <1987, 1990, 1965 ... > so that I have a new sequence that contains only a certain year, e.g <1965, 1965, 1965>. The result from function intake should then be then be 3.

 

[HallsofIvy]

I never mentioned that I had a database, because I do not. I do not even have the luxury of a programming language. I must describe this using only mathematics, because it is part of a formal sprecification.

A list of names and dates, as you say you have, is a data base.

So, to re-iterate: I have the two predefined functions, and the output from the first function must be "manipulated" so it can be passed as input to the second function.

1. members : Group -> P (Name x Date)

So, given the name of the group, members returns a list of (name, date) for everyone in the group?

2. something here that creates a sequence of all Dates from P (Name x Date)

I don't see why you would need this. At worst, you would need just "earliest date" and "latest date"- but if you iterate over the names, you don't need to do that.
What you do need is an "iterator"- some way to step through the entire group.

3. intake : seq Date -> N

Using a filter, I can filter the sequence of dates from (2) (e.g <1987, 1990, 1965 ... > so that I have a new sequence that contains only a certain year, e.g <1965, 1965, 1965>. The result from function intake should then be then be 3.