Hi,
how can I get the n-permutation of a given array of numbers? By n-permutation I mean e.g. for an array like 1|2|3|4 there are the 3-permutations 1|2, 1|3, 1|4, 2|3 and so on.
I tried to find a method, but I was not successful. Now I would like to write it on my own, but I have no idea about the algorithm...
I am a beginner and would be thankful for any help
Sabina
I'm sorry, but if I remember it correctly a permutation of n (unique) numbers is a variation of the length n containing each of the numbers exactly once, so for 1, 2, 3 you have:
123 132 213 231 312 321 (there is always n! permutation)
You could have also permutation of non-unique numbers (1, 2, 2)
122 212 221 (3! / 2! - in the denominator you have multiples of factorials of all the numbers that repeat)
What you mentioned is either combinations or variations of the length 2 (depending whether the order is significant: are 1-2 2-1 the same or not?)
Ideas for construction the permutations:
1. sort the numbers
Now the best way is to have some recursive thinking:
2a. let's say that we will move the first number so that it consequently take the 1st, 2nd, 3rd, ... n-th position. By doing that we will certainly get some permutations, but it's no brainer to see that certainly no all of them
2b. nevertheless, if the first number is somehow out, what is left is (n-1) numbers and task to create permutation from them
2c. but repeating recursively 2a. and 2b. you can actually solve this. Only don't forget to stop your recursion when you reach the state: one position left for the last number.
Ex. (for 1, 2, 3)
Aa. put 1 into the first empty position
1, -, -
now we have to solve the problem: permutations from 2, 3
Ba. put 2 into the first empty position
1, 2, -
only the last number stays - take the last empty position
1, 2, 3
step back to the last optional choice: (Ba)
Bb. put 2 into the other empty position
1, -, 2
only the last number stays - take the last empty position
1, 3, 2
step back to (Bb), but since the number 2 has already been to all empty positions you need to step even higher (Aa)
Ab. put 1 to the other empty position
-, 1, -
etc.
2, 1, -
2, 1, 3
-, 1, 2
3, 1, 2
-, -, 1
2, -, 1
2, 3, 1
-, 2, 1
3, 2, 1
For further details study the DFS (Depth First Search) algorithm. That's the technique you will probably need to use.
Do it as your homework ;-)
The transformation of recursive processes to the iterative ones is a quite often (and certainly in this case) just a mechanic work (basically, playing with a stack). I have tried to demonstrate the way the permutations are created. There could be probably found an algorithm which would twist and turn the order of numbers in the array to generate the permutations directly, but it would be 1) not that clear 2)faster, but its complexity would be the same.
Actually, thinking about it, there is probably a similar recursive (but easy-to-be-transformed) way to get permutations: instead of playing with positions, let's play with the numbers.
- sort the numbers
- put the first not-yet-used number to the first available position
- mark the number as "used"
- problem (n-1) numbers (n-1)positions
- when we step back to the second step we must not only remember not-yet-used numbers, but also not-yet-put-to-this-position (an extra array for each position -> if the k-th position is being filled (k+1)th through to n-th are purged)
This should be a task for 2 for-loops and 2 arrays
> The transformation of recursive processes to the
> iterative ones is a quite often (and certainly in this
> case) just a mechanic work (basically, playing with a
> stack).
Placing some context on a stack while iterating is all but equivalent to recursing, so I don't consider such algorithms as beign iterative but recursive.
- Marcus Sundman
That's a point of definition (certainly not relevant to this problem), but recursive procedure, function, method, or process is the one calling directly or indirectly itself.
Otherwise, you are, of course, right.
But consider the last solution I gave - you need an extra memory, right (that array with last used numbers for a particular position) - is it iterative or recursive? Really difficult to be said...
I'm not saying it can't be done, I just remember from my college days, sitting in some sad, sad cs class while Prof told us to write a non-recursive algo for generating permuations and it wasn't easy.
I found this cool applet:
http://www.cs.ubc.ca/spider/kvdoel/bells/bells.html
n.
given the numbers 1 to m, to generate all ordered permutations of length n (eg [1,2] but not [2,1])
idx[] = int array of size n, values = 1..n;
loop {
output idx; // a permutation
i = n;
while (idx[i] == m - n + i) { // idx[i] can not be increased
// and still create a permutation
i--; //check if previous position can be increased
if (i < 1) {
your done
}
}
idx[i]++; //increase the value at the ith position
for (each position from i+1 to n) {
idx[i] = idx[i-1]+1; // reset all indexes above I to the
// lowest value possible
}
}
I have left some snags in this pseudo code, such as array indexes starting at 1, but if you follow the algorithm you should be able to code it without to much effort.
I wonder what happens with this topic.
OK, so once again to definitions. I will write what I understand under which term, and let's see what's still missing:
Let's have a set X of distinct numbers {x1, x2, ... xm}, thus |X| = m
combinations without repeating of the length n are all the subsets Y = {y1, ... yn} where y1 <> y2 <> ... <>yn, and yj are members of X. The numbers of such combinations is m above n (numerically, m! / (n-m)!n!)
variations without repeating of the length n are all the ordered subsets Y = {y1, ... yn} where y1 <> y2 <> ... <>yn, and yj are members of X. The numbers of such variations is (numerically) m! / (n-m)!
permutations are variations without repeating of the length m. Their number is m!
pekoe (orange broken? ;-) gave an algorithm how to get (in my terms) all the combinations from m members of the length n (without repeating). If I find time tonight I will prepare a Java-like code how to introduce ordering of those (basically, how to get permutations of a given set). One can easily see that those two algorithms together can actually lead to all combinatorics subsets.
I found some time today. So here is something that does not like as a recursive stuff whatsoever:
- let's assume that we run a special arithmetics
m = 3, we'll define operation like
increase(111)=112
increase(112)=113
increase(113)=121
...
increase(333)=111 , indicated overflow
(hope it's clear what I mean)
and a special relation isPermutation(), which is valid always when each member of the n-tuple is different from the others
By doing so, we can have all the permutation on 1, 2, ..., n via:
tuple[1..m] = 1
repeat
if (tuple.isPermutation()) output (tuple)
overflow = tuple.increase()
until overflow
Note:this algorithm is a bit wasting (tests m^m tuples instead of only needed m!), but on the other hand it needs zero extra memory. Everything else somehow looks like the recursion, because it needs some structures simulating local variables in the recursive processing.
Wouldn齮 it be possible to precalculate permutations and store them in tables. Each permutation can be densly represented. All it takes is a little bit-fiddling (it's for example possible to store 5 integers of each 3 bits (integers [0..7]) in a 16-bit short integer.)
Lets say you store all permutations of lengths N=2 to 5. You齞 end up with 4 arrays (lengths 2, 6, 24, and 120) of precalculated permutations.
Now its possible to decompose arrays of greater lengths N>5 into permutations of permutations. For example N=6. You can decompose this as the following. Generate all permutations for N=2, then for each such permutation generate all permutations for N=3.
It齭 also possible to store decompositions in tables. If you allow an iteration depth of for exampel D, you can calculate the maximum N you齦l be able to handle given the number of precalculated permutation tables.
This is iterative and highly effective, just table lookups.
> has somebody given the answer allready otherwise i will
> i cannot stand the reaction of doing homework ,
> everybody somethimes is confused and needs some help
Wellcome to the real world of computing man. Mostly there are no definite answers. It's like in the trenches, you have to survive yourself. I hope my suggestion gets flak.
Funnily enough, when I was doing this problem a recursive solution didn't occur to me. Here's what I did:
NB: Curly brackets {} enclose an unordered set, ordinary brackets () enclose an ordered set, square brackets [] enclose an array index.
The n! permutations of {1,...,n} have a natural ordering, with (1, 2,... ,n) being the lowest and (n, n-1,... ,1) being the highest. So we require a method permute(Permutation p) which will take one permutation and return the next one in the sequence. To generate all perumatations we iterate permute() n! times, starting with the first permutation.
Step 1: scan the elements of Permutation p from right to left, continuing as long as the elements you examine are in reverse order. You stop at position j, which is the first position you find where p[j] < p[j+1].
Step 2: Now examine all elements p[k] for k > j (i.e. all elements to the right of p[j]), and find the smallest element which is greater than p[j].
Step 3: Swap the positions of p[j] and p[k]
Step 4: Sort the elements to the right of position j into ascending order.
So there's another iterative solution for you to add to the pile. Now, does anyone know an algorithm which takes integers m, n (m <= n!) and calculates directly the mth permutation of n integers, without iterating through the previous m-1 permutations?
> So there's another iterative solution for you to add
> to the pile. Now, does anyone know an algorithm which
> takes integers m, n (m <= n!) and calculates directly
> the mth permutation of n integers, without iterating
> through the previous m-1 permutations?
Defs :
(1,2,3) : The ordered set 1,2,3
aset[x] : The x's element of the ordered set 'aset' (starting at 1)
Ex : (1,2,3)[2] = 2
aset & x : The concatenation of aset and x
Ex : (1,2,3) & 2 = (1,2,3,2)
Algorithm :
List makePerm(int permNum) {
perm <- ();
remainingNumbers <- (1,2,..,n);
for i in 1..(n-1) {
num <- (permNum div (n-i)!) + 1;
perm <- perm & remainingNumbers[num];
removeElementAt(remainingNumbers,num);
permNum <- permNum mod (n-i)!;
}
perm <- remainingNumber[1]; last remaining number
return perm;
}
However, even if the values of x! are precalculated and only looked up in a table, this will probably be slower than JirMac's algo when iterating over all possible permutations.
> So there's another iterative solution for you to add to the pile. Now, does anyone know
> an algorithm which takes integers m, n (m <= n!) and calculates directly the mth
> permutation of n integers, without iterating through the previous m-1 permutations?
For those who are interested, I did some benchmarks a few years ago. My bell-ringing implementation was the fastest, being twice as fast as the iterative algorithm described and ten times faster than the recursive one. I implemented the direct algorithm you enquire after later, so haven't benchmarked it against the others.
The following is an example which gives 3-permutations from 5 integers.
This can be extended to calculate every permutation from 5 (or n) integers.
final public class Permutation3From5{
public static void main(String[] args){
MyList[] L0 =new MyList[5];
MyList list=null;
for(int i=0;i<5;i++){
for(int k=0;k<5;k++){
if(k!=i){
for(int q=0;q<5;q++){
if(q!=i&&q!=k){
L0=new MyList(i,new MyList(k,new MyList(q,null)));
list= L0;
while(list!=null){
System.out.print(list.toString());
list=list.getNext();
}
System.out.println();
}
}
}
}
}
} //end of main
} end of class Permutation3From5
//The next class is a type of linked list defined for the purpose of here
class MyList{
int n;
MyList next;
MyList(int n, MyList list){
this.n=n;
this.next=list;
}
MyList getNext(){
return this.next;
}
public String toString(){
return String.valueOf(this.n);
}
}
> If a recursive method is easiest, what would it look
> like?
would look like something like this for string '1 2 3 4' :
1 2 3 4//A
/ \
/\
12 3 4 // B
/ \
/\
23 4 // C
/ \
/\
34// D
you split each incoming set to permute() into 2 sets, one has one set element, and the other has the rest, you call premute on the set with the rest (until it has one) .... when it does have one ( state D): you move up to C and make permutations of 3 and 4. with that set you move up to B and add 2 to all the permutations which creates all permutations of (2 3 4), finally with that set you move back to A and add 1 to all your permutations from B giving you a resulting set that contains all permutations of (1,2,3,4).
Seems easy to think about. code for this isn't probably much prettier than for any other solution though
> Hi,
> how can I get the n-permutation of a given array of
> numbers? By n-permutation I mean e.g. for an array
> like 1|2|3|4 there are the 3-permutations 1|2, 1|3,
> 1|4, 2|3 and so on.
> I tried to find a method, but I was not successful.
> Now I would like to write it on my own, but I have no
> idea about the algorithm...
> I am a beginner and would be thankful for any help
> Sabina
oh dear, it seems that you only want algorithm, but i allready implemented it in code.
anyhow, i'm not sure that i've got right the meaning of permutation that you're talking about...
i figured there was 24 different permutations for array {1,2,3,4}, but you say there are only four.
ok, now to my algorithm that i implemented.
my theory is that if you have array of size m, then you may compute first element of n-th permutation with a simple formula: n/(m-1)!
where the answer is position, which element of all those that are left, should be taken.
now you make a recursive call to get the first element of the tail of that array.
but you have to recalculate n and m meanwhile (which are very easy as well: m will just be decremented, and n=n-(m-1)!*(n/(m-1)!) )
/**
* class Perm has public method perm, that calculates m'th
* permutation of array m
* and main method that may be used to test it.
*/
public class Perm {
public static void main(String[] args) throws Exception {
int[] test = {0, 1, 2, 3, 4};
printA(perm(args.length < 1 ? 0 :Integer.parseInt(args[0]), test));
}
private static void printA(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i ]);
}
}
public static int[] perm(int n, int[] m) {
int len = m.length;
n = n % fact(len);
int[] result = new int[len];
for (int i = 0; i < len; i++) {
int fact = fact(m.length - 1);
result[i ] = m[n / fact];
m = remNth(m, n / fact);
n -= fact * (n / fact);
}
return result;
}
private static int[] remNth(int[] src, int n) {
int[] result = new int[src.length - 1];
for (int i = 0, j = 0; i < src.length; i++, j++) {
if (i == n) {
j--;
} else {
result[j] = src[i ];
}
}
return result;
}
private static int fact(int n) {
return (n == 0 ? 1 : n * fact(n - 1));
}
}
my code has bruteforce solutions for some simple tasks, you should optimize those out... othervise it might even be O(N) complex (where N is size of array)
and with very little modification you may make my code to generate permutations of Object arrays, not simply imt arrays... (maybe it would be useful somewere)
public class Permutations {
public static void swap (int i, int j, char[] array) {
char tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void permute(char[] cbuf, int index) {
if (index == cbuf.length-1) {
System.out.println (cbuf);
} else {
for (int i=index;i<cbuf.length;i++) {
swap(index, i, cbuf);
permute ((char[])cbuf.clone(), index+1);
}
}
}
public static void main(String args[]) {
if (args.length != 1) {
System.out.println("usage: java Permutations string");
}
char[] cbuf = args[0].toCharArray();
permute(cbuf,0);
}
}
>
hi you can check my code for that purpose....
it has a class for your purpose.
it collects all possible combiantion into a vector.
for your purpose you have pass a String "12345678" to constructor of
class GetPermutations. another constructor of this class also takes Vector as an argument.
I tried to make it as genralized as possible but I was in a little bit hurry, so variale names may not be according to satandards.
i hope it will solve your problem.
i checked it on my own it worked fine .
/*****************************************************/
import java.util.Vector;
public class Test
{
public static void main(String args[])
{
String strInput="12345678";
GetPermutations test=new GetPermutations (strInput);
Vector all=test.getAllPermutations();
System.out.print("all "+all.size() + " permutations of "+strInput+" are \n");
for(int i=all.size()-1;i>=0;--i)
{
System.out.print((String)all.elementAt(i)+"\t");
}
}
}
class GetPermutations
{
Vector vectorAllPermutations;
Vector vectorInput;
StringBuffer sbCurrentCombination;
int intMax;
protected GetPermutations()
{
vectorAllPermutations=new Vector();
sbCurrentCombination=new StringBuffer();
}
GetPermutations(Vector vectorInput)
{
this();
this.vectorInput=vectorInput;
intMax=vectorInput.size();
}
GetPermutations(String strInput)
{
this();
vectorInput=new Vector();
for(int intCount=strInput.length()-1;intCount>=0;--intCount)
{
vectorInput.add(new Character(strInput.charAt(intCount)));
intMax=vectorInput.size();
}
}
public Vector getAllPermutations()
{
makePermutations(vectorInput);
return vectorAllPermutations;
}
public void makePermutations(Vector input)
{
if(input.size()==1)
{
char chToAdd=((Character)input.elementAt(0)).charValue();
sbCurrentCombination.append(chToAdd);
vectorAllPermutations.add(sbCurrentCombination.toString());
sbCurrentCombination.setLength(intMax-1);
}
else
{
for(int intCounter=input.size()-1; intCounter>=0 ; --intCounter)
{
if(sbCurrentCombination.length()>intMax-input.size())
sbCurrentCombination.setLength(intMax-input.size());
Vector temp=new Vector();
temp.addAll(input);
char chToAdd=((Character)temp.remove(intCounter)).charValue();
sbCurrentCombination.append(chToAdd);
makePermutations(temp);
}
}
}
}
My example posted earlier in this thread (posted Nov 1, 2002 6:11 AM) had a few minor error and was not readable.I will post here the corrected version with a readable form.
final public class Permutation3From5{
public static void main(String[] args){
MyList L0 =new MyList(0,null);
MyList list=null;
for(int i=0;i<5;i++){
for(int k=0;k<5;k++){
if(k!=i){
for(int q=0;q<5;q++){
if(q!=i&&q!=k){
L0=new MyList(i,new MyList(k,new MyList(q,null)));
list= L0;
while(list!=null){
System.out.print(list.toString());
list=list.getNext();
}
System.out.println();
}
}
}
}
}
} //end of main
} //end of class Permutation3From5
//The next class is a type of linked list defined for the purpose of here
class MyList{
int n;
MyList next;
MyList(int n, MyList list){
this.n=n;
this.next=list;
}
MyList getNext(){
return this.next;
}
public String toString(){
return String.valueOf(this.n);
}
}
I implemented Dijkstra's algorithm (http://www.cut-the-knot.com/do_you_know/AllPerm.shtml) in Java:
public class Permuter extends Object
{
int m_level;
int[] m_value;
int m_permCt = 0;
public Permuter(int size)
{
m_level = -1;
m_value = new int[size];
}
public void permute()
{
visit(0);
System.out.println("\nTotal permutations = " + m_permCt);
}
public void visit(int k)
{
m_level++;
m_value[k] = m_level;
if (m_level == m_value.length)
{
addPermutation();
}
else
{
for (int i = 0; i < m_value.length; i++)
{
if (m_value[i] == 0)
visit(i);
}
}
m_level--;
m_value[k] = 0;
}
void addPermutation()
{
for (int i = 0; i < m_value.length; i++)
{
System.out.print(m_value[i] + " ");
}
System.out.println();
m_permCt++;
}
}