# can you help turn this into a math formula?

• April 3rd 2010, 07:46 PM
jacob
can you help turn this into a math formula?
I have a set of numbers e.g.

X = {1, 2, 3 ,4 ,10, 11, 12}

what would be the math notation for splitting the set into a list or sequence of smaller sets depending on some condition

e.g f(x, y) = |x - y| < 5

psudo code would be like this:-

function f(x, y):
return |x - y| < 5

Set X = {1, 2, 3 ,4, 10, 11, 12}
List<Set> lst = Empty

for(i = 1; i < X.Length; i = i+1) // i=1, iterate while i < X.Length, increment i by 1 every iteration
{
Set Tmp = Empty

while( f(X[i-1], X[i]) ) // keep adding members to set while function returns true
{
i = i + 1 // increment i
}

}

If this is not clear please let me know.

P.s. i think i migth need a memebrship function but i'm not sure how to write this out.

• April 4th 2010, 02:59 AM
emakarov
Quote:

I have a set of numbers
You must mean a sequence of numbers because the result of the splitting may depend on the order of numbers.

There are many ways, of course, more or less awkward. For example, first you may define a predicate $P$ on sequences as follows:

$P(\langle x_1,\dots,x_n\rangle)$ iff $f(x_i,x_{i+1})$ for each $1\le i.

Then you may say that for every sequence $s=\langle x_1,\dots,x_n\rangle$ there exists a sequence of breakpoints $x_{k_1},\dots,x_{k_m}$ where $k_1<\dots such that $s$ is equal to the concatenation of subsequences,

$\langle x_1,\dots,x_{k_1}\rangle,\langle x_{k_1+1},\dots,x_{k_2}\rangle,\dots,\langle x_{k_{m-1}+1},\dots,x_{k_m}\rangle,\langle x_{k_{m}+1},\dots,x_n\rangle$

each of those subsequences satisfy $P$, and $f(x_{k_i},x_{k_i+1})$ is false for each $1\le i\le m$.

Actually, after writing this, I see that this is too involved; it would probably take the reader too much effort to decipher all this. Besides, you need to consider carefully all limit cases: it is possible that n=0? n=1? m=0? m=1? etc. You need to make sure that the formulas make sense in all those cases; for example, that $k_0$ either is defined or never occurs, etc.

So, after defining the predicate $P$, I would probably say that $s$ is represented as a concatenation of maximal subsequences satisfying $P$. "Maximal" means that they cannot be made longer. This description would make a reasonable compromise between precision and clarity.

Of course, it is possible to write a program in a functional language (such as ML or Haskell) that splits a sequence in a required way. Functional languages are basically mathematical languages because programs consist of equalities defining functions, and the bodies of those definitions consist of compositions of functions (e.g., no sequences of operations like "Set Tmp = Empty" before doing the loop). That would provide ultimate precision but, again, this is not the most user-friendly presentation.