Win a copy of Spring in Action (5th edition) this week in the Spring forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • paul wheaton
Saloon Keepers:
  • Ganesh Patekar
  • Frits Walraven
  • Tim Moores
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Stephan van Hulst
  • salvin francis
  • Tim Holloway

Print the position of the array in the output rather than the values  RSS feed

 
Greenhorn
Posts: 8
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have some code that prints out the summary of a given array but want to know how to print the position rather than the value inside the sum?




The current output is:

sum([5, 10])=15
sum([5, 10])=15
sum([15])=15


I am trying to figure out how to get the output to print the position of the array:

sum([3]) = 15
sum([0,3)] = 15
sum([1,3)]=15
 
Marshal
Posts: 61741
193
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

Please use the code button for all code; since you are new I went back, just this once, to use the code button on your code, and doesn't it look better It shows you have been taught to indent code properly. But put some spaces between successive tokens, e.g. in line 26. Don't use_underscores_in_your_names; useMixedCase, sometimes called camelCase.

Why did you say anything about an array? You aren't actually using an array; you are using a List, which is different. Why are you swapping between Lists and arrays? You probably don't need to use Arrays#asList. Not if you can use this instead (Java9+ only). You can't remove anything from such a List; if you don't need to modify it, you can however use its subList() method to get only parts of the List. Nor do you need Arrays.toString because most Lists have an overridden toString() method ready for you to use.
What have you been taught about recursion? What I was taught is that you usually return a value, until you get to a base case, where you return some sort of base value. So you can say,

I am not adding this List, but I know that the sum is equal to the first element plus the sum of the List with its first element removed. But eventually I shall get a lsit with all its elements removed; I shall say that is my base case and give you a default sum of 0.

So, your recursive method will include something like this:-
  • Note the List#isEmpty() method
  • Note use of the ?: operator so I only had to write return once.
  • Note incomplete solution so you have to work out what to pass to the next recursive call. But I have given some hints, and there is no need to copy the List element by element as you were doing.
  • There is another non‑recursive way to summate a List without a loop, which I shall show you at the end of this post. I haven't got the time to give a full explanation of it, but you can probably find hints in the Java™ Tutorials.
    I am not quite sure I understand the bit about printing the index. You could pass 0 to the first call of the method and print it and add 1 to it. You obviously know what you are doing, so you can amend this suggestion to suit your own purposes:-Mystery code follows!
     
    Campbell Ritchie
    Marshal
    Posts: 61741
    193
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    A few minutes ago, I wrote:. . . you have been taught to indent code properly. . . .

    I shall therefore leave it to you to avoid the risk of lines too long when you complete my code suggestion.
     
    Master Rancher
    Posts: 3001
    105
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:(...) .mapToInt(i -> i.intValue())

    or shorter '.mapToInt(i -> i)'
     
    Campbell Ritchie
    Marshal
    Posts: 61741
    193
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I thought the longer form would cause less confusion (yes, you can say about that). That is why I shied back from writing mapToInt(Integer::intValue)
     
    Phillip Small
    Greenhorn
    Posts: 8
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    This seems like I will have to rewrite most of it.  Is there any quicker way so that I can change what is printed?  The position rather than the value? I assumed that the change would be in this line-

    System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);

    But I guess it is not that simple.  Regarding streams, would I add that at the end of the previous code?  I am confused by this.  System.out.printf("Sum = %d%n", List.of(5, 5, 10, 15)
                                       .stream()
                                       .mapToInt(i -> i.intValue())
                                       .sum());
     
    Campbell Ritchie
    Marshal
    Posts: 61741
    193
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    If you have a List, you can simply print it with System.out.println or similar. Try it. I did earlier on JShell, which is available on Java9+.

    jshell wrote:jshell> System.out.println(List.of(5, 5, 10, 15).subList(1, 4));
    [5, 10, 15]

     
    Campbell Ritchie
    Marshal
    Posts: 61741
    193
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Forget about the mystery Stream code for the time being.
     
    Sheriff
    Posts: 12747
    210
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Phillip Small wrote:
    The current output is:
    sum([5, 10])=15
    sum([5, 10])=15
    sum([15])=15


    I am trying to figure out how to get the output to print the position of the array:
    sum([3]) = 15
    sum([0,3)] = 15
    sum([1,3)]=15


    Well, if I'm understanding what you want to do, shouldn't the output be:

    sum([0, 2]) = 15  // [5, 5, 10, 15]
    sum([1, 2]) = 15  // [5, 5, 10, 15]
    sum([3]) = 15     // [5, 5, 10, 15]

    instead?
     
    Phillip Small
    Greenhorn
    Posts: 8
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    That would work as well.  
     
    Phillip Small
    Greenhorn
    Posts: 8
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Yes Junilu.  basically, I am trying to figure out how to get the position.  the code will loop through and find the correct value based on the values in the array.  
     
    Junilu Lacar
    Sheriff
    Posts: 12747
    210
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Phillip Small wrote:That would work as well.


    "... as well"?

    That implies either is correct. I would argue that my suggestion excludes your "solution". Only one or the other is correct.

    When you are programming, you need to learn to make unambiguous statements. Ambiguity leads to confusion and bugs.

    So which is correct, my suggestion or yours?
     
    Phillip Small
    Greenhorn
    Posts: 8
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I self-corrected my statement in a reply right after that.  My mistake.  you are absolutely correct.  Thanks for the catch.  
     
    Piet Souris
    Master Rancher
    Posts: 3001
    105
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    hi Philip,

    if what Junilu writes is correct, then this is a simple solution:

    However, in you opening post code, you have a variable called target. I don't understand what you are doing in that code, despite your explanations. Can you elaborate once more about your intentions?
     
    Campbell Ritchie
    Marshal
    Posts: 61741
    193
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    That is quite different from what I thought was required at first.

    Only read what follows if you are feeling ambitious.

    Shall I let you out of your misery about Streams? They were introduced for Java8 about 4½ years ago. The concept is that you run Source→Stream₁→Stream₂→…→Stream→Destination.
    You can have as many intermediate Streams as you like, or as few. Streams run on lazy execution, so nothing happens until the last method, represented by an arrow, starts.
    In my example, the List is the source. You create a Stream, which will be a Stream<Integer> because it is created from a List<Integer> with its [inherited] stream() method. A Stream<XYZ> handles XYZ objects from its source and passes them oon towards its destination, usually having manipulated those objects somehow. There are lots of possibilities.
    I now want to change the Integers in the Stream to ints, but you can't have an ordinary Stream of primitives. You can however have one of three kinds of Stream specially designed to handle primitives, in this case an IntStream. If you go back to Stream, you will find it has a method called mapToInt(), which returns an IntStream. You can reduce its argument to use the Integer#intValue() method. You will find more about that strange syntax using -> in the Java™ Tutorials..
    Finally, the IntStream has a sum() method, which is probably the easiest part to understand.
     
    Junilu Lacar
    Sheriff
    Posts: 12747
    210
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Here's the problem as I understand it from the example provided by OP:

    Given:
    - a list L of integers {int0, int1, ..., intN}
    - an integer representing a "target" sum

    Find:
    All lists of integers I {i0, i1, ..., iN} such that L.get(i0)) + L.get(i1) + ... + L.get(iN) = target

    Each list I will have at least one element and at most as many elements as there are in L.

    If I has one element, then L.get(i0) = target
     
    Piet Souris
    Master Rancher
    Posts: 3001
    105
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Yeah, that is what I suspect, but I couldn't make that up from the code, so I would like OP ro explain it better. If it is indeed as you describe, then a way would be to determine all subsets of the numbers 0... (list.size - 1), map these to the real subsets, and see whether the sum is right. Getting all the subsets is a subject that pops up frequently at this site.

    Another, perhaps easier, way is to take an element from again the index set 0... (List.size -1), and if the map to the real list is less than the target, take the right subset (the tail) and go into the recursion. Now, I get the impression that that is what OP is doing, so I hope he can confirm that this is the case.

    But splendid work, Junilu!  
     
    Phillip Small
    Greenhorn
    Posts: 8
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks for the great advice everyone.
     
    Phillip Small
    Greenhorn
    Posts: 8
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Yes, this is the case Piet.  
     
    Junilu Lacar
    Sheriff
    Posts: 12747
    210
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Since it's a problem that lends itself naturally to recursion, my initial thought is to solve it in Scala. A good Scala solution would be very elegant. I am on the road right now but will give it a shot later in Java. Then maybe dust off my Scala.

    I think OP deserves a cow or some pie just for giving us a nice little puzzle to play around with. I don't know if I've seen this one before actually.
     
    Piet Souris
    Master Rancher
    Posts: 3001
    105
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    By sorting the list in the first place you can optimize the search a little (the indices that form a solution will change accordingly, but if allowed, the effect is the same).
    For instance, if you have a sublist of indices, with a real sum less than target, and say, the first element of the tail leads to a sum that is larger than the target, you do not need to inspect thst tail any further.
    Like:

    the original sorted list is {1, 3, 5, 7, 9}, and you try the index sublist {0, 2} with a sum of 6, the target being 8, the next index sublist would be {0, 2, 3} leading to a sum of 13, then you do not need to inspect the index sublist {0, 2} any further.

    You do not need Scala, although I like that language a lot, in Java it works just as well. To determine the real sum of an index sublist is in fact the code I gave. Well, the solution is indeed relatively easy, happy trying!

    Junilu wrote:I think OP deserves a cow or some pie just for giving us a nice little puzzle to play around with. I don't know if I've seen this one before actually.


    Can't remember too, but I agree with the cow.
     
    Junilu Lacar
    Sheriff
    Posts: 12747
    210
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Junilu Lacar wrote:I think OP deserves a cow or some pie just for giving us a nice little puzzle to play around with. I don't know if I've seen this one before actually.


    Cool. I see OP got a cow and some pie to boot. He might have to go on a diet if he keeps this up.
     
    Campbell Ritchie
    Marshal
    Posts: 61741
    193
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Cow and pie on your first post? that is quite an achievement
     
    Junilu Lacar
    Sheriff
    Posts: 12747
    210
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I see a common pattern here: Trying to solve everything all at once.

    You don't have to. Break the problem down into simpler problems.

    My first step might be to figure out how to get combinations of things in a list.

    Given a list [5, 5, 10, 15], these are the combinations I can get from them:

    [5], [5], [10], [15]
    [5, 5], [5, 10], [5, 15], [5, 10], [5, 15], [10, 15]
    [5, 5, 10], [5, 5, 15], [5, 10, 15], [5, 10, 15]
    [5, 5, 10, 15]

    If I were to use indices for the above combinations instead of the values:
    [0], [1], [2], [3]
    [0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]
    [0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]
    [0, 1, 2, 3]

    Then I would filter out any of those that didn't result in a sum that's equal to the target.
    [0], [1], [2], [3]
    [0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]
    [0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]
    [0, 1, 2, 3]

    ==> [3], [0, 2], [1, 2]

    The patterns I see with the indices strongly suggests a recursive algorithm.

    This is how I would work it out by hand. Now I can start working it out in a program.
     
    Phillip Small
    Greenhorn
    Posts: 8
    2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    That makes logical sense.  You make it sound easy.  This thing is killing me.  Thanks for your assistance.  Maybe, I should just start over.  
     
    Junilu Lacar
    Sheriff
    Posts: 12747
    210
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Phillip Small wrote:That makes logical sense.  You make it sound easy.  This thing is killing me.  Thanks for your assistance.  Maybe, I should just start over.


    Don't get too down on yourself; a recursive algorithm is not easy to formulate.
     
    Junilu Lacar
    Sheriff
    Posts: 12747
    210
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Here are some things about recursive algorithms:

    1. Recursion successively breaks down a big problem into a trivial problem + a not-so-big problem
    2. It usually uses the result of the not-so-big problem in some way
    3. It usually stops when the not-so-big problem becomes a trivial problem

    I have a feeling all these are going to be true for the problem of finding combinations([0, 1, 2, 3])
     
    Saloon Keeper
    Posts: 1174
    73
    Eclipse IDE Hibernate jQuery MySQL Database Spring Tomcat Server
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Congratulations Phillip Small,

    Your question has made it to our Journal    

    Have a Cow!
     
    Consider Paul's rocket mass heater.
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!