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
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
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
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 2 days ago
John Kugelman
241k53401455
241k53401455
asked 2 days ago
fmagnofmagno
1317
1317
add a comment |
add a comment |
5 Answers
5
active
oldest
votes
If a is your number and b the number of slots, you can use the following list comprehension:
[(a//b) + (i < (a % b)) for i in range(b)]
example:
>>> a = 23
>>> b = 17
>>> [(a//b) + (i < (a % b)) for i in range(b)]
[2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
New contributor
4
Besides renaming the variables and using the operators manually, this is identical to my solution. So in good faith, I have to give you a +1 :)
– Mad Physicist
2 days ago
Very elegant indeed!
– fmagno
yesterday
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]
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
2 days ago
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
2 days ago
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
yesterday
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
For a more clearly specified problem, this would be the better answer.
– Mad Physicist
2 days ago
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
2 days ago
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
2 days ago
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]
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]
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
If a is your number and b the number of slots, you can use the following list comprehension:
[(a//b) + (i < (a % b)) for i in range(b)]
example:
>>> a = 23
>>> b = 17
>>> [(a//b) + (i < (a % b)) for i in range(b)]
[2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
New contributor
4
Besides renaming the variables and using the operators manually, this is identical to my solution. So in good faith, I have to give you a +1 :)
– Mad Physicist
2 days ago
Very elegant indeed!
– fmagno
yesterday
add a comment |
If a is your number and b the number of slots, you can use the following list comprehension:
[(a//b) + (i < (a % b)) for i in range(b)]
example:
>>> a = 23
>>> b = 17
>>> [(a//b) + (i < (a % b)) for i in range(b)]
[2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
New contributor
4
Besides renaming the variables and using the operators manually, this is identical to my solution. So in good faith, I have to give you a +1 :)
– Mad Physicist
2 days ago
Very elegant indeed!
– fmagno
yesterday
add a comment |
If a is your number and b the number of slots, you can use the following list comprehension:
[(a//b) + (i < (a % b)) for i in range(b)]
example:
>>> a = 23
>>> b = 17
>>> [(a//b) + (i < (a % b)) for i in range(b)]
[2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
New contributor
If a is your number and b the number of slots, you can use the following list comprehension:
[(a//b) + (i < (a % b)) for i in range(b)]
example:
>>> a = 23
>>> b = 17
>>> [(a//b) + (i < (a % b)) for i in range(b)]
[2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
New contributor
edited yesterday
fmagno
1317
1317
New contributor
answered 2 days ago
marsipanmarsipan
1065
1065
New contributor
New contributor
4
Besides renaming the variables and using the operators manually, this is identical to my solution. So in good faith, I have to give you a +1 :)
– Mad Physicist
2 days ago
Very elegant indeed!
– fmagno
yesterday
add a comment |
4
Besides renaming the variables and using the operators manually, this is identical to my solution. So in good faith, I have to give you a +1 :)
– Mad Physicist
2 days ago
Very elegant indeed!
– fmagno
yesterday
4
4
Besides renaming the variables and using the operators manually, this is identical to my solution. So in good faith, I have to give you a +1 :)
– Mad Physicist
2 days ago
Besides renaming the variables and using the operators manually, this is identical to my solution. So in good faith, I have to give you a +1 :)
– Mad Physicist
2 days ago
Very elegant indeed!
– fmagno
yesterday
Very elegant indeed!
– fmagno
yesterday
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]
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
2 days ago
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
2 days ago
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
yesterday
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]
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
2 days ago
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
2 days ago
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
yesterday
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]
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]
edited 2 days ago
answered 2 days ago
Mad PhysicistMad Physicist
36k1571100
36k1571100
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
2 days ago
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
2 days ago
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
yesterday
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
2 days ago
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
2 days ago
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
yesterday
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
2 days ago
@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
2 days ago
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
2 days ago
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
2 days ago
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
yesterday
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
yesterday
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
For a more clearly specified problem, this would be the better answer.
– Mad Physicist
2 days ago
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
2 days ago
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
2 days ago
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
For a more clearly specified problem, this would be the better answer.
– Mad Physicist
2 days ago
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
2 days ago
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
2 days ago
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
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 2 days ago
Mad Physicist
36k1571100
36k1571100
answered 2 days ago
LSerniLSerni
41k64681
41k64681
For a more clearly specified problem, this would be the better answer.
– Mad Physicist
2 days ago
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
2 days ago
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
2 days ago
add a comment |
For a more clearly specified problem, this would be the better answer.
– Mad Physicist
2 days ago
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
2 days ago
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
2 days ago
For a more clearly specified problem, this would be the better answer.
– Mad Physicist
2 days ago
For a more clearly specified problem, this would be the better answer.
– Mad Physicist
2 days ago
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
2 days ago
Mad Physicist: not sure I agree with you. Elegance is a bit subjective criterion, but for a layman this is not as elegant :)
– gmagno
2 days ago
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
2 days ago
@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
2 days ago
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]
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]
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]
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]
edited yesterday
answered yesterday
pylangpylang
13.3k23853
13.3k23853
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]
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]
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]
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]
edited 13 hours ago
answered yesterday
jferardjferard
1,534311
1,534311
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