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 Jan 24 at 23:41
John Kugelman
242k53403456
242k53403456
asked Jan 24 at 18:19
fmagnofmagno
1538
1538
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]
5
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
Jan 25 at 3:57
Very elegant indeed!
– fmagno
Jan 25 at 13:53
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
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
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]
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]
5
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
Jan 25 at 3:57
Very elegant indeed!
– fmagno
Jan 25 at 13:53
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]
5
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
Jan 25 at 3:57
Very elegant indeed!
– fmagno
Jan 25 at 13:53
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]
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]
edited Jan 25 at 14:31
fmagno
1538
1538
answered Jan 24 at 19:59
marsipanmarsipan
1346
1346
5
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
Jan 25 at 3:57
Very elegant indeed!
– fmagno
Jan 25 at 13:53
add a comment |
5
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
Jan 25 at 3:57
Very elegant indeed!
– fmagno
Jan 25 at 13:53
5
5
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
Jan 25 at 3:57
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
Jan 25 at 3:57
Very elegant indeed!
– fmagno
Jan 25 at 13:53
Very elegant indeed!
– fmagno
Jan 25 at 13:53
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
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]
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]
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 Jan 24 at 18:31
answered Jan 24 at 18:26
Mad PhysicistMad Physicist
36.4k1671101
36.4k1671101
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
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
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
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
36.4k1671101
36.4k1671101
answered Jan 24 at 18:34
LSerniLSerni
41.1k64681
41.1k64681
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]
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 Jan 25 at 22:21
answered Jan 25 at 11:06
pylangpylang
13.4k23953
13.4k23953
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 Jan 26 at 16:24
answered Jan 25 at 19:39
jferardjferard
1,559311
1,559311
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