Weird permutation algorithm
Greetings!
Since this is my first post, i want first to thank to all of you that made this forum grow, since it helped me a lot in previous times.
Now, my problem =)
I've made several searches across these threads and found none of use. Well, I found some, but they just don't do the job =\
I would like to create an algorithm to calculate all permutations between a String like this one: "iiiooo".
I know the algorithm in "paper", it's output is something like this:
1: iiiooo - - - - - 11: oiiioo
2: iioioo - - - - - 12: oiioio
3: iiooio - - - - - 13: oiiooi
4: iioooi - - - - - 14: oioiio
5: ioiioo - - - - - 15: oioioi
6: ioioio - - - - - 16: oiooii
7: ioiooi - - - - - 17: ooiiio
8: iooiio - - - - - 18: ooiioi
9: iooioi - - - - - 19: ooioii
10: ioooii - - - - - 20: oooiii
The algorithms of permutations around these forums take the "i"'s and "o"'s as independent ones, originating several repetitions causing the program to run very slowly in Strings like "iiiiiioooooo" =\
I would prefer to use recursion in this method/program.
I've already tried several solutions using Strings, chars, and even by assigning int to each char, all of them without success.
So if you could help me I would be very pleased of course.
Best regards!
# 1
> I've made several searches across these threads and found
> none of use. Well, I found some, but they just don't do the job =\
Did you look at this one?
http://forum.java.sun.com/thread.jspa?forumID=426&threadID=408731
Although the output isn't unique, which is what I think you want.
# 2
http://en.wikipedia.org/wiki/Permutation#Algorithm_to_generate_permutations
Besides that, you didn't really provide enough information:
Is each "i" unique? In other words, are we talking about "combination with repetition" or "combination without repetition"?
In case you didn't know, some other keywords that might help your searches be more successful are:
combinatorics
replacement or repetition
counting
sampling
# 3
Ah yes, this is just another version of the clique problem. Essentially you want to choose all unique 3 tuples of 6 elements.
You could have found your answer here:
http://forum.java.sun.com/thread.jspa?forumID=426&threadID=397462
public class TT
{
// n is the number of nodes in the graph
// i and j are both initially both 0
// c[] is a set of integers
// example: clique(5, 0, 0, new int[3]);
// will behave like 3 nested for loops that
// enumerate all unique 3-tuples over a set of 5
public static void clique(int n, int i, int j, int[] c)
{
if (i == c.length) {
int h = 0;
for (int k = 0; k < n; k++) {
if (h < c.length && c[h] == k) {
System.out.print("i");
h++;
}
else {
System.out.print("o");
}
}
//for (int k = 0; k < c.length; k++)
//System.out.print(c[k] + " " );
System.out.println();
}
else {
for (int k = j; k <= (n - c.length) + i; k++) {
c[ i ] = k;
clique(n, i + 1, k + 1, c);
}
}
}
public static void main(String[] args)
{
clique(6, 0, 0, new int[3]);
/*
iiiooo
iioioo
iiooio
iioooi
ioiioo
ioioio
ioiooi
iooiio
iooioi
ioooii
oiiioo
oiioio
oiiooi
oioiio
oioioi
oiooii
ooiiio
ooiioi
ooioii
oooiii
*/
}
}
# 4
Another approach that does not use recursion (and more appropriate if you want your bitset as an integer)
public static void main(String[] args){
for(int i = 0x7; i<=0x1C;){
System.out.println(Integer.toBinaryString(i));
i = nextNumberWithSameNumberOfBits(i);
}
}
public static int nextNumberWithSameNumberOfBits(int a){
int c = a & -a;
int r = a + c;
a = (((r^a) >>> 2) / c) | r;
return a;
}
output is:
111
1011
1101
1110
10011
10101
10110
11001
11010
11100
100011
100101
100110
101001
101010
101100
110001
110010
110100
111000
# 5
Thank you all for your attention and time =)
rkippen algorithm works pretty nice, and outputs all possible permutations. All others seems nice, and the bitwise approach looks very optimized. I'll take a look at that later if no recursion needed.
Once more, thank you all =)
Best regards!
# 6
If the alphabet has a size > 2 then the above bitset approaches don't
work. I once stole the following little algorithm from C++ STL and *ahem*
adjusted it to my taste. The algorithm runs as follows:
1) given a permutation p_1 p_2 ... p_n:
2) find the rightmost i such that p_i < p_i+1
3) if no such i can be found stop
4) find the rightmost j > i such that p_i < p_j
5) swap p_i and p_j
6) reverse p_i+1 ... p_n
note that a j in step 4) can always be found. This is the corresponding
Java implementation:public static int[] perm(int[] p) {
int i, j;
// step 2)
for (i= p.length; --i >= 0; )
if (p[i] < p[i+1])
break;
// step 3)
if (i < 0) return null;
// step 4)
for (j= p.length; j-- > i; )
if (p[j] > p[i])
break;
// step 5)
int tmp= p[i]; p[i]= p[j]; p[j]= tmp;
// step 6)
for (j= p.length; ++i < --j; ) {
tmp= p[i]; p[i]= p[j]; p[j]= tmp;
}
return p;
}
kind regards,
Jos
