Tempora Telora

Ranch Hand

Posts: 83

posted 12 years ago

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?

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

( and author)

Sheriff

Posts: 4118

posted 12 years ago

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 ]

The Former is probably a more OO approach.

best,

M

[ September 15, 2005: Message edited by: Max Habibi ]

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 12 years ago

I'm not sure how much

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

*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

Posts: 4632

posted 12 years ago

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

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

Jayesh Lalwani

Ranch Hand

Posts: 502

posted 12 years ago

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

Originally posted by Jim Yingst:

I'm not sure how muchsortinghas to do with this - the question is about generatingpermutations. 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

Sheriff

Posts: 18671

posted 12 years ago

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.

"I'm not back." - Bill Harding, *Twister*

Jayesh Lalwani

Ranch Hand

Posts: 502

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 12 years ago

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

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

*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 ]

"I'm not back." - Bill Harding, *Twister*

Layne Lund

Ranch Hand

Posts: 3061

posted 12 years ago

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.

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.

posted 12 years ago

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.
Piscis Babelis est parvus, flavus, et hiridicus, et est probabiliter insolitissima raritas in toto mundo.

Originally posted by Jim Yingst:

Generating all combinationsisa 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

posted 12 years ago

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

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