• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Permutation help

 
Tempora Telora
Ranch Hand
Posts: 83
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok guys here is my problem. I know that i have to develop some way to create permutations of a list that is given to me. But i am not for sure how to do this. For example i will recieve a list of items such as:
123
90
200
11
599
and i have to figure out the best combination to get closest to 2000. Is there a permutation generator in java? Or should i use a cloned array and try and do some sorting methods?
 
Max Habibi
town drunk
( and author)
Sheriff
Posts: 4118
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You have two general approaches here: Either provide a Comparator that does the correct type of comparision, then feed the List and the Comparator to the static Collections.sort method, or roll your own loop.

The Former is probably a more OO approach.

best,
M
[ September 15, 2005: Message edited by: Max Habibi ]
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm not sure how much sorting has to do with this - the question is about generating permutations. Or really, generating combinations sounds closer to what you want. You can Google "java combinations" or "java permutations" to get many sample algorithms of varying usefulness to you. I suspect that for this particular problem you might do better to roll your own algorithm - but it's going to take some work to figure it out. Generating all combinations using one of the algorithms you find and trying them one at a time it probably a good initial approach. If the performance is good enough, you're done. If not, you will hopefully have gained enough understanding of the complexities to consider how the algoritm could be improved. Good luck...
[ September 15, 2005: Message edited by: Jim Yingst ]
 
Michael Dunn
Ranch Hand
Posts: 4632
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
do you have a login name at sun 'monkeyPop'?

if not, I posted something that works OK on a small range of numbers

http://forum.java.sun.com/thread.jspa?threadID=662769

see reply #20
 
Michael Ernest
High Plains Drifter
Sheriff
Posts: 7292
Netbeans IDE VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What kind of assignment is this for? Are you being asked to deal with a concrete example of a travelling salesman problem to show it is NP complete?
 
Jayesh Lalwani
Ranch Hand
Posts: 502
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Jim Yingst:
I'm not sure how much sorting has to do with this - the question is about generating permutations. Or really, generating combinations sounds closer to what you want. You can Google "java combinations" or "java permutations" to get many sample algorithms of varying usefulness to you. I suspect that for this particular problem you might do better to roll your own algorithm - but it's going to take some work to figure it out. Generating all combinations using one of the algorithms you find and trying them one at a time it probably a good initial approach. If the performance is good enough, you're done. If not, you will hopefully have gained enough understanding of the complexities to consider how the algoritm could be improved. Good luck...

[ September 15, 2005: Message edited by: Jim Yingst ]



I think Max was hinting that sorting the collection leads to a clean solution. Think about this:- "Larger the number you start with, the closer you are to the solution".
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah, I had meant to include in my post something like "it's quite possible that it would be useful to sort your list as a first step..." However it seems as though the bulk of the coding to be done here is not covered by the relatively trivial (thanks to libraries) task of sorting the numbers.
 
Jayesh Lalwani
Ranch Hand
Posts: 502
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But, for this problem, if you sort the list, you don't need to generate all the combinations
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, and this is why I ended up omitting the sentence from my post. (I went back and forth on this.) I was thinking the poster would learn more by doing it themselves. However on reflection you're right that it probably would have been better to provide the hint about sorting, with the caveat that it is only a first step. Although at this point the best route may depend on how well the original poster can work out subsequent steps for himself. Generating all combinations is a valid way to solve the problem, albeit an inefficient one.
[ September 15, 2005: Message edited by: Jim Yingst ]
 
Layne Lund
Ranch Hand
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
"i have to figure out the best combination to get closest to 2000"

I'm not sure what this means. How is a combination (or permutation) "close to 2000"?

Layne
 
Joel McNary
Bartender
Posts: 1840
Eclipse IDE Java Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think that the problem is:

Here is a list of numbers. Find the subset whose sum is closest to 2000. (...without going over the retail price... OK, not really). Of course, the example given is trivial, because the total sum is only 1023, so the answer is the entire set. Add 149, 59, 165, and 765 to the list and it becomes a more interesting problem.

I don't think that sorting is going to help, and permutations can be a bit of a bear, particularily when you are looking for all permutations, not permutations of a specific number.

Generally speaking, what you want to do is have a loop from 1 to n, where n is the number of elements in the set. For each number, you build the subsets that contain that number of elements. I found this best to be done through recursion -- iteration to achieve this is a bit hairy.

See if you can figure it out from that. (You might be able to.) If you get stuck, post your code and we will be glad to help.
 
Joel McNary
Bartender
Posts: 1840
Eclipse IDE Java Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Jim Yingst:
Generating all combinations is a valid way to solve the problem, albeit an inefficient one.


At least the way I'm reading the problem, there doesn't really seem to be any other way to do it. If your list was {1965, 1978, 35} you would have to test 1965 + 1978, 1978 + 35 and 1965 + 35 (and 1965, 1978, 35, and 1978+1965+35) to find that 1965+35 is the closest to 2000.

Thus, I suggest using that input as your test case. It is simple enough that you can do it by hand, and if you can do it by hand, you can write a program to do it.
 
Jayesh Lalwani
Ranch Hand
Posts: 502
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Joel McNary:


At least the way I'm reading the problem, there doesn't really seem to be any other way to do it. If your list was {1965, 1978, 35} you would have to test 1965 + 1978, 1978 + 35 and 1965 + 35 (and 1965, 1978, 35, and 1978+1965+35) to find that 1965+35 is the closest to 2000.


You run 2 loops. The first iteration goes through all elements, the second skips the top most, the third skips the top 2 and so on. Worst case performance:- n-squared. Much better than all combinations, which is what order of N!.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic