permutations

[tavo alfonso]

hi my name is tavo, i got to do in java a method than give all the posible permutations of a string like "abc" i was looking for a logical solution but i couldnt find it, i hope somebody here could tell me how, but i dont want the code, i just want an explication, i know it could be done in two ways, by recursivity or in the normal way, but its all i know i hope you can help me

[David McCombs]

To find out how many permutations(remember with permutations, order matters) use n!/(n-r)! This is good to know, so you know how many lines of output you should have.

To actually find them a string with 3 letters is a good start. Find a way to generate them on paper in a logical pattern:

abc
acb
bac
bca
cab
cba

Note the pattern and apply it to an algorithm for this specific case. If you need it to work for just about any length of string, you need to generalize the algorithm.

I don't think it matters much if you use a loop or recursion, but a loop might be a bit easier. Now try to apply it to code. Test it and if it doesn't work, come here with specific questions and the code you wrote.

[tavo alfonso]

this is what i got, i take the String, lets supose that is "abc" and i cut it in letters, each letter has an space in a array, so i got Array[];
array[0]=a;
array[1]=b;
array[2]=c;

so what i want to do is just play with the spaces of the array whit loops, but i got a problem, this algorytm must work whit a String of any sice.
so i try no find a logic way.

with this example i know that i had 6 permutantions, i know too that in the array are 3 diferent letters, i made a factorial of 3-1; that is 2, whit these i know that the fist letter repeats 2 times so i have this:

a
a
b
b
c
c

so for the next 2 letters y was tinking that i could use a swap, to move the letters of position, but i dont know how really swap works,

and its all that i got, and this could be efficent whith a String of 2 letter but not with a String of 4 or more...

how, can i move the spaces of a array?
i mean:

array[0]=a
array[1]=b
array[2]=c
to
array[0]=b
array[1]=c
arrya[2]=a

[Stan James]

Try to describe it in plain language. For three letters, maybe:

for each letter
   add that letter to the output
   add the other two letters from left to right
   add the other two letters from right to left

Try to get that much in code and see if it makes sense. If the next assignment is 4 letters, we ought to generalize that "add the others" bit. Here's another way to do three letters:

for each letter
   add that letter to the output
   for each letter that we haven't used yet
      add that letter to the output
      for each letter that we haven't used yet 
         add that letter to the output

Starts to look like recursion. Give it a shot, if you get stuck show us what you have.

[Greg Charles]

I'll just add a couple of points. First the number of permutations is going to be n! not n!/(n-r)!. What would "r" be in this case? Next, you can avoid putting the characters into the array explicitly by using the String.toCharArray() method, e.g. "abc".toCharArrary().

Once you have this array, you don't really need to swap the elements. If I understand right, all you need to do is print out the possible permutations, so there is no need to ever actually change the array itself. This may be confusing, but a lot of the magic of software is simulating what it appears to do. It's just like when you drag an icon across the screen, you aren't actually moving it, but just erasing pixels in one location and drawing them in another. So, think how you would print out the array in various orders without actually rearranging it internally. I agree that you might use recursion, or possibly just a loop.

Good luck!
[ November 03, 2006: Message edited by: Greg Charles ]

[David McCombs]

Note: remove the / in my post, it was just put there to avoid the pointless filtering of certain characters and isn't a very smart filter. Which is also the reason some of this post is in code tags.

The formula for finding permutations is exactly what I posted and correct for ANY permutation. n! works in this case is only because n and /r are equal. Posting that a permutation is n!(even though it is correct in this case), gives the false impression that n! works in all permutation cases, which is false.

n=the number of characters in the string, in the string "abc" n=3.
r=the number of characters chosen, always. In this case, r=3.

3!/(3-3)! = 6

[ November 03, 2006: Message edited by: David McCombs ]
[ November 03, 2006: Message edited by: David McCombs ]

[Jim Yingst]

[David]: Note: remove the / in my post, it was just put there to avoid the pointless filtering of certain characters and isn't a very smart filter. Which is also the reason some of this post is in code tags.

Hunh? The only / in your previous post was quite necessary, I think, unless you also remove the (n-r ! term.

As for the fitering, it's not pointless, but I acknowledge it does sometimes get in the way of legitimate posts. Still, given the number of nearly unreadable posts we used to have from people who felt the need to abbreviate 'you' as 'u', and similar shortcuts, I think it's worth it.

[Greg]: What would "r" be in this case?

Ummm... equal to n, I would think. What else could it be? This easily converts David's formula to Greg's. The difference in formulas seems like a non-issue to me. David gave a more general formula, while Greg gave a more specific one (where r = 0). I think the more specific one is all we need for this particular problem. But really, the more general formula isn't that complex, and it's easy to imagine similar problems with slightly more complex problem statements which would require the more general formula. In fact, I'm still not 100% certain what "all the possible permutations of a string like 'abc'" means. But the simplest interpretation I can think of is that it means all possible permutations of the characters a, b, c (three possibilities, n = 3) in a list of length 3 (r = 3). Great, so n = r and we can use the simpler formula. Huzzah!

[Henry Wong]

i know it could be done in two ways, by recursivity or in the normal way

When I look at this problem, all I see is the recursive solution. To me, the recursive solution is the "normal way". Can this actually be done easily without recursion?

Henry

[David McCombs]

I think the more specific one is all we need for this particular problem. But really, the more general formula isn't that complex, and it's easy to imagine similar problems with slightly more complex problem statements which would require the more general formula. In fact, I'm still not 100% certain what "all the possible permutations of a string like 'abc'" means.

n! is all that is needed, but needs to be made clear it is only for a certain special case. Otherwise people without a basic mathematics background could be misled. What if it was a string of length 4, and all possible permutations of 2 characters in the string was required?

"all the possible permutations of a string like 'abc'" means exactly what the definition of permutations implies. A permutation, is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. Simply put it is all possible ordered combinations of the set of items.

In permutations, order matters. "abc" is not the same as "bac" or "cba".

Related is combinations, where there is no sense of order, so given "abc" and choosing 3 characters, there is exactly 1 combination because "abc"="bac"="cba"=...

Hope that is a bit helpful.

[ November 03, 2006: Message edited by: David McCombs ]
[ November 03, 2006: Message edited by: David McCombs ]

[Jim Yingst]

[David]: "all the possible permutations of a string like 'abc' means exactly what the definition of permutations implies.

Oh, piffle. 'Permutations' is clear enough, but what I'm not certain of is, what is meant by "string like 'abc'"? Because, frankly, if J Random Client uses a term like that, I need to ask more questions before I'm certain what they really mean. In particular, I would need to know if a string like 'aab' is something we should consider. Is 'aab' like abc enough that we should consider it, or not? Or more concisely: Is 'aab' a valid input? Or more generally, something like 'aaabbccccd'? A real-world client might answer either yes or no, depending on their needs, and each leads to different results. (Well, technically the result with no repetitions is a subset of the result allowing for possible repetitions.) The answers given here so far do not include the possibility of repetition within the string - and while I would concede that I think such repetition is probably not intended, based on the original question, I think it would be irresponsible to assume that's the case. That's what I mean when I say "I'm still not 100% certain what "all the possible permutations of a string like 'abc'" means."

[David McCombs]

I think it would be safe to assume no repetitions, else you would eventually have an infinite set of strings. Besides, repetitions have no part in the definition of permutation.

A string like "abc" implies, at least to me, that the string can have any length.

The only thing I think is somewhat vague is a string like "aab" allowed, like you talked about.

Whether it is allowed or not is hardly worth worrying about since the first a and the second a can be treated as separate items. It doesn't really change the essence of the problem since what is in each index is largely irrelevant. In a string of length 3, you can consider index 0, index 1, index 2, and sort them as such. If the values in the indices are the same, they are still considered different items and as such has the same number of permutations as it would if the 3 indices were unique.

To make my point clearer: let's say you have three books. "Unix Network Programming", "Head First Design Patterns" and "Unix Network Programming". 2 of the books are the same, but are there really less ways you can stack them then if they were 3 different titles?

Anyway, I am sure I flogged this to death, and then some. Sorry for misunderstanding your question. I hope you didn't take offense.

[Jim Yingst]

[David]: I think it would be safe to assume no repetitions, else you would eventually have an infinite set of strings.

Ummm... what? I have no idea what you're thinking of here. It's easy to specify a problem that allows repetitions, but requires finite overall length, or finite repetitions for individual elements. Take two standard decks of 52 cards and put them together - how many different ways are there to order these? (Considering each pair of identical cards as equivalent.) The answer is very big, but not infinite: it's 104!/2^52.

[David]: repetitions have no part in the definition of permutation.

I disagree. Repetition may not be part of the most naive definitions of permutation, but it's a standard complication to consider when dealing with permutations:

http://en.wikipedia.org/wiki/Permutations_and_combinations

[David]: To make my point clearer: let's say you have three books. "Unix Network Programming", "Head First Design Patterns" and "Unix Network Programming". 2 of the books are the same, but are there really less ways you can stack them then if they were 3 different titles?

Depends whether you consider the two Unix books as truly indistinguishable, or not. (This is similar to asking, are you using == or .equals() to determine equality?) If the two volumes are distinguishable, there are 6 ways to order the books; if they are indistinguishable, there are 3. Which answer is more appropriate depends on the context of the problem.

Putting it another way: If I asked how many ways are there to order the letters in "aab", would you tell me there are 3 ways, or 6? I can list three: "aab", "aba", "baa". If you say six, what are the other three? I can imagine contexts where it makes sense to distinguish between the two a's. But I can also (quite easily) imagine contexts where that makes no sense at all.

[David McCombs]

If you have a set and one or more elements are the same, you can merge those elements without changing the set. Using the definition of permutations a pair of cards containing the ace of spaces and 3 of hearts is a different pair then then 3 of hearts and the ace of spades. If you consider them to be the same you no longer have permutations but combinations.

That link doesn't really make your point. In the permutation without repetition section, the same dog will show up in many of those 2730 ways to order them, but the same ordered set will not show up twice. (spot, fido, max) is not the same set as (fido, spot, max).

"If I asked how many ways are there to order the letters in "aab", would you tell me there are 3 ways, or 6?"

I would answer 6 because in the context of original question each index is what matters. I think it is irrelevant what is in the string elements.

index 1, index 2, index 3

index 1, index 3, index 2

index 2, index 1, index 3

index 2, index 3, index 1

index 3, index 1, index 2

index 3, index 2, index 1

[Jim Yingst]

There are a large number of links out there which demonstrate that just because someone talks about permutations, they are not necessarily excluding the possibility of repetition of identical elements.

http://regentsprep.org/Regents/Math/permut/LpermRep.htm
http://www.mathsisfun.com/combinatorics/combinations-permutations.html
http://www.cartage.org.lb/en/themes/Sciences/Mathematics/Algebra/foci/topics/Countingproblems/Countingproblems.htm

I'm sure you can also find links that talk about permutations and combinations only in the context of no repetitions. That's fine; it's a common problem to consider (with simpler formulas, after all) but that doesn't mean it's the only definition of permutations out there.

[David]: Using the definition of permutations a pair of cards containing the ace of spaces and 3 of hearts is a different pair then then 3 of hearts and the ace of spades. If you consider them to be the same you no longer have permutations but combinations.

Missing the point of my cards example. Obviously the three of hearts and ace of spades are different. That's why I specified two decks. Each card now has one identical match from the other deck. The problem doesn't magically turn into combinations just because some elements are identical. Order still matters, except when comparing the positions of two identical cards.

[David]: That link doesn't really make your point. In the permutation without repetition section, the same dog will show up in many of those 2730 ways to order them, but the same ordered set will not show up twice. (spot, fido, max) is not the same set as (fido, spot, max).

Another missed point. Your apparent need to continually re-explain permutations without repetition is irrelevant - I gave that link to support that it's also valid to consider permutations with repetition. (We don't know if that was the original poster's intent, but I submit it's possible.) You're looking in the wrong section, with respect to the point I was making.

[I would answer 6 because in the context of original question each index is what matters.

But in the question I asked, index was not mentioned at all. I talked about letters. Your answer about indices is changing the context of the question I asked. If you're talking about the original poster's question, then yes it's possible that index was what they cared about. (Though here again, index was never mentioned in that question either - you're just guessing about what they cared about.) My point was that I wasn't 100% sure what they meant, as I said. If you can be sure by mentally blocking out any possibility of another interpretation, great. There's a fairly high chance the no-repetition scenario is all the original poster cared about. But it is not 100%, unless we get more info from the original poster.

I love the Stan Kelly-Bootle quote in your signature, by the way.
[ November 04, 2006: Message edited by: Jim Yingst ]

[tavo alfonso]

well, i was reading the all the posts and these is what i got,

public class segundoparcial{

public static void main(String[] args){
String [] arr = {"cba"};
permutaciones(arr);
}
public static void permutaciones(String []arr){

String a="";
a=arr[0];

//ordena los valores del String en orden descendente a asendente, los separa y los mete a una arreglo
//Sort the String Alphabetically, then separe the string and put each letter into an array
char[] convierte = a.toCharArray();
java.util.Arrays.sort(convierte);
String enorden = new String(convierte);
String perm[]=new String[a.length()];
int cont;
for(cont=0;cont<a.length();cont++){
perm[cont]=enorden.substring(cont,cont+1);
}
for(cont=0;cont<a.length();cont++){
System.out.println(""+perm[cont]);
}

//Saca el factorial del String(cuantas posibles convinacioes hay)
//These tell me the convinations that must be done
int factorial=1;
int zz=a.length();

for(;zz>0;zz--){
factorial=factorial*zz;
}
System.out.println(""+factorial);


String bidi[][]=new String[factorial][a.length()];
int repet[]=new int [a.length()-2];
int x;
int y;
int z;

//saka y mete en un array los numeros de los que teng k sakar factoriales

for(x=0;x<a.length()-2;x++){
repet[x]=a.length()-(x+1);
System.out.println("prueba"+repet[x]);
}


}
}
///////

I was thinking that i need another method to make a copi of mi array and start to change spaces, and introduce each permutation into a bidimentional array,.. maybe im wrong, please watch the code and toldme what can i do, im a little stock.

i know that is more easely with recursivty but i dont know how it works, if you can help me, please try to do it without recursivity thanks

[saikrishna cinux]

import java.util.*;
import java.io.*;
public class Combinations
{
public static void main(String ars[])
{
 

boolean correct=true;
 

try {
 
File f=new File("data.xls");
FileWriter ff=new FileWriter(f);
 

for(; :wink: {
inti=2;
 
System.out.print(i+" ");
 
Integer ii=new Integer(i);
ff.write(ii.toString());
 
for(int x=0;x<4;x++)
{
 
if(correct==new Random().nextBoolean())
 {
 if(i==1)
 i++;
 else if(i==2)
 i++;
 else if(i==3)
 i=3;
System.out.print(i+" ");
Integer ii1=new Integer(i);
ff.write(ii1.toString());
 

 }
 

 else
 {
 if(i==3)
 --i;
 else if(i==2)
 --i;
 else if(i==1)
 i=1;
System.out.print(i+" ");
 
Integer ii2=new Integer(i);
ff.write(ii2.toString());
 
 }
 

}
 System.out.println();
ff.write("\r");
 
}//End of infinity loop
 

 

}
 
catch(Exception e){System.out.println(e);}
 

 
}}
 

similar code