Python number line cluster exercisePython sequence cluster exerciseCalling an external command in PythonWhat are metaclasses in Python?Finding the index of an item given a list containing it in PythonDifference between append vs. extend list methods in PythonHow can I safely create a nested directory in Python?Does Python have a ternary conditional operator?How do I get the number of elements in a list in Python?How to read a file line-by-line into a list?Does Python have a string 'contains' substring method?Catch multiple exceptions in one line (except block)

Smoothness of finite-dimensional functional calculus

Theorems that impeded progress

What typically incentivizes a professor to change jobs to a lower ranking university?

How much RAM could one put in a typical 80386 setup?

How do we improve the relationship with a client software team that performs poorly and is becoming less collaborative?

Modeling an IPv4 Address

What's the point of deactivating Num Lock on login screens?

Prove that NP is closed under karp reduction?

Why does Kotter return in Welcome Back Kotter?

Why don't electron-positron collisions release infinite energy?

Why doesn't H₄O²⁺ exist?

How could an uplifted falcon's brain work?

Show that if two triangles built on parallel lines, with equal bases have the same perimeter only if they are congruent.

How does strength of boric acid solution increase in presence of salicylic acid?

Email Account under attack (really) - anything I can do?

Do I have a twin with permutated remainders?

What does it mean to describe someone as a butt steak?

Why are electrically insulating heatsinks so rare? Is it just cost?

Approximately how much travel time was saved by the opening of the Suez Canal in 1869?

What are these boxed doors outside store fronts in New York?

Mathematical cryptic clues

Dragon forelimb placement

Did Shadowfax go to Valinor?

Which models of the Boeing 737 are still in production?



Python number line cluster exercise


Python sequence cluster exerciseCalling an external command in PythonWhat are metaclasses in Python?Finding the index of an item given a list containing it in PythonDifference between append vs. extend list methods in PythonHow can I safely create a nested directory in Python?Does Python have a ternary conditional operator?How do I get the number of elements in a list in Python?How to read a file line-by-line into a list?Does Python have a string 'contains' substring method?Catch multiple exceptions in one line (except block)






.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;








1















I am working through an exercise in my textbook (Ex 4.7) and am implementing the code in Python to practice dynamic programming. I am having some trouble actually executing Algorithm 4.8. I understand what is going on until I get to 'Otherwise range s from 1 to t-1 and set s to minimize f(s). Why is the book using s in the for loop as well as setting it to the function f(s)? How should one go about implementing that line in Python?



[current code at bottom]



enter image description here



enter image description here



enter image description here



My current code is this so far:



x = [1,2,5,6,10]
k = 3
n = 5

r = [[0 for x in range(k)] for x in range(n)]
c = [[0 for x in range(k)] for x in range(n)]

def Union(lst1, lst2):
final_list = lst1 + lst2
return final_list

for j in range(k):
for t in range(n):
if j == 0:
r[t][j] = (x[t]-x[0])/2
c[t][j] = [(x[t]+x[0])/2]
else:
for s in range(t-1):
f = max(r[s][j-1], (x[t]-x[s+1])/2)
#set s to minimize f??
r[t][j] = f
w = []
w.append((x[t]+x[s+1])/2)
if c[s][j-1] == 0:
c[t][j] = w
else:
c[t][j] = Union(c[s][j - 1], w)

print(r)
print(c)


Any help is much appreciated!










share|improve this question






























    1















    I am working through an exercise in my textbook (Ex 4.7) and am implementing the code in Python to practice dynamic programming. I am having some trouble actually executing Algorithm 4.8. I understand what is going on until I get to 'Otherwise range s from 1 to t-1 and set s to minimize f(s). Why is the book using s in the for loop as well as setting it to the function f(s)? How should one go about implementing that line in Python?



    [current code at bottom]



    enter image description here



    enter image description here



    enter image description here



    My current code is this so far:



    x = [1,2,5,6,10]
    k = 3
    n = 5

    r = [[0 for x in range(k)] for x in range(n)]
    c = [[0 for x in range(k)] for x in range(n)]

    def Union(lst1, lst2):
    final_list = lst1 + lst2
    return final_list

    for j in range(k):
    for t in range(n):
    if j == 0:
    r[t][j] = (x[t]-x[0])/2
    c[t][j] = [(x[t]+x[0])/2]
    else:
    for s in range(t-1):
    f = max(r[s][j-1], (x[t]-x[s+1])/2)
    #set s to minimize f??
    r[t][j] = f
    w = []
    w.append((x[t]+x[s+1])/2)
    if c[s][j-1] == 0:
    c[t][j] = w
    else:
    c[t][j] = Union(c[s][j - 1], w)

    print(r)
    print(c)


    Any help is much appreciated!










    share|improve this question


























      1












      1








      1


      0






      I am working through an exercise in my textbook (Ex 4.7) and am implementing the code in Python to practice dynamic programming. I am having some trouble actually executing Algorithm 4.8. I understand what is going on until I get to 'Otherwise range s from 1 to t-1 and set s to minimize f(s). Why is the book using s in the for loop as well as setting it to the function f(s)? How should one go about implementing that line in Python?



      [current code at bottom]



      enter image description here



      enter image description here



      enter image description here



      My current code is this so far:



      x = [1,2,5,6,10]
      k = 3
      n = 5

      r = [[0 for x in range(k)] for x in range(n)]
      c = [[0 for x in range(k)] for x in range(n)]

      def Union(lst1, lst2):
      final_list = lst1 + lst2
      return final_list

      for j in range(k):
      for t in range(n):
      if j == 0:
      r[t][j] = (x[t]-x[0])/2
      c[t][j] = [(x[t]+x[0])/2]
      else:
      for s in range(t-1):
      f = max(r[s][j-1], (x[t]-x[s+1])/2)
      #set s to minimize f??
      r[t][j] = f
      w = []
      w.append((x[t]+x[s+1])/2)
      if c[s][j-1] == 0:
      c[t][j] = w
      else:
      c[t][j] = Union(c[s][j - 1], w)

      print(r)
      print(c)


      Any help is much appreciated!










      share|improve this question
















      I am working through an exercise in my textbook (Ex 4.7) and am implementing the code in Python to practice dynamic programming. I am having some trouble actually executing Algorithm 4.8. I understand what is going on until I get to 'Otherwise range s from 1 to t-1 and set s to minimize f(s). Why is the book using s in the for loop as well as setting it to the function f(s)? How should one go about implementing that line in Python?



      [current code at bottom]



      enter image description here



      enter image description here



      enter image description here



      My current code is this so far:



      x = [1,2,5,6,10]
      k = 3
      n = 5

      r = [[0 for x in range(k)] for x in range(n)]
      c = [[0 for x in range(k)] for x in range(n)]

      def Union(lst1, lst2):
      final_list = lst1 + lst2
      return final_list

      for j in range(k):
      for t in range(n):
      if j == 0:
      r[t][j] = (x[t]-x[0])/2
      c[t][j] = [(x[t]+x[0])/2]
      else:
      for s in range(t-1):
      f = max(r[s][j-1], (x[t]-x[s+1])/2)
      #set s to minimize f??
      r[t][j] = f
      w = []
      w.append((x[t]+x[s+1])/2)
      if c[s][j-1] == 0:
      c[t][j] = w
      else:
      c[t][j] = Union(c[s][j - 1], w)

      print(r)
      print(c)


      Any help is much appreciated!







      python algorithm cluster-analysis dynamic-programming






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Mar 9 at 3:26

























      asked Mar 9 at 2:43







      user10322040





























          1 Answer
          1






          active

          oldest

          votes


















          1














          The algorithm is very good. My code is as follow.



          x = [1,2,5,6,10]
          k = 3
          n = 5

          r = [[[] for _ in range(k)] for _ in range(n)]
          c = [[[] for _ in range(k)] for _ in range(n)]


          def f(s, j_down, t):
          return max(r[s][j_down], (x[t]-x[s+1])/2.)

          def get_min_f_and_s(j_down, t):
          """ range s from 1 to t-1 and set s to minimize f(s)
          for example t=5 and j=3, so s range from 1 to 4, if f(1)=0.5, f(2)=0.4, f(3)=0.1, f(4)= 1.0, so f(4) is min one and s=2.
          And r[5][j] = f(2).
          """
          items = [(s, f(s, j_down, t))for s in range(t)]
          s, min_f = min(items, key=lambda x:x[1])
          return s, min_f

          for j in range(k):
          if j == 0:
          for t in range(n):
          for t in range(n):
          r[t][j] = (x[t]-x[0])/2.0
          c[t][j] = [(x[t]+x[0])/2.0]
          else:
          for t in range(1, n):
          s, min_f = get_min_f_and_s(j-1, t)
          r[t][j] = min_f

          c[t][j] = c[s][j-1] + [(x[t]+x[s+1])/2.,]

          print(r[-1][-1])
          print(c[-1][-1])


          A advice :
          When don't understand algorithm, you can run it by hand in scratch paper, maybe you will figure out how it work.






          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%2f55073517%2fpython-number-line-cluster-exercise%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown
























            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            1














            The algorithm is very good. My code is as follow.



            x = [1,2,5,6,10]
            k = 3
            n = 5

            r = [[[] for _ in range(k)] for _ in range(n)]
            c = [[[] for _ in range(k)] for _ in range(n)]


            def f(s, j_down, t):
            return max(r[s][j_down], (x[t]-x[s+1])/2.)

            def get_min_f_and_s(j_down, t):
            """ range s from 1 to t-1 and set s to minimize f(s)
            for example t=5 and j=3, so s range from 1 to 4, if f(1)=0.5, f(2)=0.4, f(3)=0.1, f(4)= 1.0, so f(4) is min one and s=2.
            And r[5][j] = f(2).
            """
            items = [(s, f(s, j_down, t))for s in range(t)]
            s, min_f = min(items, key=lambda x:x[1])
            return s, min_f

            for j in range(k):
            if j == 0:
            for t in range(n):
            for t in range(n):
            r[t][j] = (x[t]-x[0])/2.0
            c[t][j] = [(x[t]+x[0])/2.0]
            else:
            for t in range(1, n):
            s, min_f = get_min_f_and_s(j-1, t)
            r[t][j] = min_f

            c[t][j] = c[s][j-1] + [(x[t]+x[s+1])/2.,]

            print(r[-1][-1])
            print(c[-1][-1])


            A advice :
            When don't understand algorithm, you can run it by hand in scratch paper, maybe you will figure out how it work.






            share|improve this answer





























              1














              The algorithm is very good. My code is as follow.



              x = [1,2,5,6,10]
              k = 3
              n = 5

              r = [[[] for _ in range(k)] for _ in range(n)]
              c = [[[] for _ in range(k)] for _ in range(n)]


              def f(s, j_down, t):
              return max(r[s][j_down], (x[t]-x[s+1])/2.)

              def get_min_f_and_s(j_down, t):
              """ range s from 1 to t-1 and set s to minimize f(s)
              for example t=5 and j=3, so s range from 1 to 4, if f(1)=0.5, f(2)=0.4, f(3)=0.1, f(4)= 1.0, so f(4) is min one and s=2.
              And r[5][j] = f(2).
              """
              items = [(s, f(s, j_down, t))for s in range(t)]
              s, min_f = min(items, key=lambda x:x[1])
              return s, min_f

              for j in range(k):
              if j == 0:
              for t in range(n):
              for t in range(n):
              r[t][j] = (x[t]-x[0])/2.0
              c[t][j] = [(x[t]+x[0])/2.0]
              else:
              for t in range(1, n):
              s, min_f = get_min_f_and_s(j-1, t)
              r[t][j] = min_f

              c[t][j] = c[s][j-1] + [(x[t]+x[s+1])/2.,]

              print(r[-1][-1])
              print(c[-1][-1])


              A advice :
              When don't understand algorithm, you can run it by hand in scratch paper, maybe you will figure out how it work.






              share|improve this answer



























                1












                1








                1







                The algorithm is very good. My code is as follow.



                x = [1,2,5,6,10]
                k = 3
                n = 5

                r = [[[] for _ in range(k)] for _ in range(n)]
                c = [[[] for _ in range(k)] for _ in range(n)]


                def f(s, j_down, t):
                return max(r[s][j_down], (x[t]-x[s+1])/2.)

                def get_min_f_and_s(j_down, t):
                """ range s from 1 to t-1 and set s to minimize f(s)
                for example t=5 and j=3, so s range from 1 to 4, if f(1)=0.5, f(2)=0.4, f(3)=0.1, f(4)= 1.0, so f(4) is min one and s=2.
                And r[5][j] = f(2).
                """
                items = [(s, f(s, j_down, t))for s in range(t)]
                s, min_f = min(items, key=lambda x:x[1])
                return s, min_f

                for j in range(k):
                if j == 0:
                for t in range(n):
                for t in range(n):
                r[t][j] = (x[t]-x[0])/2.0
                c[t][j] = [(x[t]+x[0])/2.0]
                else:
                for t in range(1, n):
                s, min_f = get_min_f_and_s(j-1, t)
                r[t][j] = min_f

                c[t][j] = c[s][j-1] + [(x[t]+x[s+1])/2.,]

                print(r[-1][-1])
                print(c[-1][-1])


                A advice :
                When don't understand algorithm, you can run it by hand in scratch paper, maybe you will figure out how it work.






                share|improve this answer















                The algorithm is very good. My code is as follow.



                x = [1,2,5,6,10]
                k = 3
                n = 5

                r = [[[] for _ in range(k)] for _ in range(n)]
                c = [[[] for _ in range(k)] for _ in range(n)]


                def f(s, j_down, t):
                return max(r[s][j_down], (x[t]-x[s+1])/2.)

                def get_min_f_and_s(j_down, t):
                """ range s from 1 to t-1 and set s to minimize f(s)
                for example t=5 and j=3, so s range from 1 to 4, if f(1)=0.5, f(2)=0.4, f(3)=0.1, f(4)= 1.0, so f(4) is min one and s=2.
                And r[5][j] = f(2).
                """
                items = [(s, f(s, j_down, t))for s in range(t)]
                s, min_f = min(items, key=lambda x:x[1])
                return s, min_f

                for j in range(k):
                if j == 0:
                for t in range(n):
                for t in range(n):
                r[t][j] = (x[t]-x[0])/2.0
                c[t][j] = [(x[t]+x[0])/2.0]
                else:
                for t in range(1, n):
                s, min_f = get_min_f_and_s(j-1, t)
                r[t][j] = min_f

                c[t][j] = c[s][j-1] + [(x[t]+x[s+1])/2.,]

                print(r[-1][-1])
                print(c[-1][-1])


                A advice :
                When don't understand algorithm, you can run it by hand in scratch paper, maybe you will figure out how it work.







                share|improve this answer














                share|improve this answer



                share|improve this answer








                edited Mar 9 at 7:42

























                answered Mar 9 at 6:57









                Happy BoyHappy Boy

                40629




                40629





























                    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%2f55073517%2fpython-number-line-cluster-exercise%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

                    Identity Server 4 is not redirecting to Angular app after login2019 Community Moderator ElectionIdentity Server 4 and dockerIdentityserver implicit flow unauthorized_clientIdentityServer Hybrid Flow - Access Token is null after user successful loginIdentity Server to MVC client : Page Redirect After loginLogin with Steam OpenId(oidc-client-js)Identity Server 4+.NET Core 2.0 + IdentityIdentityServer4 post-login redirect not working in Edge browserCall to IdentityServer4 generates System.NullReferenceException: Object reference not set to an instance of an objectIdentityServer4 without HTTPS not workingHow to get Authorization code from identity server without login form

                    2005 Ahvaz unrest Contents Background Causes Casualties Aftermath See also References Navigation menue"At Least 10 Are Killed by Bombs in Iran""Iran"Archived"Arab-Iranians in Iran to make April 15 'Day of Fury'"State of Mind, State of Order: Reactions to Ethnic Unrest in the Islamic Republic of Iran.10.1111/j.1754-9469.2008.00028.x"Iran hangs Arab separatists"Iran Overview from ArchivedConstitution of the Islamic Republic of Iran"Tehran puzzled by forged 'riots' letter""Iran and its minorities: Down in the second class""Iran: Handling Of Ahvaz Unrest Could End With Televised Confessions""Bombings Rock Iran Ahead of Election""Five die in Iran ethnic clashes""Iran: Need for restraint as anniversary of unrest in Khuzestan approaches"Archived"Iranian Sunni protesters killed in clashes with security forces"Archived

                    Can't initialize raids on a new ASUS Prime B360M-A motherboard2019 Community Moderator ElectionSimilar to RAID config yet more like mirroring solution?Can't get motherboard serial numberWhy does the BIOS entry point start with a WBINVD instruction?UEFI performance Asus Maximus V Extreme