Mixing
Distribute an integer amount by a set of slots as evenly as possible
I am trying to figure an elegant way of implementing the distribution of an amount into a given set of slots in python.
For example:
7 oranges distributed onto 4 plates would return:
[2, 2, 2, 1]
10 oranges across 4 plates would be:
[3, 3, 2, 2]
python
edited Jan 24 at 23:41
John Kugelman
246k54406459
asked Jan 24 at 18:19
fmagnofmagno
167110
add a comment |
I am trying to figure an elegant way of implementing the distribution of an amount into a given set of slots in python.
For example:
7 oranges distributed onto 4 plates would return:
[2, 2, 2, 1]
10 oranges across 4 plates would be:
[3, 3, 2, 2]
python
edited Jan 24 at 23:41
John Kugelman
246k54406459
asked Jan 24 at 18:19
fmagnofmagno
167110
add a comment |
I am trying to figure an elegant way of implementing the distribution of an amount into a given set of slots in python.
For example:
7 oranges distributed onto 4 plates would return:
[2, 2, 2, 1]
10 oranges across 4 plates would be:
[3, 3, 2, 2]
python
edited Jan 24 at 23:41
John Kugelman
246k54406459
asked Jan 24 at 18:19
fmagnofmagno
167110
I am trying to figure an elegant way of implementing the distribution of an amount into a given set of slots in python.
For example:
7 oranges distributed onto 4 plates would return:
[2, 2, 2, 1]
10 oranges across 4 plates would be:
[3, 3, 2, 2]
python
python
edited Jan 24 at 23:41
John Kugelman
246k54406459
asked Jan 24 at 18:19
fmagnofmagno
167110
edited Jan 24 at 23:41
John Kugelman
246k54406459
asked Jan 24 at 18:19
fmagnofmagno
167110
edited Jan 24 at 23:41
John Kugelman
246k54406459
edited Jan 24 at 23:41
John Kugelman
246k54406459
edited Jan 24 at 23:41
John Kugelman
246k54406459
246k54406459
asked Jan 24 at 18:19
fmagnofmagno
167110
asked Jan 24 at 18:19
fmagnofmagno
167110
asked Jan 24 at 18:19
fmagnofmagno
167110
167110
add a comment |
add a comment |
5 Answers
5
active
oldest
votes
Conceptually, what you want to do is compute 7 // 4 = 1 and 7 % 4 = 3. This means that all the plates get 1 whole orange. The remainder of 3 tells you that three of the plates get an extra orange.
The divmod builtin is a shortcut for getting both quantities simultaneously:
def distribute(oranges, plates):
base, extra = divmod(oranges, plates)
return [base + (i < extra) for i in range(plates)]
With your example:
>>> distribute(oranges=7, plates=4)
[2, 2, 2, 1]
For completeness, you'd probably want to check that oranges is non-negative and plates is positive. Given those conditions, here are some additional test cases:
>>> distribute(oranges=7, plates=1)
[7]
>>> distribute(oranges=0, plates=4)
[0, 0, 0, 0]
>>> distribute(oranges=20, plates=2)
[10, 10]
>>> distribute(oranges=19, plates=4)
[5, 5, 5, 4]
>>> distribute(oranges=10, plates=4)
[3, 3, 2, 2]
answered Jan 24 at 18:26
Mad PhysicistMad Physicist
38.1k1676109
3
@Lserni. This method guarantees that the difference between the maximum and minimum plate is at most 1. What additional criteria did you have for evenness?
– Mad Physicist
Jan 24 at 23:06
1
While I agree that the distribution of the remainder could be improved from "shoved to the left", OP does nothing to lead me to believe that that's something they want.
– Mad Physicist
Jan 24 at 23:12
Actually the OP's second example indicates that your solution - apart from simplicity - is the one yielding the expected results (hadn't noticed it before).
– LSerni
Jan 25 at 6:47
add a comment |
You want to look at Bresenham's algorithm for drawing lines (i.e. distributing X pixels on a Y range as "straightly" as possible; the application of this to the distribution problem is straightforward).
This is an implementation I found here:
def get_line(start, end):
"""Bresenham's Line Algorithm
Produces a list of tuples from start and end
>>> points1 = get_line((0, 0), (3, 4))
>>> points2 = get_line((3, 4), (0, 0))
>>> assert(set(points1) == set(points2))
>>> print points1
[(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]
>>> print points2
[(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)]
"""
# Setup initial conditions
x1, y1 = start
x2, y2 = end
dx = x2 - x1
dy = y2 - y1
# Determine how steep the line is
is_steep = abs(dy) > abs(dx)
# Rotate line
if is_steep:
x1, y1 = y1, x1
x2, y2 = y2, x2
# Swap start and end points if necessary and store swap state
swapped = False
if x1 > x2:
x1, x2 = x2, x1
y1, y2 = y2, y1
swapped = True
# Recalculate differentials
dx = x2 - x1
dy = y2 - y1
# Calculate error
error = int(dx / 2.0)
ystep = 1 if y1 < y2 else -1
# Iterate over bounding box generating points between start and end
y = y1
points =
for x in range(x1, x2 + 1):
coord = (y, x) if is_steep else (x, y)
points.append(coord)
error -= abs(dy)
if error < 0:
y += ystep
error += dx
# Reverse the list if the coordinates were swapped
if swapped:
points.reverse()
return points
edited Jan 24 at 18:38
Mad Physicist
38.1k1676109
answered Jan 24 at 18:34
LSerniLSerni
41.4k64882
For a more clearly specified problem, this would be the better answer.
– Mad Physicist
Jan 24 at 18:37
1
Mad Physicist: not sure I agree with you. Elegance is a bit subjective criterion, but for a layman this is not as elegant :)
– gmagno
Jan 24 at 18:43
3
@gmagno. It's not just about elegance. This solution actually distributes the bins differently than mine. If there was an additional requirement to maintain as uniform a distribution across the peaks as possible, mine wouldn't cut it at all. But yes, this is more cumbersome and I'm guessing OP wanted the beginner version.
– Mad Physicist
Jan 25 at 3:55
add a comment |
See also more_itertools.distribute, a third-party tool and its source code.
Code
Here we distributes m items into n bins, one-by-one, and count each bin.
import more_itertools as mit
def sum_distrib(m, n):
"""Return an iterable of m items distributed across n spaces."""
return [sum(x) for x in mit.distribute(n, [1]*m)]
Demo
sum_distrib(10, 4)
# [3, 3, 2, 2]
sum_distrib(7, 4)
# [2, 2, 2, 1]
sum_distrib(23, 17)
# [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Example
This idea is akin to distributing a deck of cards among players. Here is an initial game of Slapjack
import random
import itertools as it
players = 8
suits = list("♠♡♢♣")
ranks = list(range(2, 11)) + list("JQKA")
deck = list(it.product(ranks, suits))
random.shuffle(deck)
hands = [list(hand) for hand in mit.distribute(players, deck)]
hands
# [[('A', '♣'), (9, '♠'), ('K', '♣'), (7, '♢'), ('A', '♠'), (5, '♠'), (2, '♠')],
# [(6, '♣'), ('Q', '♠'), (5, '♢'), (5, '♡'), (3, '♡'), (8, '♡'), (7, '♣')],
# [(7, '♡'), (9, '♢'), (2, '♢'), (9, '♡'), (7, '♠'), ('K', '♠')],
# ...]
where the cards are distributed "as equally as possible between all [8] players":
[len(hand) for hand in hands]
# [7, 7, 7, 7, 6, 6, 6, 6]
answered Jan 25 at 11:06
pylangpylang
14.1k24458
add a comment |
Mad Physicist answer is perfect. But if you want to distribute the oranges uniformley on the plates (eg. 2 3 2 3 vs 2 2 3 3 in the 7 oranges and 4 plates example), here's an simple idea.
Easy case
Take an example with 31 oranges and 7 plates for example.
Step 1: You begin like Mad Physicist with an euclidian division: 31 = 4*7 + 3. Put 4 oranges in each plate and keep the remaining 3.
[4, 4, 4, 4, 4, 4, 4]
Step 2: Now, you have more plates than oranges, and that's quite different: you have to distribute plates among oranges. You have 7 plates and 3 oranges left: 7 = 2*3 + 1. You will have 2 plates per orange (you have a plate left, but it doesn't matter). Let's call this 2 the leap. Start at leap/2 will be pretty :
[4, 5, 4, 5, 4, 5, 4]
Not so easy case
That was the easy case. What happens with 34 oranges and 7 plates?
Step 1: You still begin like Mad Physicist with an euclidian division: 34 = 4*7 + 6. Put 4 oranges in each plate and keep the remaining 6.
[4, 4, 4, 4, 4, 4, 4]
Step 2: Now, you have 7 plates and 6 oranges left: 7 = 1*6 + 1. You will have one plate per orange. But wait.. I don't have 7 oranges! Don't be afraid, I lend you an apple:
[5, 5, 5, 5, 5, 5, 4+apple]
But if you want some uniformity, you have to place that apple elsewhere! Why not try distribute apples like oranges in the first case? 7 plates, 1 apple : 7 = 1*7 + 0. The leap is 7, start at leap/2, that is 3:
[5, 5, 5, 4+apple, 5, 5, 5]
Step 3. You owe me an apple. Please give me back my apple :
[5, 5, 5, 4, 5, 5, 5]
To summarize : if you have few oranges left, you distribute the peaks, else you distribute the valleys. (Disclaimer: I'm the author of this "algorithm" and I hope it is correct, but please correct me if I'm wrong !)
The code
Enough talk, the code:
def distribute(oranges, plates):
base, extra = divmod(oranges, plates) # extra < plates
if extra == 0:
L = [base for _ in range(plates)]
elif extra <= plates//2:
leap = plates // extra
L = [base + (i%leap == leap//2) for i in range(plates)]
else: # plates/2 < extra < plates
leap = plates // (plates-extra) # plates - extra is the number of apples I lent you
L = [base + (1 - (i%leap == leap//2)) for i in range(plates)]
return L
Some tests:
>>> distribute(oranges=28, plates=7)
[4, 4, 4, 4, 4, 4, 4]
>>> distribute(oranges=29, plates=7)
[4, 4, 4, 5, 4, 4, 4]
>>> distribute(oranges=30, plates=7)
[4, 5, 4, 4, 5, 4, 4]
>>> distribute(oranges=31, plates=7)
[4, 5, 4, 5, 4, 5, 4]
>>> distribute(oranges=32, plates=7)
[5, 4, 5, 4, 5, 4, 5]
>>> distribute(oranges=33, plates=7)
[5, 4, 5, 5, 4, 5, 5]
>>> distribute(oranges=34, plates=7)
[5, 5, 5, 4, 5, 5, 5]
>>> distribute(oranges=35, plates=7)
[5, 5, 5, 5, 5, 5, 5]
answered Jan 25 at 19:39
jferardjferard
1,794312
add a comment |
Not sure how this works. But it returns the exact same results
a = 23
b = 17
s = pd.Series(pd.cut(mylist, b), index=mylist)
s.groupby(s).size().values
answered Feb 3 at 8:20
shantanuoshantanuo
11.9k58155263
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54353083%2fdistribute-an-integer-amount-by-a-set-of-slots-as-evenly-as-possible%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
Conceptually, what you want to do is compute 7 // 4 = 1 and 7 % 4 = 3. This means that all the plates get 1 whole orange. The remainder of 3 tells you that three of the plates get an extra orange.
The divmod builtin is a shortcut for getting both quantities simultaneously:
def distribute(oranges, plates):
base, extra = divmod(oranges, plates)
return [base + (i < extra) for i in range(plates)]
With your example:
>>> distribute(oranges=7, plates=4)
[2, 2, 2, 1]
For completeness, you'd probably want to check that oranges is non-negative and plates is positive. Given those conditions, here are some additional test cases:
>>> distribute(oranges=7, plates=1)
[7]
>>> distribute(oranges=0, plates=4)
[0, 0, 0, 0]
>>> distribute(oranges=20, plates=2)
[10, 10]
>>> distribute(oranges=19, plates=4)
[5, 5, 5, 4]
>>> distribute(oranges=10, plates=4)
[3, 3, 2, 2]
answered Jan 24 at 18:26
Mad PhysicistMad Physicist
38.1k1676109
3
@Lserni. This method guarantees that the difference between the maximum and minimum plate is at most 1. What additional criteria did you have for evenness?
– Mad Physicist
Jan 24 at 23:06
1
While I agree that the distribution of the remainder could be improved from "shoved to the left", OP does nothing to lead me to believe that that's something they want.
– Mad Physicist
Jan 24 at 23:12
Actually the OP's second example indicates that your solution - apart from simplicity - is the one yielding the expected results (hadn't noticed it before).
– LSerni
Jan 25 at 6:47
add a comment |
Conceptually, what you want to do is compute 7 // 4 = 1 and 7 % 4 = 3. This means that all the plates get 1 whole orange. The remainder of 3 tells you that three of the plates get an extra orange.
The divmod builtin is a shortcut for getting both quantities simultaneously:
def distribute(oranges, plates):
base, extra = divmod(oranges, plates)
return [base + (i < extra) for i in range(plates)]
With your example:
>>> distribute(oranges=7, plates=4)
[2, 2, 2, 1]
For completeness, you'd probably want to check that oranges is non-negative and plates is positive. Given those conditions, here are some additional test cases:
>>> distribute(oranges=7, plates=1)
[7]
>>> distribute(oranges=0, plates=4)
[0, 0, 0, 0]
>>> distribute(oranges=20, plates=2)
[10, 10]
>>> distribute(oranges=19, plates=4)
[5, 5, 5, 4]
>>> distribute(oranges=10, plates=4)
[3, 3, 2, 2]
answered Jan 24 at 18:26
Mad PhysicistMad Physicist
38.1k1676109
3
@Lserni. This method guarantees that the difference between the maximum and minimum plate is at most 1. What additional criteria did you have for evenness?
– Mad Physicist
Jan 24 at 23:06
1
While I agree that the distribution of the remainder could be improved from "shoved to the left", OP does nothing to lead me to believe that that's something they want.
– Mad Physicist
Jan 24 at 23:12
Actually the OP's second example indicates that your solution - apart from simplicity - is the one yielding the expected results (hadn't noticed it before).
– LSerni
Jan 25 at 6:47
add a comment |
Conceptually, what you want to do is compute 7 // 4 = 1 and 7 % 4 = 3. This means that all the plates get 1 whole orange. The remainder of 3 tells you that three of the plates get an extra orange.
The divmod builtin is a shortcut for getting both quantities simultaneously:
def distribute(oranges, plates):
base, extra = divmod(oranges, plates)
return [base + (i < extra) for i in range(plates)]
With your example:
>>> distribute(oranges=7, plates=4)
[2, 2, 2, 1]
For completeness, you'd probably want to check that oranges is non-negative and plates is positive. Given those conditions, here are some additional test cases:
>>> distribute(oranges=7, plates=1)
[7]
>>> distribute(oranges=0, plates=4)
[0, 0, 0, 0]
>>> distribute(oranges=20, plates=2)
[10, 10]
>>> distribute(oranges=19, plates=4)
[5, 5, 5, 4]
>>> distribute(oranges=10, plates=4)
[3, 3, 2, 2]
answered Jan 24 at 18:26
Mad PhysicistMad Physicist
38.1k1676109
Conceptually, what you want to do is compute 7 // 4 = 1 and 7 % 4 = 3. This means that all the plates get 1 whole orange. The remainder of 3 tells you that three of the plates get an extra orange.
The divmod builtin is a shortcut for getting both quantities simultaneously:
def distribute(oranges, plates):
base, extra = divmod(oranges, plates)
return [base + (i < extra) for i in range(plates)]
With your example:
>>> distribute(oranges=7, plates=4)
[2, 2, 2, 1]
For completeness, you'd probably want to check that oranges is non-negative and plates is positive. Given those conditions, here are some additional test cases:
>>> distribute(oranges=7, plates=1)
[7]
>>> distribute(oranges=0, plates=4)
[0, 0, 0, 0]
>>> distribute(oranges=20, plates=2)
[10, 10]
>>> distribute(oranges=19, plates=4)
[5, 5, 5, 4]
>>> distribute(oranges=10, plates=4)
[3, 3, 2, 2]
answered Jan 24 at 18:26
Mad PhysicistMad Physicist
38.1k1676109
edited Jan 24 at 18:31
answered Jan 24 at 18:26
Mad PhysicistMad Physicist
38.1k1676109
answered Jan 24 at 18:26
Mad PhysicistMad Physicist
38.1k1676109
answered Jan 24 at 18:26
Mad PhysicistMad Physicist
38.1k1676109
38.1k1676109
3
@Lserni. This method guarantees that the difference between the maximum and minimum plate is at most 1. What additional criteria did you have for evenness?
– Mad Physicist
Jan 24 at 23:06
1
While I agree that the distribution of the remainder could be improved from "shoved to the left", OP does nothing to lead me to believe that that's something they want.
– Mad Physicist
Jan 24 at 23:12
Actually the OP's second example indicates that your solution - apart from simplicity - is the one yielding the expected results (hadn't noticed it before).
– LSerni
Jan 25 at 6:47
add a comment |
3
@Lserni. This method guarantees that the difference between the maximum and minimum plate is at most 1. What additional criteria did you have for evenness?
– Mad Physicist
Jan 24 at 23:06
1
While I agree that the distribution of the remainder could be improved from "shoved to the left", OP does nothing to lead me to believe that that's something they want.
– Mad Physicist
Jan 24 at 23:12
Actually the OP's second example indicates that your solution - apart from simplicity - is the one yielding the expected results (hadn't noticed it before).
– LSerni
Jan 25 at 6:47
3
3
@Lserni. This method guarantees that the difference between the maximum and minimum plate is at most 1. What additional criteria did you have for evenness?
– Mad Physicist
Jan 24 at 23:06
@Lserni. This method guarantees that the difference between the maximum and minimum plate is at most 1. What additional criteria did you have for evenness?
– Mad Physicist
Jan 24 at 23:06
1
1
While I agree that the distribution of the remainder could be improved from "shoved to the left", OP does nothing to lead me to believe that that's something they want.
– Mad Physicist
Jan 24 at 23:12
While I agree that the distribution of the remainder could be improved from "shoved to the left", OP does nothing to lead me to believe that that's something they want.
– Mad Physicist
Jan 24 at 23:12
Actually the OP's second example indicates that your solution - apart from simplicity - is the one yielding the expected results (hadn't noticed it before).
– LSerni
Jan 25 at 6:47
Actually the OP's second example indicates that your solution - apart from simplicity - is the one yielding the expected results (hadn't noticed it before).
– LSerni
Jan 25 at 6:47
add a comment |
You want to look at Bresenham's algorithm for drawing lines (i.e. distributing X pixels on a Y range as "straightly" as possible; the application of this to the distribution problem is straightforward).
This is an implementation I found here:
def get_line(start, end):
"""Bresenham's Line Algorithm
Produces a list of tuples from start and end
>>> points1 = get_line((0, 0), (3, 4))
>>> points2 = get_line((3, 4), (0, 0))
>>> assert(set(points1) == set(points2))
>>> print points1
[(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]
>>> print points2
[(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)]
"""
# Setup initial conditions
x1, y1 = start
x2, y2 = end
dx = x2 - x1
dy = y2 - y1
# Determine how steep the line is
is_steep = abs(dy) > abs(dx)
# Rotate line
if is_steep:
x1, y1 = y1, x1
x2, y2 = y2, x2
# Swap start and end points if necessary and store swap state
swapped = False
if x1 > x2:
x1, x2 = x2, x1
y1, y2 = y2, y1
swapped = True
# Recalculate differentials
dx = x2 - x1
dy = y2 - y1
# Calculate error
error = int(dx / 2.0)
ystep = 1 if y1 < y2 else -1
# Iterate over bounding box generating points between start and end
y = y1
points =
for x in range(x1, x2 + 1):
coord = (y, x) if is_steep else (x, y)
points.append(coord)
error -= abs(dy)
if error < 0:
y += ystep
error += dx
# Reverse the list if the coordinates were swapped
if swapped:
points.reverse()
return points
edited Jan 24 at 18:38
Mad Physicist
38.1k1676109
answered Jan 24 at 18:34
LSerniLSerni
41.4k64882
For a more clearly specified problem, this would be the better answer.
– Mad Physicist
Jan 24 at 18:37
1
Mad Physicist: not sure I agree with you. Elegance is a bit subjective criterion, but for a layman this is not as elegant :)
– gmagno
Jan 24 at 18:43
3
@gmagno. It's not just about elegance. This solution actually distributes the bins differently than mine. If there was an additional requirement to maintain as uniform a distribution across the peaks as possible, mine wouldn't cut it at all. But yes, this is more cumbersome and I'm guessing OP wanted the beginner version.
– Mad Physicist
Jan 25 at 3:55
add a comment |
You want to look at Bresenham's algorithm for drawing lines (i.e. distributing X pixels on a Y range as "straightly" as possible; the application of this to the distribution problem is straightforward).
This is an implementation I found here:
def get_line(start, end):
"""Bresenham's Line Algorithm
Produces a list of tuples from start and end
>>> points1 = get_line((0, 0), (3, 4))
>>> points2 = get_line((3, 4), (0, 0))
>>> assert(set(points1) == set(points2))
>>> print points1
[(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]
>>> print points2
[(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)]
"""
# Setup initial conditions
x1, y1 = start
x2, y2 = end
dx = x2 - x1
dy = y2 - y1
# Determine how steep the line is
is_steep = abs(dy) > abs(dx)
# Rotate line
if is_steep:
x1, y1 = y1, x1
x2, y2 = y2, x2
# Swap start and end points if necessary and store swap state
swapped = False
if x1 > x2:
x1, x2 = x2, x1
y1, y2 = y2, y1
swapped = True
# Recalculate differentials
dx = x2 - x1
dy = y2 - y1
# Calculate error
error = int(dx / 2.0)
ystep = 1 if y1 < y2 else -1
# Iterate over bounding box generating points between start and end
y = y1
points =
for x in range(x1, x2 + 1):
coord = (y, x) if is_steep else (x, y)
points.append(coord)
error -= abs(dy)
if error < 0:
y += ystep
error += dx
# Reverse the list if the coordinates were swapped
if swapped:
points.reverse()
return points
edited Jan 24 at 18:38
Mad Physicist
38.1k1676109
answered Jan 24 at 18:34
LSerniLSerni
41.4k64882
For a more clearly specified problem, this would be the better answer.
– Mad Physicist
Jan 24 at 18:37
1
Mad Physicist: not sure I agree with you. Elegance is a bit subjective criterion, but for a layman this is not as elegant :)
– gmagno
Jan 24 at 18:43
3
@gmagno. It's not just about elegance. This solution actually distributes the bins differently than mine. If there was an additional requirement to maintain as uniform a distribution across the peaks as possible, mine wouldn't cut it at all. But yes, this is more cumbersome and I'm guessing OP wanted the beginner version.
– Mad Physicist
Jan 25 at 3:55
add a comment |
You want to look at Bresenham's algorithm for drawing lines (i.e. distributing X pixels on a Y range as "straightly" as possible; the application of this to the distribution problem is straightforward).
This is an implementation I found here:
def get_line(start, end):
"""Bresenham's Line Algorithm
Produces a list of tuples from start and end
>>> points1 = get_line((0, 0), (3, 4))
>>> points2 = get_line((3, 4), (0, 0))
>>> assert(set(points1) == set(points2))
>>> print points1
[(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]
>>> print points2
[(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)]
"""
# Setup initial conditions
x1, y1 = start
x2, y2 = end
dx = x2 - x1
dy = y2 - y1
# Determine how steep the line is
is_steep = abs(dy) > abs(dx)
# Rotate line
if is_steep:
x1, y1 = y1, x1
x2, y2 = y2, x2
# Swap start and end points if necessary and store swap state
swapped = False
if x1 > x2:
x1, x2 = x2, x1
y1, y2 = y2, y1
swapped = True
# Recalculate differentials
dx = x2 - x1
dy = y2 - y1
# Calculate error
error = int(dx / 2.0)
ystep = 1 if y1 < y2 else -1
# Iterate over bounding box generating points between start and end
y = y1
points =
for x in range(x1, x2 + 1):
coord = (y, x) if is_steep else (x, y)
points.append(coord)
error -= abs(dy)
if error < 0:
y += ystep
error += dx
# Reverse the list if the coordinates were swapped
if swapped:
points.reverse()
return points
edited Jan 24 at 18:38
Mad Physicist
38.1k1676109
answered Jan 24 at 18:34
LSerniLSerni
41.4k64882
You want to look at Bresenham's algorithm for drawing lines (i.e. distributing X pixels on a Y range as "straightly" as possible; the application of this to the distribution problem is straightforward).
This is an implementation I found here:
def get_line(start, end):
"""Bresenham's Line Algorithm
Produces a list of tuples from start and end
>>> points1 = get_line((0, 0), (3, 4))
>>> points2 = get_line((3, 4), (0, 0))
>>> assert(set(points1) == set(points2))
>>> print points1
[(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]
>>> print points2
[(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)]
"""
# Setup initial conditions
x1, y1 = start
x2, y2 = end
dx = x2 - x1
dy = y2 - y1
# Determine how steep the line is
is_steep = abs(dy) > abs(dx)
# Rotate line
if is_steep:
x1, y1 = y1, x1
x2, y2 = y2, x2
# Swap start and end points if necessary and store swap state
swapped = False
if x1 > x2:
x1, x2 = x2, x1
y1, y2 = y2, y1
swapped = True
# Recalculate differentials
dx = x2 - x1
dy = y2 - y1
# Calculate error
error = int(dx / 2.0)
ystep = 1 if y1 < y2 else -1
# Iterate over bounding box generating points between start and end
y = y1
points =
for x in range(x1, x2 + 1):
coord = (y, x) if is_steep else (x, y)
points.append(coord)
error -= abs(dy)
if error < 0:
y += ystep
error += dx
# Reverse the list if the coordinates were swapped
if swapped:
points.reverse()
return points
edited Jan 24 at 18:38
Mad Physicist
38.1k1676109
answered Jan 24 at 18:34
LSerniLSerni
41.4k64882
edited Jan 24 at 18:38
Mad Physicist
38.1k1676109
edited Jan 24 at 18:38
Mad Physicist
38.1k1676109
edited Jan 24 at 18:38
Mad Physicist
38.1k1676109
38.1k1676109
answered Jan 24 at 18:34
LSerniLSerni
41.4k64882
answered Jan 24 at 18:34
LSerniLSerni
41.4k64882
answered Jan 24 at 18:34
LSerniLSerni
41.4k64882
41.4k64882
For a more clearly specified problem, this would be the better answer.
– Mad Physicist
Jan 24 at 18:37
1
Mad Physicist: not sure I agree with you. Elegance is a bit subjective criterion, but for a layman this is not as elegant :)
– gmagno
Jan 24 at 18:43
3
@gmagno. It's not just about elegance. This solution actually distributes the bins differently than mine. If there was an additional requirement to maintain as uniform a distribution across the peaks as possible, mine wouldn't cut it at all. But yes, this is more cumbersome and I'm guessing OP wanted the beginner version.
– Mad Physicist
Jan 25 at 3:55
add a comment |
For a more clearly specified problem, this would be the better answer.
– Mad Physicist
Jan 24 at 18:37
1
Mad Physicist: not sure I agree with you. Elegance is a bit subjective criterion, but for a layman this is not as elegant :)
– gmagno
Jan 24 at 18:43
3
@gmagno. It's not just about elegance. This solution actually distributes the bins differently than mine. If there was an additional requirement to maintain as uniform a distribution across the peaks as possible, mine wouldn't cut it at all. But yes, this is more cumbersome and I'm guessing OP wanted the beginner version.
– Mad Physicist
Jan 25 at 3:55
For a more clearly specified problem, this would be the better answer.
– Mad Physicist
Jan 24 at 18:37
For a more clearly specified problem, this would be the better answer.
– Mad Physicist
Jan 24 at 18:37
1
1
Mad Physicist: not sure I agree with you. Elegance is a bit subjective criterion, but for a layman this is not as elegant :)
– gmagno
Jan 24 at 18:43
Mad Physicist: not sure I agree with you. Elegance is a bit subjective criterion, but for a layman this is not as elegant :)
– gmagno
Jan 24 at 18:43
3
3
@gmagno. It's not just about elegance. This solution actually distributes the bins differently than mine. If there was an additional requirement to maintain as uniform a distribution across the peaks as possible, mine wouldn't cut it at all. But yes, this is more cumbersome and I'm guessing OP wanted the beginner version.
– Mad Physicist
Jan 25 at 3:55
@gmagno. It's not just about elegance. This solution actually distributes the bins differently than mine. If there was an additional requirement to maintain as uniform a distribution across the peaks as possible, mine wouldn't cut it at all. But yes, this is more cumbersome and I'm guessing OP wanted the beginner version.
– Mad Physicist
Jan 25 at 3:55
add a comment |
See also more_itertools.distribute, a third-party tool and its source code.
Code
Here we distributes m items into n bins, one-by-one, and count each bin.
import more_itertools as mit
def sum_distrib(m, n):
"""Return an iterable of m items distributed across n spaces."""
return [sum(x) for x in mit.distribute(n, [1]*m)]
Demo
sum_distrib(10, 4)
# [3, 3, 2, 2]
sum_distrib(7, 4)
# [2, 2, 2, 1]
sum_distrib(23, 17)
# [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Example
This idea is akin to distributing a deck of cards among players. Here is an initial game of Slapjack
import random
import itertools as it
players = 8
suits = list("♠♡♢♣")
ranks = list(range(2, 11)) + list("JQKA")
deck = list(it.product(ranks, suits))
random.shuffle(deck)
hands = [list(hand) for hand in mit.distribute(players, deck)]
hands
# [[('A', '♣'), (9, '♠'), ('K', '♣'), (7, '♢'), ('A', '♠'), (5, '♠'), (2, '♠')],
# [(6, '♣'), ('Q', '♠'), (5, '♢'), (5, '♡'), (3, '♡'), (8, '♡'), (7, '♣')],
# [(7, '♡'), (9, '♢'), (2, '♢'), (9, '♡'), (7, '♠'), ('K', '♠')],
# ...]
where the cards are distributed "as equally as possible between all [8] players":
[len(hand) for hand in hands]
# [7, 7, 7, 7, 6, 6, 6, 6]
answered Jan 25 at 11:06
pylangpylang
14.1k24458
add a comment |
See also more_itertools.distribute, a third-party tool and its source code.
Code
Here we distributes m items into n bins, one-by-one, and count each bin.
import more_itertools as mit
def sum_distrib(m, n):
"""Return an iterable of m items distributed across n spaces."""
return [sum(x) for x in mit.distribute(n, [1]*m)]
Demo
sum_distrib(10, 4)
# [3, 3, 2, 2]
sum_distrib(7, 4)
# [2, 2, 2, 1]
sum_distrib(23, 17)
# [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Example
This idea is akin to distributing a deck of cards among players. Here is an initial game of Slapjack
import random
import itertools as it
players = 8
suits = list("♠♡♢♣")
ranks = list(range(2, 11)) + list("JQKA")
deck = list(it.product(ranks, suits))
random.shuffle(deck)
hands = [list(hand) for hand in mit.distribute(players, deck)]
hands
# [[('A', '♣'), (9, '♠'), ('K', '♣'), (7, '♢'), ('A', '♠'), (5, '♠'), (2, '♠')],
# [(6, '♣'), ('Q', '♠'), (5, '♢'), (5, '♡'), (3, '♡'), (8, '♡'), (7, '♣')],
# [(7, '♡'), (9, '♢'), (2, '♢'), (9, '♡'), (7, '♠'), ('K', '♠')],
# ...]
where the cards are distributed "as equally as possible between all [8] players":
[len(hand) for hand in hands]
# [7, 7, 7, 7, 6, 6, 6, 6]
answered Jan 25 at 11:06
pylangpylang
14.1k24458
add a comment |
See also more_itertools.distribute, a third-party tool and its source code.
Code
Here we distributes m items into n bins, one-by-one, and count each bin.
import more_itertools as mit
def sum_distrib(m, n):
"""Return an iterable of m items distributed across n spaces."""
return [sum(x) for x in mit.distribute(n, [1]*m)]
Demo
sum_distrib(10, 4)
# [3, 3, 2, 2]
sum_distrib(7, 4)
# [2, 2, 2, 1]
sum_distrib(23, 17)
# [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Example
This idea is akin to distributing a deck of cards among players. Here is an initial game of Slapjack
import random
import itertools as it
players = 8
suits = list("♠♡♢♣")
ranks = list(range(2, 11)) + list("JQKA")
deck = list(it.product(ranks, suits))
random.shuffle(deck)
hands = [list(hand) for hand in mit.distribute(players, deck)]
hands
# [[('A', '♣'), (9, '♠'), ('K', '♣'), (7, '♢'), ('A', '♠'), (5, '♠'), (2, '♠')],
# [(6, '♣'), ('Q', '♠'), (5, '♢'), (5, '♡'), (3, '♡'), (8, '♡'), (7, '♣')],
# [(7, '♡'), (9, '♢'), (2, '♢'), (9, '♡'), (7, '♠'), ('K', '♠')],
# ...]
where the cards are distributed "as equally as possible between all [8] players":
[len(hand) for hand in hands]
# [7, 7, 7, 7, 6, 6, 6, 6]
answered Jan 25 at 11:06
pylangpylang
14.1k24458
See also more_itertools.distribute, a third-party tool and its source code.
Code
Here we distributes m items into n bins, one-by-one, and count each bin.
import more_itertools as mit
def sum_distrib(m, n):
"""Return an iterable of m items distributed across n spaces."""
return [sum(x) for x in mit.distribute(n, [1]*m)]
Demo
sum_distrib(10, 4)
# [3, 3, 2, 2]
sum_distrib(7, 4)
# [2, 2, 2, 1]
sum_distrib(23, 17)
# [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Example
This idea is akin to distributing a deck of cards among players. Here is an initial game of Slapjack
import random
import itertools as it
players = 8
suits = list("♠♡♢♣")
ranks = list(range(2, 11)) + list("JQKA")
deck = list(it.product(ranks, suits))
random.shuffle(deck)
hands = [list(hand) for hand in mit.distribute(players, deck)]
hands
# [[('A', '♣'), (9, '♠'), ('K', '♣'), (7, '♢'), ('A', '♠'), (5, '♠'), (2, '♠')],
# [(6, '♣'), ('Q', '♠'), (5, '♢'), (5, '♡'), (3, '♡'), (8, '♡'), (7, '♣')],
# [(7, '♡'), (9, '♢'), (2, '♢'), (9, '♡'), (7, '♠'), ('K', '♠')],
# ...]
where the cards are distributed "as equally as possible between all [8] players":
[len(hand) for hand in hands]
# [7, 7, 7, 7, 6, 6, 6, 6]
answered Jan 25 at 11:06
pylangpylang
14.1k24458
edited Jan 25 at 22:21
answered Jan 25 at 11:06
pylangpylang
14.1k24458
answered Jan 25 at 11:06
pylangpylang
14.1k24458
answered Jan 25 at 11:06
pylangpylang
14.1k24458
14.1k24458
add a comment |
add a comment |
Mad Physicist answer is perfect. But if you want to distribute the oranges uniformley on the plates (eg. 2 3 2 3 vs 2 2 3 3 in the 7 oranges and 4 plates example), here's an simple idea.
Easy case
Take an example with 31 oranges and 7 plates for example.
Step 1: You begin like Mad Physicist with an euclidian division: 31 = 4*7 + 3. Put 4 oranges in each plate and keep the remaining 3.
[4, 4, 4, 4, 4, 4, 4]
Step 2: Now, you have more plates than oranges, and that's quite different: you have to distribute plates among oranges. You have 7 plates and 3 oranges left: 7 = 2*3 + 1. You will have 2 plates per orange (you have a plate left, but it doesn't matter). Let's call this 2 the leap. Start at leap/2 will be pretty :
[4, 5, 4, 5, 4, 5, 4]
Not so easy case
That was the easy case. What happens with 34 oranges and 7 plates?
Step 1: You still begin like Mad Physicist with an euclidian division: 34 = 4*7 + 6. Put 4 oranges in each plate and keep the remaining 6.
[4, 4, 4, 4, 4, 4, 4]
Step 2: Now, you have 7 plates and 6 oranges left: 7 = 1*6 + 1. You will have one plate per orange. But wait.. I don't have 7 oranges! Don't be afraid, I lend you an apple:
[5, 5, 5, 5, 5, 5, 4+apple]
But if you want some uniformity, you have to place that apple elsewhere! Why not try distribute apples like oranges in the first case? 7 plates, 1 apple : 7 = 1*7 + 0. The leap is 7, start at leap/2, that is 3:
[5, 5, 5, 4+apple, 5, 5, 5]
Step 3. You owe me an apple. Please give me back my apple :
[5, 5, 5, 4, 5, 5, 5]
To summarize : if you have few oranges left, you distribute the peaks, else you distribute the valleys. (Disclaimer: I'm the author of this "algorithm" and I hope it is correct, but please correct me if I'm wrong !)
The code
Enough talk, the code:
def distribute(oranges, plates):
base, extra = divmod(oranges, plates) # extra < plates
if extra == 0:
L = [base for _ in range(plates)]
elif extra <= plates//2:
leap = plates // extra
L = [base + (i%leap == leap//2) for i in range(plates)]
else: # plates/2 < extra < plates
leap = plates // (plates-extra) # plates - extra is the number of apples I lent you
L = [base + (1 - (i%leap == leap//2)) for i in range(plates)]
return L
Some tests:
>>> distribute(oranges=28, plates=7)
[4, 4, 4, 4, 4, 4, 4]
>>> distribute(oranges=29, plates=7)
[4, 4, 4, 5, 4, 4, 4]
>>> distribute(oranges=30, plates=7)
[4, 5, 4, 4, 5, 4, 4]
>>> distribute(oranges=31, plates=7)
[4, 5, 4, 5, 4, 5, 4]
>>> distribute(oranges=32, plates=7)
[5, 4, 5, 4, 5, 4, 5]
>>> distribute(oranges=33, plates=7)
[5, 4, 5, 5, 4, 5, 5]
>>> distribute(oranges=34, plates=7)
[5, 5, 5, 4, 5, 5, 5]
>>> distribute(oranges=35, plates=7)
[5, 5, 5, 5, 5, 5, 5]
answered Jan 25 at 19:39
jferardjferard
1,794312
add a comment |
Mad Physicist answer is perfect. But if you want to distribute the oranges uniformley on the plates (eg. 2 3 2 3 vs 2 2 3 3 in the 7 oranges and 4 plates example), here's an simple idea.
Easy case
Take an example with 31 oranges and 7 plates for example.
Step 1: You begin like Mad Physicist with an euclidian division: 31 = 4*7 + 3. Put 4 oranges in each plate and keep the remaining 3.
[4, 4, 4, 4, 4, 4, 4]
Step 2: Now, you have more plates than oranges, and that's quite different: you have to distribute plates among oranges. You have 7 plates and 3 oranges left: 7 = 2*3 + 1. You will have 2 plates per orange (you have a plate left, but it doesn't matter). Let's call this 2 the leap. Start at leap/2 will be pretty :
[4, 5, 4, 5, 4, 5, 4]
Not so easy case
That was the easy case. What happens with 34 oranges and 7 plates?
Step 1: You still begin like Mad Physicist with an euclidian division: 34 = 4*7 + 6. Put 4 oranges in each plate and keep the remaining 6.
[4, 4, 4, 4, 4, 4, 4]
Step 2: Now, you have 7 plates and 6 oranges left: 7 = 1*6 + 1. You will have one plate per orange. But wait.. I don't have 7 oranges! Don't be afraid, I lend you an apple:
[5, 5, 5, 5, 5, 5, 4+apple]
But if you want some uniformity, you have to place that apple elsewhere! Why not try distribute apples like oranges in the first case? 7 plates, 1 apple : 7 = 1*7 + 0. The leap is 7, start at leap/2, that is 3:
[5, 5, 5, 4+apple, 5, 5, 5]
Step 3. You owe me an apple. Please give me back my apple :
[5, 5, 5, 4, 5, 5, 5]
To summarize : if you have few oranges left, you distribute the peaks, else you distribute the valleys. (Disclaimer: I'm the author of this "algorithm" and I hope it is correct, but please correct me if I'm wrong !)
The code
Enough talk, the code:
def distribute(oranges, plates):
base, extra = divmod(oranges, plates) # extra < plates
if extra == 0:
L = [base for _ in range(plates)]
elif extra <= plates//2:
leap = plates // extra
L = [base + (i%leap == leap//2) for i in range(plates)]
else: # plates/2 < extra < plates
leap = plates // (plates-extra) # plates - extra is the number of apples I lent you
L = [base + (1 - (i%leap == leap//2)) for i in range(plates)]
return L
Some tests:
>>> distribute(oranges=28, plates=7)
[4, 4, 4, 4, 4, 4, 4]
>>> distribute(oranges=29, plates=7)
[4, 4, 4, 5, 4, 4, 4]
>>> distribute(oranges=30, plates=7)
[4, 5, 4, 4, 5, 4, 4]
>>> distribute(oranges=31, plates=7)
[4, 5, 4, 5, 4, 5, 4]
>>> distribute(oranges=32, plates=7)
[5, 4, 5, 4, 5, 4, 5]
>>> distribute(oranges=33, plates=7)
[5, 4, 5, 5, 4, 5, 5]
>>> distribute(oranges=34, plates=7)
[5, 5, 5, 4, 5, 5, 5]
>>> distribute(oranges=35, plates=7)
[5, 5, 5, 5, 5, 5, 5]
answered Jan 25 at 19:39
jferardjferard
1,794312
add a comment |
Mad Physicist answer is perfect. But if you want to distribute the oranges uniformley on the plates (eg. 2 3 2 3 vs 2 2 3 3 in the 7 oranges and 4 plates example), here's an simple idea.
Easy case
Take an example with 31 oranges and 7 plates for example.
Step 1: You begin like Mad Physicist with an euclidian division: 31 = 4*7 + 3. Put 4 oranges in each plate and keep the remaining 3.
[4, 4, 4, 4, 4, 4, 4]
Step 2: Now, you have more plates than oranges, and that's quite different: you have to distribute plates among oranges. You have 7 plates and 3 oranges left: 7 = 2*3 + 1. You will have 2 plates per orange (you have a plate left, but it doesn't matter). Let's call this 2 the leap. Start at leap/2 will be pretty :
[4, 5, 4, 5, 4, 5, 4]
Not so easy case
That was the easy case. What happens with 34 oranges and 7 plates?
Step 1: You still begin like Mad Physicist with an euclidian division: 34 = 4*7 + 6. Put 4 oranges in each plate and keep the remaining 6.
[4, 4, 4, 4, 4, 4, 4]
Step 2: Now, you have 7 plates and 6 oranges left: 7 = 1*6 + 1. You will have one plate per orange. But wait.. I don't have 7 oranges! Don't be afraid, I lend you an apple:
[5, 5, 5, 5, 5, 5, 4+apple]
But if you want some uniformity, you have to place that apple elsewhere! Why not try distribute apples like oranges in the first case? 7 plates, 1 apple : 7 = 1*7 + 0. The leap is 7, start at leap/2, that is 3:
[5, 5, 5, 4+apple, 5, 5, 5]
Step 3. You owe me an apple. Please give me back my apple :
[5, 5, 5, 4, 5, 5, 5]
To summarize : if you have few oranges left, you distribute the peaks, else you distribute the valleys. (Disclaimer: I'm the author of this "algorithm" and I hope it is correct, but please correct me if I'm wrong !)
The code
Enough talk, the code:
def distribute(oranges, plates):
base, extra = divmod(oranges, plates) # extra < plates
if extra == 0:
L = [base for _ in range(plates)]
elif extra <= plates//2:
leap = plates // extra
L = [base + (i%leap == leap//2) for i in range(plates)]
else: # plates/2 < extra < plates
leap = plates // (plates-extra) # plates - extra is the number of apples I lent you
L = [base + (1 - (i%leap == leap//2)) for i in range(plates)]
return L
Some tests:
>>> distribute(oranges=28, plates=7)
[4, 4, 4, 4, 4, 4, 4]
>>> distribute(oranges=29, plates=7)
[4, 4, 4, 5, 4, 4, 4]
>>> distribute(oranges=30, plates=7)
[4, 5, 4, 4, 5, 4, 4]
>>> distribute(oranges=31, plates=7)
[4, 5, 4, 5, 4, 5, 4]
>>> distribute(oranges=32, plates=7)
[5, 4, 5, 4, 5, 4, 5]
>>> distribute(oranges=33, plates=7)
[5, 4, 5, 5, 4, 5, 5]
>>> distribute(oranges=34, plates=7)
[5, 5, 5, 4, 5, 5, 5]
>>> distribute(oranges=35, plates=7)
[5, 5, 5, 5, 5, 5, 5]
answered Jan 25 at 19:39
jferardjferard
1,794312
Mad Physicist answer is perfect. But if you want to distribute the oranges uniformley on the plates (eg. 2 3 2 3 vs 2 2 3 3 in the 7 oranges and 4 plates example), here's an simple idea.
Easy case
Take an example with 31 oranges and 7 plates for example.
Step 1: You begin like Mad Physicist with an euclidian division: 31 = 4*7 + 3. Put 4 oranges in each plate and keep the remaining 3.
[4, 4, 4, 4, 4, 4, 4]
Step 2: Now, you have more plates than oranges, and that's quite different: you have to distribute plates among oranges. You have 7 plates and 3 oranges left: 7 = 2*3 + 1. You will have 2 plates per orange (you have a plate left, but it doesn't matter). Let's call this 2 the leap. Start at leap/2 will be pretty :
[4, 5, 4, 5, 4, 5, 4]
Not so easy case
That was the easy case. What happens with 34 oranges and 7 plates?
Step 1: You still begin like Mad Physicist with an euclidian division: 34 = 4*7 + 6. Put 4 oranges in each plate and keep the remaining 6.
[4, 4, 4, 4, 4, 4, 4]
Step 2: Now, you have 7 plates and 6 oranges left: 7 = 1*6 + 1. You will have one plate per orange. But wait.. I don't have 7 oranges! Don't be afraid, I lend you an apple:
[5, 5, 5, 5, 5, 5, 4+apple]
But if you want some uniformity, you have to place that apple elsewhere! Why not try distribute apples like oranges in the first case? 7 plates, 1 apple : 7 = 1*7 + 0. The leap is 7, start at leap/2, that is 3:
[5, 5, 5, 4+apple, 5, 5, 5]
Step 3. You owe me an apple. Please give me back my apple :
[5, 5, 5, 4, 5, 5, 5]
To summarize : if you have few oranges left, you distribute the peaks, else you distribute the valleys. (Disclaimer: I'm the author of this "algorithm" and I hope it is correct, but please correct me if I'm wrong !)
The code
Enough talk, the code:
def distribute(oranges, plates):
base, extra = divmod(oranges, plates) # extra < plates
if extra == 0:
L = [base for _ in range(plates)]
elif extra <= plates//2:
leap = plates // extra
L = [base + (i%leap == leap//2) for i in range(plates)]
else: # plates/2 < extra < plates
leap = plates // (plates-extra) # plates - extra is the number of apples I lent you
L = [base + (1 - (i%leap == leap//2)) for i in range(plates)]
return L
Some tests:
>>> distribute(oranges=28, plates=7)
[4, 4, 4, 4, 4, 4, 4]
>>> distribute(oranges=29, plates=7)
[4, 4, 4, 5, 4, 4, 4]
>>> distribute(oranges=30, plates=7)
[4, 5, 4, 4, 5, 4, 4]
>>> distribute(oranges=31, plates=7)
[4, 5, 4, 5, 4, 5, 4]
>>> distribute(oranges=32, plates=7)
[5, 4, 5, 4, 5, 4, 5]
>>> distribute(oranges=33, plates=7)
[5, 4, 5, 5, 4, 5, 5]
>>> distribute(oranges=34, plates=7)
[5, 5, 5, 4, 5, 5, 5]
>>> distribute(oranges=35, plates=7)
[5, 5, 5, 5, 5, 5, 5]
answered Jan 25 at 19:39
jferardjferard
1,794312
edited Jan 26 at 16:24
answered Jan 25 at 19:39
jferardjferard
1,794312
answered Jan 25 at 19:39
jferardjferard
1,794312
answered Jan 25 at 19:39
jferardjferard
1,794312
1,794312
add a comment |
add a comment |
Not sure how this works. But it returns the exact same results
a = 23
b = 17
s = pd.Series(pd.cut(mylist, b), index=mylist)
s.groupby(s).size().values
answered Feb 3 at 8:20
shantanuoshantanuo
11.9k58155263
add a comment |
Not sure how this works. But it returns the exact same results
a = 23
b = 17
s = pd.Series(pd.cut(mylist, b), index=mylist)
s.groupby(s).size().values
answered Feb 3 at 8:20
shantanuoshantanuo
11.9k58155263
add a comment |
Not sure how this works. But it returns the exact same results
a = 23
b = 17
s = pd.Series(pd.cut(mylist, b), index=mylist)
s.groupby(s).size().values
answered Feb 3 at 8:20
shantanuoshantanuo
11.9k58155263
Not sure how this works. But it returns the exact same results
a = 23
b = 17
s = pd.Series(pd.cut(mylist, b), index=mylist)
s.groupby(s).size().values
answered Feb 3 at 8:20
shantanuoshantanuo
11.9k58155263
answered Feb 3 at 8:20
shantanuoshantanuo
11.9k58155263
answered Feb 3 at 8:20
shantanuoshantanuo
11.9k58155263
answered Feb 3 at 8:20
shantanuoshantanuo
11.9k58155263
11.9k58155263
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54353083%2fdistribute-an-integer-amount-by-a-set-of-slots-as-evenly-as-possible%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
