File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Permutation help Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Permutation help" Watch "Permutation help" New topic
Author

Permutation help

Tempora Telora
Ranch Hand

Joined: Jun 20, 2005
Posts: 83
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

Joined: Jun 27, 2002
Posts: 4118
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 ]

Java Regular Expressions
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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'm not back." - Bill Harding, Twister
Michael Dunn
Ranch Hand

Joined: Jun 09, 2003
Posts: 4632
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

Joined: Oct 25, 2000
Posts: 7292

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?


Make visible what, without you, might perhaps never have been seen.
- Robert Bresson
Jayesh Lalwani
Ranch Hand

Joined: Nov 05, 2004
Posts: 502
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

Joined: Jan 30, 2000
Posts: 18671
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

Joined: Nov 05, 2004
Posts: 502
But, for this problem, if you sort the list, you don't need to generate all the combinations
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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

Joined: Dec 06, 2001
Posts: 3061
"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


Java API Documentation
The Java Tutorial
Joel McNary
Bartender

Joined: Aug 20, 2001
Posts: 1817

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.


Piscis Babelis est parvus, flavus, et hiridicus, et est probabiliter insolitissima raritas in toto mundo.
Joel McNary
Bartender

Joined: Aug 20, 2001
Posts: 1817

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

Joined: Nov 05, 2004
Posts: 502
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!.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Permutation help