This week's book giveaway is in the Clojure forum.
We're giving away four copies of Clojure in Action and have Amit Rathore and Francis Avila on-line!
See this thread for details.
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

permutations of the list

 
Mona Alsh
Ranch Hand
Posts: 32
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1158
Eclipse IDE Firefox Browser Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Could you paste the code that you claim is working for permuting characters?
 
fred rosenberger
lowercase baba
Bartender
Pie
Posts: 12017
24
Chrome Java Linux
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Mona Alsh
Ranch Hand
Posts: 32
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 32
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 9472
50
Eclipse IDE Hibernate Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Mona Alsh
Ranch Hand
Posts: 32
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 9472
50
Eclipse IDE Hibernate Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 32
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 6529
21
Java Linux Mac Scala Spring
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Mona Alsh
Ranch Hand
Posts: 32
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 6529
21
Java Linux Mac Scala Spring
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 9472
50
Eclipse IDE Hibernate Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic