bucket numbers by range
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I have a list of numbers:
0,1,2, 200,220,240, 310,330, 371,380,390
I want to put these numbers into four buckets using range with value 40 for example.
0,1,2 are all in range 40. So they should be bucketed together
200,220,240 - same story
301,330 - are in range 40
371,380,390 should be bucketed together.
I don't know how many numbers I would get or how many buckets I would need. I know only range value.
I'm looking for the minimum number of buckets with range R which will contain all numbers in some list of n numbers
I hope there are some algorithms for doing it. Could you please give some pointers? Thanks!
recreational-mathematics
asked Sep 5 at 6:38
Sergey
1063
add a comment |Â
up vote
1
down vote
favorite
I have a list of numbers:
0,1,2, 200,220,240, 310,330, 371,380,390
I want to put these numbers into four buckets using range with value 40 for example.
0,1,2 are all in range 40. So they should be bucketed together
200,220,240 - same story
301,330 - are in range 40
371,380,390 should be bucketed together.
I don't know how many numbers I would get or how many buckets I would need. I know only range value.
I'm looking for the minimum number of buckets with range R which will contain all numbers in some list of n numbers
I hope there are some algorithms for doing it. Could you please give some pointers? Thanks!
recreational-mathematics
asked Sep 5 at 6:38
Sergey
1063
Not sure I understand your question. Are you looking for the minimum number of buckets with range $R$ which will contain all numbers in some list of $n$ numbers?
– Jens
Sep 5 at 17:15
Yes, thank you, your problem summary sounds much better and cleaner.
– Sergey
Sep 5 at 21:02
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I have a list of numbers:
0,1,2, 200,220,240, 310,330, 371,380,390
I want to put these numbers into four buckets using range with value 40 for example.
0,1,2 are all in range 40. So they should be bucketed together
200,220,240 - same story
301,330 - are in range 40
371,380,390 should be bucketed together.
I don't know how many numbers I would get or how many buckets I would need. I know only range value.
I'm looking for the minimum number of buckets with range R which will contain all numbers in some list of n numbers
I hope there are some algorithms for doing it. Could you please give some pointers? Thanks!
recreational-mathematics
asked Sep 5 at 6:38
Sergey
1063
I have a list of numbers:
0,1,2, 200,220,240, 310,330, 371,380,390
I want to put these numbers into four buckets using range with value 40 for example.
0,1,2 are all in range 40. So they should be bucketed together
200,220,240 - same story
301,330 - are in range 40
371,380,390 should be bucketed together.
I don't know how many numbers I would get or how many buckets I would need. I know only range value.
I'm looking for the minimum number of buckets with range R which will contain all numbers in some list of n numbers
I hope there are some algorithms for doing it. Could you please give some pointers? Thanks!
recreational-mathematics
recreational-mathematics
asked Sep 5 at 6:38
Sergey
1063
asked Sep 5 at 6:38
Sergey
1063
edited Sep 5 at 21:03
asked Sep 5 at 6:38
Sergey
1063
asked Sep 5 at 6:38
Sergey
1063
asked Sep 5 at 6:38
Sergey
1063
1063
Not sure I understand your question. Are you looking for the minimum number of buckets with range $R$ which will contain all numbers in some list of $n$ numbers?
– Jens
Sep 5 at 17:15
Yes, thank you, your problem summary sounds much better and cleaner.
– Sergey
Sep 5 at 21:02
add a comment |Â
Not sure I understand your question. Are you looking for the minimum number of buckets with range $R$ which will contain all numbers in some list of $n$ numbers?
– Jens
Sep 5 at 17:15
Yes, thank you, your problem summary sounds much better and cleaner.
– Sergey
Sep 5 at 21:02
Not sure I understand your question. Are you looking for the minimum number of buckets with range $R$ which will contain all numbers in some list of $n$ numbers?
– Jens
Sep 5 at 17:15
Not sure I understand your question. Are you looking for the minimum number of buckets with range $R$ which will contain all numbers in some list of $n$ numbers?
– Jens
Sep 5 at 17:15
Yes, thank you, your problem summary sounds much better and cleaner.
– Sergey
Sep 5 at 21:02
Yes, thank you, your problem summary sounds much better and cleaner.
– Sergey
Sep 5 at 21:02
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
Say $m$ is the least number in our list. Then there must be a minimum list of buckets that includes the bucket $[m,m+R]$ where $R$ is the range. This bucket can't move any further to the right, since it will then not include $m$, and moving the bucket to the left wouldn't add anything, since it already contains the least element. Then we look at our list of elements not yet included in buckets, let $m_2$ be the least element in that list, and repeat. You can always just find a minimum list of buckets by including the bucket that contains the least uncovered element as its left endpoint, and repeat until you cover every element.
answered Sep 5 at 22:22
Kevin Long
3,17121228
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Say $m$ is the least number in our list. Then there must be a minimum list of buckets that includes the bucket $[m,m+R]$ where $R$ is the range. This bucket can't move any further to the right, since it will then not include $m$, and moving the bucket to the left wouldn't add anything, since it already contains the least element. Then we look at our list of elements not yet included in buckets, let $m_2$ be the least element in that list, and repeat. You can always just find a minimum list of buckets by including the bucket that contains the least uncovered element as its left endpoint, and repeat until you cover every element.
answered Sep 5 at 22:22
Kevin Long
3,17121228
add a comment |Â
up vote
1
down vote
Say $m$ is the least number in our list. Then there must be a minimum list of buckets that includes the bucket $[m,m+R]$ where $R$ is the range. This bucket can't move any further to the right, since it will then not include $m$, and moving the bucket to the left wouldn't add anything, since it already contains the least element. Then we look at our list of elements not yet included in buckets, let $m_2$ be the least element in that list, and repeat. You can always just find a minimum list of buckets by including the bucket that contains the least uncovered element as its left endpoint, and repeat until you cover every element.
answered Sep 5 at 22:22
Kevin Long
3,17121228
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Say $m$ is the least number in our list. Then there must be a minimum list of buckets that includes the bucket $[m,m+R]$ where $R$ is the range. This bucket can't move any further to the right, since it will then not include $m$, and moving the bucket to the left wouldn't add anything, since it already contains the least element. Then we look at our list of elements not yet included in buckets, let $m_2$ be the least element in that list, and repeat. You can always just find a minimum list of buckets by including the bucket that contains the least uncovered element as its left endpoint, and repeat until you cover every element.
answered Sep 5 at 22:22
Kevin Long
3,17121228
Say $m$ is the least number in our list. Then there must be a minimum list of buckets that includes the bucket $[m,m+R]$ where $R$ is the range. This bucket can't move any further to the right, since it will then not include $m$, and moving the bucket to the left wouldn't add anything, since it already contains the least element. Then we look at our list of elements not yet included in buckets, let $m_2$ be the least element in that list, and repeat. You can always just find a minimum list of buckets by including the bucket that contains the least uncovered element as its left endpoint, and repeat until you cover every element.
answered Sep 5 at 22:22
Kevin Long
3,17121228
answered Sep 5 at 22:22
Kevin Long
3,17121228
answered Sep 5 at 22:22
Kevin Long
3,17121228
answered Sep 5 at 22:22
Kevin Long
3,17121228
3,17121228
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2905947%2fbucket-numbers-by-range%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Not sure I understand your question. Are you looking for the minimum number of buckets with range $R$ which will contain all numbers in some list of $n$ numbers?
– Jens
Sep 5 at 17:15
Yes, thank you, your problem summary sounds much better and cleaner.
– Sergey
Sep 5 at 21:02