Author |
Topic: select x numbers from n numbers in sequence evenly (Read 695 times) |
|
maaz
Newbie
Posts: 7
|
 |
select x numbers from n numbers in sequence evenly
« on: Mar 17th, 2008, 8:23pm » |
 Quote  Modify
|
This is my first and hopefully many more to post in future:
So, we are given a list of n numbers from 1-n and a number d. d < n. We need to select d numbers from n such that the selected numbers are evenly distributed.
So, n = [1...100] and d = 15. So, we need to select 15 values from n which are mostly evenly distributed.
Any ideas ?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: select x numbers from n numbers in sequence ev
« Reply #1 on: Mar 18th, 2008, 1:45am » |
Quote Modify
|
There's numerous ways.
Simplest would be to pick one uniformly, swap it to the front, pick one from the rest of the list uniformly, swap it to second place etc. Similar to how you'd could randomize a list of number, except you stop after d.
There's also a nice solution here in case n isn't known beforehand and you're only allowed one pass .
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: select x numbers from n numbers in sequence ev
« Reply #2 on: Mar 18th, 2008, 3:40am » |
Quote Modify
|
Another one
S={};
for ( int i=n-d ; i<n ; i++ )
{
int a = rand()%(i+1);
if !(a in S) S = S+{a};
else S = S+{i};
}
Explained here.
|
| « Last Edit: Mar 18th, 2008, 3:41am by Grimbal » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: select x numbers from n numbers in sequence ev
« Reply #3 on: Mar 18th, 2008, 3:42am » |
Quote Modify
|
on Mar 17th, 2008, 8:23pm, maaz wrote:| So, we need to select 15 values from n which are mostly evenly distributed. |
|
Why "mostly"?
|
|
IP Logged |
|
|
|
maaz
Newbie
Posts: 7
|
|
Re: select x numbers from n numbers in sequence ev
« Reply #4 on: Mar 18th, 2008, 8:17am » |
Quote Modify
|
Ok. So I made a mistake in my question.
The numbers in n are in sequence. Say 1...100. All 100 numbers in sequence and sorted.
If we are given pick up 10 numbers, we need to pick up 10, 20, 30..100. so that they are all evenly spaced.
They cannot be selected randomly as they need to be evenly spaced so the sequence of k numbers selected looks good. Now, if k is 15 or 7, how do we select k numbers that are evenly spaced here ?
for example, consider that k of these n numbers need to be plotted an x axis of a graph of n numbers and we need them to be as evenly spaced as possible. Picking them at random is not the solution.
Also, the random() % i+1 could be a little biased as say if k is 3 and n is 100, then we would always do random() % 98, 99, 100 and then we need to know how big the random() should be as compared to n.
|
| « Last Edit: Mar 18th, 2008, 8:38am by maaz » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: select x numbers from n numbers in sequence ev
« Reply #5 on: Mar 18th, 2008, 8:54am » |
Quote Modify
|
Huh.. well, in that case, just take i* N/k for i=1..k
|
| « Last Edit: Mar 18th, 2008, 8:54am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: select x numbers from n numbers in sequence ev
« Reply #6 on: Mar 18th, 2008, 11:23am » |
Quote Modify
|
on Mar 18th, 2008, 8:54am, towr wrote:| Huh.. well, in that case, just take i*N/k for i=1..k |
|
More interesting question would be if the numbers were not sorted and the values defined by the sorted list should be taken. .... Can you find the O(n) algorithm?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: select x numbers from n numbers in sequence ev
« Reply #7 on: Mar 18th, 2008, 1:33pm » |
Quote Modify
|
on Mar 18th, 2008, 11:23am, Hippo wrote:
More interesting question would be if the numbers were not sorted and the values defined by the sorted list should be taken. .... Can you find the O(n) algorithm? |
|
First find the smallest and largest number
Then make a length d array, where every position has a target value you want to approach, a long the lines of theprevious solution.
For each number try to put it in the closest bin, but only if it's closer to the target than what's in there already.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print