Distribute an integer amount by a set of slots as evenly as possible












19















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]









share|improve this question





























    19















    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]









    share|improve this question



























      19












      19








      19


      5






      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]









      share|improve this question
















      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






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Jan 24 at 23:41









      John Kugelman

      242k53403456




      242k53403456










      asked Jan 24 at 18:19









      fmagnofmagno

      1538




      1538
























          5 Answers
          5






          active

          oldest

          votes


















          11














          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]





          share|improve this answer





















          • 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



















          36














          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]





          share|improve this answer





















          • 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



















          13














          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





          share|improve this answer


























          • 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



















          3














          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]





          share|improve this answer

































            2














            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]





            share|improve this answer

























              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
              });


              }
              });














              draft saved

              draft discarded


















              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









              11














              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]





              share|improve this answer





















              • 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
















              11














              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]





              share|improve this answer





















              • 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














              11












              11








              11







              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]





              share|improve this answer















              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]






              share|improve this answer














              share|improve this answer



              share|improve this answer








              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














              • 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













              36














              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]





              share|improve this answer





















              • 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
















              36














              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]





              share|improve this answer





















              • 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














              36












              36








              36







              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]





              share|improve this answer















              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]






              share|improve this answer














              share|improve this answer



              share|improve this answer








              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














              • 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











              13














              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





              share|improve this answer


























              • 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
















              13














              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





              share|improve this answer


























              • 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














              13












              13








              13







              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





              share|improve this answer















              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






              share|improve this answer














              share|improve this answer



              share|improve this answer








              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



















              • 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











              3














              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]





              share|improve this answer






























                3














                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]





                share|improve this answer




























                  3












                  3








                  3







                  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]





                  share|improve this answer















                  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]






                  share|improve this answer














                  share|improve this answer



                  share|improve this answer








                  edited Jan 25 at 22:21

























                  answered Jan 25 at 11:06









                  pylangpylang

                  13.4k23953




                  13.4k23953























                      2














                      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]





                      share|improve this answer






























                        2














                        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]





                        share|improve this answer




























                          2












                          2








                          2







                          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]





                          share|improve this answer















                          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]






                          share|improve this answer














                          share|improve this answer



                          share|improve this answer








                          edited Jan 26 at 16:24

























                          answered Jan 25 at 19:39









                          jferardjferard

                          1,559311




                          1,559311






























                              draft saved

                              draft discarded




















































                              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.




                              draft saved


                              draft discarded














                              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





















































                              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







                              Popular posts from this blog

                              mysqli_query(): Empty query in /home/lucindabrummitt/public_html/blog/wp-includes/wp-db.php on line 1924

                              How to change which sound is reproduced for terminal bell?

                              Can I use Tabulator js library in my java Spring + Thymeleaf project?