File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes permutations of the list Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "permutations of the list" Watch "permutations of the list" New topic
Author

permutations of the list

Mona Alsh
Ranch Hand

Joined: Dec 20, 2012
Posts: 32
Hi,
I'm trying to find all permutations of the elements of the list, I'm using an algorithm that has worked just fine with an array of characters but didn't work with list
can you please check the code below and tell me what's wrong

Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Could you paste the code that you claim is working for permuting characters?


~ Mansukh
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10916
    
  12

Remember, " ItDoesntWorkIsUseless " (<---click that link). Does it compile? Does it run? Does it throw a NPE? Does it give the wrong results? Does it not let you add items to the list?

There are about a million ways it could "not work". Your job here is to make it as EASY as possible for someone to help you, and tell us what you know - and what it is doing that you think should be something else.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Mona Alsh
Ranch Hand

Joined: Dec 20, 2012
Posts: 32
Mansukhdeep Thind wrote:Could you paste the code that you claim is working for permuting characters?


Here it is , I used recursion to first find the first letter and permute all of the remaining letter . After finishing with frist letter, I go with second letter and do the same and so on

Mona Alsh
Ranch Hand

Joined: Dec 20, 2012
Posts: 32
fred rosenberger wrote:Remember, " ItDoesntWorkIsUseless " (<---click that link). Does it compile? Does it run? Does it throw a NPE? Does it give the wrong results? Does it not let you add items to the list?

There are about a million ways it could "not work". Your job here is to make it as EASY as possible for someone to help you, and tell us what you know - and what it is doing that you think should be something else.



I apologize for this misunderstand of the rules. I've pasted the code that worked with string in the second reply.
thanks for drawing my attention to this issue.
Thomas Kasene
Greenhorn

Joined: Feb 21, 2013
Posts: 3
Hey there,

As with any recursive method, there are two ways to end it: either by getting a StackOverflowError or an OutOfMemoryError, or by having a base case in your method. You'll get the errors when the method calls itself so many times that the program reaches its limits in terms of memory usage and/or callstack size, which typically happens when the method never reaches any of its base cases.

In your code, the if-block checking whether rest.isEmpty() is the base case. As far as I can tell, however, the rest list is never emptied, nor are its elements removed in any other way. List.subList() doesn't remove any elements, it just returns a view of the list, but the original list remains intact.

Good luck!
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7052
    
  16

Mona Alsh wrote:Here it is , I used recursion to first find the first letter and permute all of the remaining letter . After finishing with frist letter, I go with second letter and do the same and so on

I think it's very important for you (and us) to understand exactly what you mean by "permutations". Does your algorithm, for example, consistently return a combination where the elements are in reverse sequence? Especially for more than just three or four items.

Also: permutations are usually applied to Sets, whereas you are applying them to Lists, which allow duplicate entries (as do arrays).

I'm not saying that you've done anything wildly wrong; just that we need to know the full parameters to the problem.

Winston

Isn't it funny how there's always time and money enough to do it WRONG?
Artlicles by Winston can be found here
Mona Alsh
Ranch Hand

Joined: Dec 20, 2012
Posts: 32
Winston Gutkowski wrote:
Mona Alsh wrote:Here it is , I used recursion to first find the first letter and permute all of the remaining letter . After finishing with frist letter, I go with second letter and do the same and so on

I think it's very important for you (and us) to understand exactly what you mean by "permutations". Does your algorithm, for example, consistently return a combination where the elements are in reverse sequence? Especially for more than just three or four items.

Also: permutations are usually applied to Sets, whereas you are applying them to Lists, which allow duplicate entries (as do arrays).

I'm not saying that you've done anything wildly wrong; just that we need to know the full parameters to the problem.

Winston


Thank you Winston for your reply
I mean by permutation all possible orders of the lists, as I mentioned above I did it with string of characters and it worked but
when I used the same algorithm using list of string items, it didn't work.
even if I didn't use set, the algorithm should work because it worked with string of characters without displaying duplicates.

Thanks again and I look forward to solving this problem with your help.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7052
    
  16

Mona Alsh wrote:I mean by permutation all possible orders of the lists, as I mentioned above I did it with string of characters and it worked...

Including reversed order? Looking at your code, that seems odd, since you always keep the same order of items (or characters) and simply shift one internal one around for each initial subset. Like I say, the term "permutations" covers a whole bunch of possibilities, and we really need to know what you mean by it.

The number of possibilities of your algorithm is measured in factorials. The number of all possible combinations in n^n.

And when you have duplicate elements involved, your algorithm will produce duplicate combinations.

Winston
Mona Alsh
Ranch Hand

Joined: Dec 20, 2012
Posts: 32
Winston Gutkowski wrote:
And when you have duplicate elements involved, your algorithm will produce duplicate combinations.




It is ok if my algorithm computes duplicates if the list contains items. The only think I want to fix is how to make it work with a list of different items. Say I've a list of strings

ArrayList<>String colors = new ArrayList<String>();

colors.add("red");
colors.add("yellow");
colors.add("blue");

now the list contains three colors

I just want to print the list every time with different order , I should have 3! = 3 * 2 * 1 = 6 orders
the print statment should produce the following:
["red","yellow","blue"]
["red","blue","yellow"]
["yellow","red","blue"]
["yellow","blue","red"]
["blue","red","yellow"]
["blue","yellow","red"]

That is what I expected from my code as it did with string of characters.I'll not incldue duplicates in my list , so i'll not get duplicates in the list it going to produce.

Thanks,
Mona
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4419
    
    5

These two statements do not do similar things; one creates a new object, the other doesn't:

Understand why it makes a difference and you'll know how to fix the bug


Junilu - [How to Ask Questions] [How to Answer Questions]
Mona Alsh
Ranch Hand

Joined: Dec 20, 2012
Posts: 32
Junilu Lacar wrote:These two statements do not do similar things; one creates a new object, the other doesn't:

Understand why it makes a difference and you'll know how to fix the bug


you mean I should create ArrayList in the for loop , but that didn't help either!!
I'm still learning and I would appreciate if you show me where to create the ArrayList object!

Thanks a lot
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4419
    
    5

Mona Alsh wrote:
you mean I should create ArrayList in the for loop , but that didn't help either!!
I'm still learning and I would appreciate if you show me where to create the ArrayList object!

Please read this: ItDoesntWorkIsUseless (←click)

What did you try? If you post the code that you tried, we might see how to guide you closer to a solution but we won't give you the code outright because we view that as being counterproductive.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7052
    
  16

Mona Alsh wrote:you mean I should create ArrayList in the for loop , but that didn't help either!!
I'm still learning and I would appreciate if you show me where to create the ArrayList object!

Unless you have a good Maths background, like Fred and Matthew (and possibly Junilu; don't know ) recursion is hard. I still find it tough for non-trivial stuff, even after 35 years in the biz; and the only thing that works for me is pencil and paper.

The only thing I can tell you is that you must keep a copy of the original list; and, since your "permutations" are all going to be lists of the same length, your output needs to reflect that. However, since you're also building it up gradually, I'd probably keep a single "builder" list (of the same length as the original) that I overwrite portions of as required. When I know I'm ready to output a result, I'd copy the current 'snapshot' of my builder list to an output version.

Hope it helps.

Winston
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: permutations of the list
 
Similar Threads
missing one record from excel to access using datasources for both drivers
Compilation Fails at Line 2.
Linked List equals method
Using Two ArrayLists For One Table
Collection