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












15















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





























    15















    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



























      15












      15








      15


      4






      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 2 days ago









      John Kugelman

      241k53401455




      241k53401455










      asked 2 days ago









      fmagnofmagno

      1317




      1317
























          5 Answers
          5






          active

          oldest

          votes


















          9














          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










          New contributor




          marsipan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
          Check out our Code of Conduct.
















          • 4





            Besides renaming the variables and using the operators manually, this is identical to my solution. So in good faith, I have to give you a +1 :)

            – Mad Physicist
            2 days ago











          • Very elegant indeed!

            – fmagno
            yesterday



















          32














          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
            2 days ago






          • 1





            While I agree that the distribution of the remainder could be improved from "shoved to the left", OP does nothing to lead me to believe that that's something they want.

            – Mad Physicist
            2 days ago











          • Actually the OP's second example indicates that your solution - apart from simplicity - is the one yielding the expected results (hadn't noticed it before).

            – LSerni
            yesterday



















          10














          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
            2 days ago








          • 1





            Mad Physicist: not sure I agree with you. Elegance is a bit subjective criterion, but for a layman this is not as elegant :)

            – gmagno
            2 days ago






          • 3





            @gmagno. It's not just about elegance. This solution actually distributes the bins differently than mine. If there was an additional requirement to maintain as uniform a distribution across the peaks as possible, mine wouldn't cut it at all. But yes, this is more cumbersome and I'm guessing OP wanted the beginner version.

            – Mad Physicist
            2 days ago



















          2














          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

































            0














            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









              9














              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










              New contributor




              marsipan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.
















              • 4





                Besides renaming the variables and using the operators manually, this is identical to my solution. So in good faith, I have to give you a +1 :)

                – Mad Physicist
                2 days ago











              • Very elegant indeed!

                – fmagno
                yesterday
















              9














              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










              New contributor




              marsipan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.
















              • 4





                Besides renaming the variables and using the operators manually, this is identical to my solution. So in good faith, I have to give you a +1 :)

                – Mad Physicist
                2 days ago











              • Very elegant indeed!

                – fmagno
                yesterday














              9












              9








              9







              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










              New contributor




              marsipan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.










              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










              New contributor




              marsipan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.









              share|improve this answer



              share|improve this answer








              edited yesterday









              fmagno

              1317




              1317






              New contributor




              marsipan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.









              answered 2 days ago









              marsipanmarsipan

              1065




              1065




              New contributor




              marsipan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.





              New contributor





              marsipan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.






              marsipan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.








              • 4





                Besides renaming the variables and using the operators manually, this is identical to my solution. So in good faith, I have to give you a +1 :)

                – Mad Physicist
                2 days ago











              • Very elegant indeed!

                – fmagno
                yesterday














              • 4





                Besides renaming the variables and using the operators manually, this is identical to my solution. So in good faith, I have to give you a +1 :)

                – Mad Physicist
                2 days ago











              • Very elegant indeed!

                – fmagno
                yesterday








              4




              4





              Besides renaming the variables and using the operators manually, this is identical to my solution. So in good faith, I have to give you a +1 :)

              – Mad Physicist
              2 days ago





              Besides renaming the variables and using the operators manually, this is identical to my solution. So in good faith, I have to give you a +1 :)

              – Mad Physicist
              2 days ago













              Very elegant indeed!

              – fmagno
              yesterday





              Very elegant indeed!

              – fmagno
              yesterday













              32














              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
                2 days ago






              • 1





                While I agree that the distribution of the remainder could be improved from "shoved to the left", OP does nothing to lead me to believe that that's something they want.

                – Mad Physicist
                2 days ago











              • Actually the OP's second example indicates that your solution - apart from simplicity - is the one yielding the expected results (hadn't noticed it before).

                – LSerni
                yesterday
















              32














              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
                2 days ago






              • 1





                While I agree that the distribution of the remainder could be improved from "shoved to the left", OP does nothing to lead me to believe that that's something they want.

                – Mad Physicist
                2 days ago











              • Actually the OP's second example indicates that your solution - apart from simplicity - is the one yielding the expected results (hadn't noticed it before).

                – LSerni
                yesterday














              32












              32








              32







              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 2 days ago

























              answered 2 days ago









              Mad PhysicistMad Physicist

              36k1571100




              36k1571100








              • 3





                @Lserni. This method guarantees that the difference between the maximum and minimum plate is at most 1. What additional criteria did you have for evenness?

                – Mad Physicist
                2 days ago






              • 1





                While I agree that the distribution of the remainder could be improved from "shoved to the left", OP does nothing to lead me to believe that that's something they want.

                – Mad Physicist
                2 days ago











              • Actually the OP's second example indicates that your solution - apart from simplicity - is the one yielding the expected results (hadn't noticed it before).

                – LSerni
                yesterday














              • 3





                @Lserni. This method guarantees that the difference between the maximum and minimum plate is at most 1. What additional criteria did you have for evenness?

                – Mad Physicist
                2 days ago






              • 1





                While I agree that the distribution of the remainder could be improved from "shoved to the left", OP does nothing to lead me to believe that that's something they want.

                – Mad Physicist
                2 days ago











              • Actually the OP's second example indicates that your solution - apart from simplicity - is the one yielding the expected results (hadn't noticed it before).

                – LSerni
                yesterday








              3




              3





              @Lserni. This method guarantees that the difference between the maximum and minimum plate is at most 1. What additional criteria did you have for evenness?

              – Mad Physicist
              2 days ago





              @Lserni. This method guarantees that the difference between the maximum and minimum plate is at most 1. What additional criteria did you have for evenness?

              – Mad Physicist
              2 days ago




              1




              1





              While I agree that the distribution of the remainder could be improved from "shoved to the left", OP does nothing to lead me to believe that that's something they want.

              – Mad Physicist
              2 days ago





              While I agree that the distribution of the remainder could be improved from "shoved to the left", OP does nothing to lead me to believe that that's something they want.

              – Mad Physicist
              2 days ago













              Actually the OP's second example indicates that your solution - apart from simplicity - is the one yielding the expected results (hadn't noticed it before).

              – LSerni
              yesterday





              Actually the OP's second example indicates that your solution - apart from simplicity - is the one yielding the expected results (hadn't noticed it before).

              – LSerni
              yesterday











              10














              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
                2 days ago








              • 1





                Mad Physicist: not sure I agree with you. Elegance is a bit subjective criterion, but for a layman this is not as elegant :)

                – gmagno
                2 days ago






              • 3





                @gmagno. It's not just about elegance. This solution actually distributes the bins differently than mine. If there was an additional requirement to maintain as uniform a distribution across the peaks as possible, mine wouldn't cut it at all. But yes, this is more cumbersome and I'm guessing OP wanted the beginner version.

                – Mad Physicist
                2 days ago
















              10














              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
                2 days ago








              • 1





                Mad Physicist: not sure I agree with you. Elegance is a bit subjective criterion, but for a layman this is not as elegant :)

                – gmagno
                2 days ago






              • 3





                @gmagno. It's not just about elegance. This solution actually distributes the bins differently than mine. If there was an additional requirement to maintain as uniform a distribution across the peaks as possible, mine wouldn't cut it at all. But yes, this is more cumbersome and I'm guessing OP wanted the beginner version.

                – Mad Physicist
                2 days ago














              10












              10








              10







              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 2 days ago









              Mad Physicist

              36k1571100




              36k1571100










              answered 2 days ago









              LSerniLSerni

              41k64681




              41k64681













              • For a more clearly specified problem, this would be the better answer.

                – Mad Physicist
                2 days ago








              • 1





                Mad Physicist: not sure I agree with you. Elegance is a bit subjective criterion, but for a layman this is not as elegant :)

                – gmagno
                2 days ago






              • 3





                @gmagno. It's not just about elegance. This solution actually distributes the bins differently than mine. If there was an additional requirement to maintain as uniform a distribution across the peaks as possible, mine wouldn't cut it at all. But yes, this is more cumbersome and I'm guessing OP wanted the beginner version.

                – Mad Physicist
                2 days ago



















              • For a more clearly specified problem, this would be the better answer.

                – Mad Physicist
                2 days ago








              • 1





                Mad Physicist: not sure I agree with you. Elegance is a bit subjective criterion, but for a layman this is not as elegant :)

                – gmagno
                2 days ago






              • 3





                @gmagno. It's not just about elegance. This solution actually distributes the bins differently than mine. If there was an additional requirement to maintain as uniform a distribution across the peaks as possible, mine wouldn't cut it at all. But yes, this is more cumbersome and I'm guessing OP wanted the beginner version.

                – Mad Physicist
                2 days ago

















              For a more clearly specified problem, this would be the better answer.

              – Mad Physicist
              2 days ago







              For a more clearly specified problem, this would be the better answer.

              – Mad Physicist
              2 days ago






              1




              1





              Mad Physicist: not sure I agree with you. Elegance is a bit subjective criterion, but for a layman this is not as elegant :)

              – gmagno
              2 days ago





              Mad Physicist: not sure I agree with you. Elegance is a bit subjective criterion, but for a layman this is not as elegant :)

              – gmagno
              2 days ago




              3




              3





              @gmagno. It's not just about elegance. This solution actually distributes the bins differently than mine. If there was an additional requirement to maintain as uniform a distribution across the peaks as possible, mine wouldn't cut it at all. But yes, this is more cumbersome and I'm guessing OP wanted the beginner version.

              – Mad Physicist
              2 days ago





              @gmagno. It's not just about elegance. This solution actually distributes the bins differently than mine. If there was an additional requirement to maintain as uniform a distribution across the peaks as possible, mine wouldn't cut it at all. But yes, this is more cumbersome and I'm guessing OP wanted the beginner version.

              – Mad Physicist
              2 days ago











              2














              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














                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












                  2








                  2







                  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 yesterday

























                  answered yesterday









                  pylangpylang

                  13.3k23853




                  13.3k23853























                      0














                      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






























                        0














                        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




























                          0












                          0








                          0







                          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 13 hours ago

























                          answered yesterday









                          jferardjferard

                          1,534311




                          1,534311






























                              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

                              "Incorrect syntax near the keyword 'ON'. (on update cascade, on delete cascade,)

                              Alcedinidae

                              Origin of the phrase “under your belt”?