This week's book giveaway is in the Android forum. We're giving away four copies of Head First Android and have Dawn & David Griffiths on-line! See this thread for details.

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?

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 ]

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 ]

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

posted

0

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

posted

0

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

posted

0

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 ]

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.

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

posted

0

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!.