1
$\begingroup$

Let us have a sorted array of n numbers and we would like to find a well spaced set of C of them, More specifically, we want to get a subset $ S\subset T$ with |S| = C and with $min_{i,j \in S,i\ne j} |i-j|$ as large as possible. Come up an algorithm for fining the best S.

What is the correct output if the sorted array as 1, 2, 3, 4 ,5 ,6 and c is 3. What about if the sorted array as 1, 10, 11, 12, 23, 24, 25 and c is 3 ? also appreciated any hints to approached this question if you clearly understand what the question is asking.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Have you tried simpler situations? What is the correct output if the sorted array is 1, 2, 3 and C is 2? What is the correct output if the sorted array is 1, 2, 3, 4 ,5 and C is 2 or 3? What is the correct output if the sorted array is 1, 2, 3, 4 ,5 ,6,7 and C is 2 or 3? How can you make the set as large as possible? $\endgroup$ – John L. Feb 13 '19 at 1:21
  • $\begingroup$ if the sorted array is 1,2,3 and c is 2, then output is (1,2); if sorted array is 1,2,3,4,5 and c is 3 , then output is (1,2,3); I don't think the question is asking to make the set as large as possible, it is asking to make |i-j| to be as larger as possible. $\endgroup$ – CCOthers Feb 13 '19 at 1:41
  • $\begingroup$ "output is (1,2); if sorted array is 1,2,3,4,5 and c is 3, then output is (1,2,3)"? Your typo? (1,3,5)? $\endgroup$ – John L. Feb 13 '19 at 1:47
  • $\begingroup$ "How can you make the set as large as possible?" My statement was incomplete. I meant, suppose the difference $\min_{i,j \in S,i\ne j} |i-j|$ is given, how you make the set as large as possible? If you can make the largest such set, then you will know whether there is a subset with C elements. $\endgroup$ – John L. Feb 13 '19 at 1:52
  • $\begingroup$ not a typo, I have been trying to understand the question. $\endgroup$ – CCOthers Feb 13 '19 at 2:04
1
$\begingroup$

What is the correct output if the sorted array as 1, 2, 3, 4 ,5 ,6 and C is 3?

Let us try. How about (1,2,3)? Too closely together. We should push away 3. (1,2,6) looks more far apart. Hmm, (1,2) is not good. (1, 3, 6) is the best.

What about if the sorted array as 1, 10, 11, 12, 23, 24, 25 and C is 3 ?

We should include the smallest and biggest numbers, 1 and 25. Then we should choose a number as close to the middle as possible. (1,12,25).

...

Let us analyze $\min_{i,j \in S,i\ne j} |i-j|$. Suppose $S=\{a_1, a_2, \cdots, a_C\}$, where $a_k\le a_{k+1}$. Then $$\min_{i,j \in S,i\ne j} |i-j|=\min_{1\le k\lt C}|a_{k+1}-a_k|$$ since the difference between two non-adjacent numbers $a_k$ and $a_{k+t}$ must be greater than the difference between $a_k$ and $a_{k+1}$.

So the minimum difference among numbers in $S$ seems in "reverse proportion" to the difference between the adjacent or nearby numbers of the given array.

I will leave the above as a hint. Hopefully it is enough for you to figure out the rest.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you explain what it really meant "$min_{i,j \in S,i\ne j} |i-j|$ as large as possible "? My understanding is that: i and j are the two smallest element in the set S, then their difference is as large as possible ? isn't that contradiction ? $\endgroup$ – CCOthers Feb 24 '19 at 0:21
  • $\begingroup$ For example, if $S=\{1,4,6,8\}$. Then $(i,j)$ where $i,j\in S$ and $i\not=j$ can be $(1,4), (1,6), (1,8), (4,6), (4,8), (6,8)$. So $|i-j|$ is 3, 5, 7, 2, 4, 2 respectively. The min (which is shorthand for minimum) of all $|i-j|$ is 2. That minimum value, 2 takes place at (4,6) or (6,8). $\endgroup$ – John L. Feb 24 '19 at 4:59

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.